Основні поняття теорії графів

Теорія графів

Виникнення теорії графів пов’язують з іменем Леонарда Ейлера, який у 1736 р., коли працював в Російський Академії наук, не тільки розв’язав популярну на той час головоломку про кенігсбергські мости, а й знайшов критерій існування в графі спеціального маршруту (ейлерового циклу). Це задача про те чи можливо здійснити прогулянку таким чином, що якщо вийти з будь-якого місця міста повернутися в нього, проходячи один раз по кожному мосту? Місто Кенігсберг (Калінінград) розташовано на чотирьох частинах суші a, b, c, d тому їх було представлено у вигляді вершин, а сім мостів зображені ребрами, які з’єднують відповідні вершини. В результаті отримали граф (рис.1). Ейлер довів, що подібний маршрут має бути тільки для графа у якого кожна вершина зв’язана парним числом ребер .

Рис. 1.

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

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

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

Основні поняття теорії графів

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

Граф позначається буквою G, множина вершин V, множина відношень (дуг або ребер) – E, упорядкована пара G = (V, E). Нехай V = {v₁, v₂, ..., v_n} і E = {e₁, e₂...,e_m}

При цьому елементи множини V зобра­жають крапками на площині, а ребра (v_i, v_j ) — відрізками (прямоліній­ними або криволінійними), які з'єднують крапки v_i та v_j. Граф називаєть­ся скінченним, якщо множини його вершин і ребер є скінченними. Кількість вершин графа n, а кількість ребер m. Граф, який містить n вершин та m ребер називають (n, m) - графом.

Кількість вершин n(G) графа називають його порядком.

Рис. 2.

Граф, який є моделлю симетричного відношення називається простим або симетричним графом, неорієнтованим графом.

Граф G = (V, E), V = {v₁, v₂, v₃ v₄,, v₅} і E = {e₁, e₂, e₃, e₄, e₅, e₆}. Ребра можуть задаватися ще послідовністю вершин E = {(v₁, v₅), (v₁, v₅), (v₁, v₃), (v₂,,v₃),(v₂,v₄), (v₂, v₅), (v₄, v₅)}.

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

Основна ознака мультиграфа – між деякими його вершинами існує декілька ребер або дуг.

Граф, який є моделлю несиметричного відношення називається орієнтованим графом. Щоб змоделювати несиметричне відношення треба вказати направлення ребер. Направлення показують стрілочкою. Стрілочка, яка відображає несиметричне відношення називається дугою графа.

Рис. 3.

Таким чином для простого графа – граф складається з двох множин (вершин та ребер), для несиметричного графа – граф складається з двох множин (вершин та дуг).

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

Рис. 4.

Якщо граф G = (V, Æ ) - множина відношень порожня (рис. 4, а).

Але якщо множина вершин V - порожня, то порожньою є також множина Е. Такий граф називається порожнім. Такий граф нази­вається нуль-графом і позначається Æ (рис. 4, b).

Лінії, що зображають ребра графа, можуть перетинатися, але точки перети­ну не є вершинами; різні ребра можуть бути інцидентними одній і тій самій парі вершин (рис.2), такі ребра називаються кратними. Цей випадок відповідає наявності кількох однакових пар E = {(v₁, v₅), (v₁, v₅). Граф, що містить кратні ребра, називається мультиграфом.

Ребро може з'єднува­ти деяку вершину саму з собою (рис. 5), таке ребро називається петлею. Цей випадок відповідає наявності в множині Е пар вигляду (v, v). Граф із петлями та кратними ребрами називається псевдографом.

Рис. 5

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

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

Є специфічний вид ребра або дуги, які і в симетричному і в орієнтованому називається однаково петля - модель рефлексивного відношення

Рис. 6.

Повний граф G = (V, E), n = , m = .

Кожне ребро e_k Î E з’єднує пару вершин v_i, v_j Î V, які є його кінцями ці вершини граничні. Розрізняють початкову вершину з якої дуга виходить та кінцеву вершину , в яку дуга входить. Дві вершини (граничні вершини) які з’єднані двома або більше ребрами називаються кратними.

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

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

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

Інцидентність. Задання графа за допомогою матриці інцидентності.

Задати граф означає задати множини його вершин і ребер, а також відношення інцидентності. Коли граф G — скінченний, тоді вершини даного графа v₁ ,v₂,,..., v_n, а його ребра е₁, е₂,..., е_m. Відношення інцидентності можна оз­начити матрицею S= , що має n рядків й т стовпців. Рядки відпо­відають вершинам графа, а стовпці відпо­відають його ребрам. Якщо вершина v_i є інцидентною ребру е_о, , то s_ij = 1, в іншому випадку s_ij = 0. Це матриця інци­дентності звичайного графа G, яка є одним із способів його визначення (для графа на рис. 2).

S_ij =

;

У матриці інцидентності орієнтованого графа G, якщо вершина v_i —початок ребра e_j, то s_ij = 1; якщо v_i: - кінець e_j, то s_ij = -1. Кількість одиниць у рідку дорівнює степені відповідній вершині (для орграфа кількість позитивних одиниць визначає позитивну степінь, а кількість від’ємних одиниць - від’ємну степінь). Нульовий рядок відповідає ізольованій вершині, а нульовий стовпець - петлі.

Треба мати на увазі, що нульовий стовпець матриці інцидентності лише вказує на присутність петлі, але не містить відомостей про те, з якою вершиною зв’язана ця петля.

S_ij =

S_ij = .

Відношення інцидентності можна задати ще списком ребер графа. Кож­ний рядок цього списку відповідає ребру, в ньому записано номери вер­шин, інцидентних йому. Для неорієнтованого графа порядок цих вершин у рядку довільний, для орієнтованого першим записується номер або інше найменування початку ребра, а другим — його кінця. У таблицяхнаведено списки ребер для графів, зображених на рис. 2 та 3.

Таблиця 1