Тема 4.1 Основи теорії графів. Способи завдання графів.

Графічні представлення-зручний спосіб ілюстрації змісту різних понять, що відносяться до інших способів формалізованих представлень (наприклад, діаграми Венна й інші графічні ілюстрації основних теоретико-множинних і логічних представлень).

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

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

Слід мати на увазі, що при зображенні графа не всі деталі малюнка однаково важливі; зокрема, несуттєві геометричні властивості ребер (довжина, кривизна і т.д.) і взаємне розташування вершин на площині.

Графічні представлення у вузькому розумінні - це опис досліджуваної системи, процесу, явища засобами теорії графів у виді сукупності двох класів об'єктів: вершин і з'єднуючих їхніх ліній – ребер чи дуг. Графи і їх складові характеризуються властивостями і набором припустимих перетворень (операцій) над ними.(Рис.1)

Графом G називається сукупність двох множин: вершин V і ребер Е, між елементами яких визначене відношення інцидентності - кожне ребро інцидентне рівно двом вершинам , які воно з'єднує. При цьому вершина і ребро е називаються інцидентними один одному, а вершини , що є для ребра е кінцевими крапками, називаються суміжними. Часто замість , пишуть відповідно , .

Ребро, щоз'єднує дві вершини, може мати напрямок від однієї вершини до іншої; у цьому випадку воно називається спрямованим, чи орієнтованим, чи дугою і зображується стрілкою, спрямованою від вершини, що називається початком, до вершини, що іменується кінцем.

Граф, що містить спрямовані ребра (дуги) з початком і кінцем , називається орієнтованим (орграфом), а ненаправлені - неорієнтованим (назвемо н-графом). (Рис.2)

Ребра, що інцидентні одній і тій же парі вершин, називаються кратними(на рис.2 ребра між вершинами b і d).Граф, що містить кратні ребра, іменується мулътиграфом (Рис.2). Ребро, кінцеві вершини якого збігаються, називається петлею.(на рис.2 ребро на вершині с)

Граф називається кінцевим, якщо множина його елементів (вершин і ребер) конечна, і порожнім, якщо його множина вершин V(a значить і ребер Е) порожня. Граф без петель і кратних ребер іменується повним, якщо кожна пара вершин з'єднана ребром.(рис.3)

Доповненням графа G називається граф G’ , щомає ті ж вершини, що і граф G, і має тільки ті ребра, які потрібно додати до графа G, щоб одержати повний граф.(рис.4)

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

Локальним степенем (чи просто степенем) вершини н-графа G називається кількість ребер p(v), що інциденті вершині v. Вершина, що інцидентна єдиному ребру називається висячою. В н-графі сума ступенів усіх вершин дорівнює подвоєному числу ребер т графа, тобто парна (передбачається, що в графі з петлями петля дає внесок 2 у ступінь вершини):

(1)

звідси випливає, що в н-графі число вершин непарного ступеня парне.

Для вершин орграфа визначаються два локальні ступені:

– р₁ (v) - число ребер з початком у вершині v, чи кількість вихідних з v ребер;

– р₂ (v) - кількість вхідних у v ребер, тобто для яких ця вершина є кінцем.

Петля дає внесок 1 в обидві ці ступені.

В орграфі суми ступенів усіх вершин р₁(v) і р₂ (v) дорівнюють кількості ребер т цього графа, а виходить, і рівні між собою:

(2)

Графи G₁ і G₂ рівні, тобто G₁ = G₂, якщо їхні множини вершин і ребер (виражених через пари інцидентних їм вершин) збігаються: V₁ = V₂ і Е₁ = Е₂.

Ми познайомилися з двома способами опису графів: графічним, і у виді двох множин вершин V ребер Е, коли кожне ребро визначене парою інцидентних йому кінцевих вершин ( ). Є й інші способи, використовувані в теорії графів.

У загальному виді задати граф - значить описати множини його вершин і ребер, а також відношення інцидентності. Для опису вершин і ребер досить їх занумерувати. Нехай v_1,v₂,... ,v_j,... ,v_n - вершини графа G; e₁,e₂,... , е_i,... ,е_т – ребра. Відношення інцидентності задається:

– матрицею інцидентності розміру т х п : по вертикалі і горизонталі вказуються вершини і ребра відповідно, а на перетинанні i-ої вершини j-го ребра у випадку неорієнтованого графа проставляється 1, якщо вони інциденті, і 0 - у протилежному випадку, тобто

1, якщо ребро е_i, інцидентне вершині v_j ,

a_ij=

0 у противному випадку,

а у випадку орграфа: -1, якщо вершина є початком ребра, 1 - якщо вершина є кінцем ребра, і 0 - якщо вершина і ребро не інцидентні; якщо деяка вершина є для ребра і початком, і кінцем (тобто ребро - петля), проставляється будь-яке інше число, наприклад 2, тобто

-1, якщо вершина v_j - початок ребра е_i;

1, якщо вершина v_j - кінець ребра е_i;

a_ij= а (будь-яке число, відмінне від -1, 1, 0), якщо е_i - петля, a v-інцидентна їй вершина;

0 в інших випадках;

– списком ребер графа, представленим двома стовпцями: у лівому перелічуються всі ребра а в правому - інцидентні йому вершини ; для н-графа порядок вершин у рядку довільний, для орграфа першим стоїть номер початку ребра. Список ребер графа є, власне кажучи, скороченим представленням матриці інцидентності (у кожнім її рядку тільки два елементи відмінні від 0 чи навіть один, якщо ребро - петля);

– матрицею суміжності || b_kl|| - квадратною матрицею розміру п х п: по вертикалі і горизонталі перелічуються усі вершини , а на перетинанні k-ої і 1-ої вершин у випадку н-графа проставляється число, рівне числу ребер, що з'єднують ці вершини; для орграфа b_kl дорівнює числу ребер з початком у к-ій вершині і кінцем у 1 -ій. Матриця суміжності н-графа симетрична щодо головної діагоналі b_kl= b_lk., і всі його ребра визначаються верхнім правим трикутником матриці, розташованим над діагоналлю, включаючи останню. Таким чином, число ребер н-графа по матриці суміжності дорівнює сумі елементів b_kl, розташованих на діагоналі і вище, дорівнює . Число ребер орграфа дорівнює і визначаються всіма елементами b_kl матриці суміжності.

Приклад 1.Задати різними способами графи, що зображені на рис.5

Матриця інцидентності

Граф Н

Граф G

Матриця суміжності