188

Розділ VII Теорія графів

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

За допомогою інструментарію теорії графів розв’язується велика кількість економіко-математичних задач, зокрема наведена у вступі задача „про призначення”, задача календарного планування, мережевого планування тощо. Взагалі теорія має велике значення у всіх галузях науки, які стосуються аналізу і управління економікою.

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

Означення 7.1. Нехай – довільна множина, – деяка сукупність пар вигляду , де . Упорядкована пара , яка складається з множини та сукупності , називається графом із множиною вершин V і множиною ребер E.

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

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

Означення 7.2. Кількість вершин графа називають його порядком.

Приклад 7.1. Розглянемо зображення графів, що наведені на рис.7.1.

Рис.7.1.

Граф має множину вершин і множину ребер . , тобто порядок графа дорівнює 4, .

Граф має множину вершин і множину ребер . , . Це граф порядку 5.

Якщо є ребро в графі , тобто , то можна сказати:

• вершини і суміжні в графі ;

• вершини і є кінцями ребра ;

• вершини та інцидентні ребру ;

• ребро інцидентне вершині ().

Означення 7.3. Кількість ребер графа, інцидентних деякій вершині , називається локальним степенем, або просто степенем вершини і позначається .

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

Приклад 7.2. Розглянемо графи з рис.7.1.

В графі суміжними є всі вершини , суміжні трійки ребер ; ; ; .

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

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

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

Лінії, що зображають ребра графа, можуть перетинатися, але точки перетину не є вершинами (перетин ребер і графу на рис.7.1.). Різні ребра можуть бути інцидентні одній і тій самій парі вершин (рис.7.2 а), такі ребра називаються кратними. Цей випадок відповідає наявності декількох однакових пар .

Означення 7.6. Граф, що містить кратні ребра, називається мультиграфом. Ребро може з’єднувати деяку вершину саму з собою (рис.7.2 б), таке ребро називається петлею. Цей випадок відповідає наявності в множині пар вигляду . Граф з петлями та кратними ребрами називається псевдографом (рис.7.2 б).

Прикладом звичайного графу є граф на рис.7.1.

Рис.7.2.

Означення 7.7. Якщо пари вважаються упорядкованими, то граф називається орієнтованим або орграфом. Інакше граф називається неорієнтованим. Ребра орієнтованого графа прийнято називати дугами та зображати напрямленими відрізками, як на рис.7.2 в.

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

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

Означення 7.8. Скінченний неорієнтований граф без петель і кратних ребер називається звичайним.

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

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