На головну

 матриці інціденцій |  списки суміжності |  B f c b d e d b f d |  ВИЗНАЧЕННЯ |  Доведення |  ВИЗНАЧЕННЯ |  ТЕОРЕМА 5.3 |  ВИЗНАЧЕННЯ |  ВИЗНАЧЕННЯ |  ВИЗНАЧЕННЯ |

ВИЗНАЧЕННЯ

  1.  E. підрахунку суми балів, визначення індексу ПМА за формулою.
  2.  I Розрахунок витрат для визначення повної собівартості вироби (роботи, послуги), визначення рентабельності його виробництва
  3.  I. Яке визначення найбільш повно виражає сутність програмованого навчання?
  4.  III. Визначення міри покарання
  5.  VI. Визначення напору на виході з підпірного насоса
  6.  А 6. ЗАМІНА ПРІДАТОЧОГО ПРОПОЗИЦІЇ Відокремлені означення.
  7.  А. Визначення сценарію

Графом називається всяка пара G = (V, U), в якій V - Це кінцеве безліч, зване безліччю вершин графа, а U - Кінцеве безліч ребер графа.

Будь-яке ребро графа представляється або однією парою вершин (а,b), Або двома протилежними парами (a,b) І (b,a). Якщо ребро з Uпредставляється тільки однією парою (a, b), То воно називається орієнтованим ребром, провідним з a в b. При цьому aназивається початком, а b -кінців такого ребра.

якщо ребро u представляється двома парами (a, b) І (b, a),
 то u називається неорієнтованим ребром. Будь-яке неорієнтоване ребро між вершинами a иb веде як з a в b, Так і назад. При цьому вершини a иb є як началами, так і кінцями цього ребра. Кажуть, що ребро веде як з a в b, так і з b в a.

Всякі дві вершини, які з'єднуються ребром, називаються суміжними.

Будемо розглядати тільки такі графи, у яких все ребра різні і не допускається одночасна зв'язок однієї і тієї ж пари вершин орієнтованим і неорієнтованим ребром або парою протилежно орієнтованих ребер. Графи, які допускають можливість кількох ребер, що з'єднують пари вершин, називаються мультиграфом. Такі графи в даному навчальному посібнику не розглядаються.

(В останньому випадку відповідна пара ребер буде розглядатися як одне неорієнтоване ребро.)

Тоді ребра графів можна представляти просто парами вершин виду (a, b), Для яких додатково вказується; чи є ребро орієнтованим чи ні. У цьому випадку число ребер графа збігається з числом пар вершин, які представляють собою ребра графа.

Тому в подальшому будемо вважати, що U - Це безліч пар вершин. При цьому кожне ребро є однією парою вершин або двома парами. Тобто, якщо G = (V, U) І пара (a, b) Являє ребро графа G, То допустима запис (a, b) I U.

зауваження. Можна вважати, що перераховані умови забороняють будь-яке дублювання ребер. Введені обмеження не призводять до обмеженості проведеного нижче вивчення графів, визначення і результати якого можуть бути перенесені або узагальнені на випадок графів, що мають довільні кількості ребер між парами вершин. При поданні графів з кратними ребрами можна вважати, що будь-яка пара вершин в них з'єднана не більше ніж одним ребром, якому зіставлено числова характеристика, що дорівнює кратності ребер між парами вершин. Така характеристика ребер виявляється корисною у випадках, коли подаються ребрами зв'язку відносяться до різних класів або забезпечені додатковою інформацією про довжину, вартості або пропускної здатності.

Ребро, у якого вершини початку і кінця збігаються, називається петлею.

Число ребер, що виходять з деякої вершини a і відмінних від петель, називається ступенем цієї вершини і позначається як d(a). Вершина a для якої виконано рівність d(a) = 0, називається ізольованою.

Граф, все ребра якого неорієнтовані, називається неорієнтованим графом.

Як уже зазначалося, найпростішим способом представлення графів є їх геометрична реалізація. При цьому вершини графів зазвичай представляються точками простору, які позначені позначеннями вершин.

Розглянемо приклад геометричного завдання графа, наведений на рис. 5.2 .:

a

b

v

e

C d

Мал. 5.2.

Графи можна зображувати так, щоб дуги, відповідні ребрах, перетиналися. Таке уявлення графів не є геометричній реалізацією, але в деяких випадках може виявитися корисним або кращим.

Крім наочного геометричного зображення і представлення графів використовуються і інші способи завдання. Вони дозволяють представляти графи у вигляді структур, які можна зберігати і обробляти за допомогою спеціальних алгоритмів і програм.

Розглянемо основні способи завдань графів за допомогою спеціальних структур.

1. списки ребер

Подання довільного графа за допомогою списку ребер складається в заповненні масиву, що містить всі пари вершин, що представляють ребра графа. Недоліком такого способу подання є можливість втрати інформації про ізольованих вершинах.

 



 ОСНОВНІ ПОНЯТТЯ |  матриці суміжності
© um.co.ua - учбові матеріали та реферати