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

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

Можна також ще сказати, що графом називається сукупність точок і ліній, в якій кінці кожної лінії належать множині точок.

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

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

Граф, у якому будь-яка пара вершин з'єднана ребрами, називається повним (мал.8, в).

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

Степенем вершини будемо називати число ребер, яким належить ця вершина. Або ще можна сказати, що степенем вершини називається кількість ребер, інцидентних даній вершині. Позначається степінь вершини а як Р(а). Наприклад, вершинаА (мал. 9, а) має степінь 3, а вершинаВ - степінь 1: Р(А) = 3; Р(В) = 1.

Нехай задано граф з N вершинами, які позначені ava2,..., aN. Кажуть, що існує шлях від вершини аі до вершини а-, якщо існує послідовність ребер, яка з'єднує вершини аі та З малюнка 10 видно, що існує шлях між вершинами А та В, оскільки існує така послідовність ребер, що їх з'єднує. У свою чергу кажуть, що вершини а1 та а - є зв'язними, якщо існує шлях від аі до а-. Це означає, що вищеназвані вершини А та В є зв'язними. А от вершини А та С, а також В та С з малюнка 10 - незв'язні, оскільки не існує жодного шляху, яким можна було б дістатися від однієї з указаних вершин до іншої.

Надалі будемо називати граф зв'язним, якщо будь-яка пара його вершин зв'язна. Зрозуміло, що повний граф завжди є зв'язним, але не всякий зв'язний граф є повним. Прикладом може бути будь-який багатокутник: він зв'язний, але не повний (мал. 11, а). Але якщо у цьому багатокутнику провести всі діагоналі, то отримаємо повний зв'язний граф (мал. 11, б).

Введемо ще один термін: циклом називається шлях, в якому збігаються початкова і кінцева вершини. На малюнку 12 зображено граф, який для кожної вершини має по кілька циклів. Наприклад, для вершини 1 існує 6 циклів: (1-2, 2-5, 5-3, 3-1), (1-3, 3-7, 7-4, 4-1), (1-3, 3-5, 5-6, 6-3, 3-1), (1-2,5, 5-6, 6-3, 3-1), (1-2, 2-5, 5-6, 6-3, 3-7, 7-4, 4-1), (1-3, 5, 5-6, 6-3, 3-7, 7-4, 4-1).

Якщо цикл через кожну вершину проходить лише один раз, то такий цикл називається простим. Як видно з малюнка 12, для вершини 1 існує чотири простих цикли: (1-2, 2-5, 5-3, 3-1), (1-3, 3-7, 7-4, 4-1), (1-2, 2-5, 5-6, 6-3, 3-1), (1-2, 2-5, 5-6, 6-3, 3-7, 7-4, 4-1).

Довжиною шляху (циклу) називається кількість ребер цього шляху (циклу). На малюнку 12 для кожного вказаного циклу вершини 1 неважко порахувати довжину: 4, 4, 5, 5, 7, 7.

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

Досі ми говорили про графи, у яких ребра не мають орієнтації, тобто на малюнку 12 ребра 1-2 та 2-1 - не можна розрізнити. Однак не в усіх задачах таке обмеження нас влаштовуватиме. Наприклад, якщо йтиметься про географічну відстань між двома містами, то у цьому випадку нас, можливо, і не буде цікавити напрям руху між ними. Але якщо метою задачі є визначення економії палива на цьому відрізку шляху, а один населений пункт розміщений на горі, другий - в низині, то ребра 1-2 та 2-1 будуть різними і для них необхідно стрілкою вказувати напрям. Такий граф, у якому для всіх ребер вказано напрям, називається орієнтованим, або орграфом (мал. 15).

Для неорієнтованого ребра графа порядок, в якому вказуються вершини, які воно з'єднує, неважливий. Для орієнтованого ребра першою вказується вершина, з якої воно виходить. В орграфі також існує поняття орієнтованого шляху: це послідовність ребер між двома вершинами з урахуванням їхньої орієнтації. Шлях в орграфі, який є циклом, називається орієнтованим циклом. До речі, порівняно з неорієнтованим графом, зображеним на малюнку 12, в орієнтованому графі (мал. 15) для вершини 1 існує вже тільки два орієнтованих цикли: (1-2, 2-5, 5-3, 3-1) та (1-4, 4-7, 7-3, 3-1). Вони ж одночасно є простими. Зв'язність орієнтованого графа визначається без урахування орієнтації його ребер.

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

Якщо ж у графі вказана ще й «вага» кожного ребра, то такий граф називається зваженим. Тобто існують неорієнтовані зважені графи та орієнтовані зважені графи (мал. 16). Прикладом може бути задача, коли задається напрям руху дорогами між населеними пунктами та вартість перевезення ними деякого вантажу.

Слід ввести поняття ще двох специфічних графів, з якими нам доведеться мати справу під час розв'язання задач. Це ейлерів та гамільтонівграфи.

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

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

Контрольні запитання

1.      Що таке граф? З яких елементів він складається?

2.      Які вершини називають інцедентними ребрам?

3.      Які вершини називають суміжними?

4.      Які вершини називають ізольованими?

5.      Який граф називають плоским, а який – просторовим?

6.      Які вершини графа називають зв’язаними?

7.      Що називають циклом у графі?

8.      Який граф називають деревом, а який – лісом?

9.      Який граф називають орієнтованим, або орграфом?

10.  Які числа називають вхідним степенем та вихідним степенем для вершини у орграфі?

11.  Який граф називають зваженим?

12.  Який граф називають ейлеревим?

13.  Який граф називають гамільтоновим?