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

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

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

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

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

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

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

Зауважимо, що ребро графа завжди має вершини: одну (це ребро-петля) або дві.

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

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

Степінь вершини – це кількість ребер, яким належить ця вершина. Степінь вершини А позначається Р(А)=3 (вершина належить трьом ребрам)

Нехай задано граф з n вершинами: А1, А2, …, Аn. Кажуть, що існує шлях від вершини Аі до вершини Аj, якщо існує послідовність ребер, яка з’єднує вершини Аі та Аj. Вершини Аі та Аj називаються зв’язними, якщо існує шлях від Аі до Аj.

Граф э зв’язним, якщо будь-яка пара його вершин зв’язна.

Зауважимо, що повний граф завжди є зв’язним, але не всякий зв’язний граф є повним.

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

Для вершини 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, 2-5, 5-6, 6-3, 3-1),  (1-2, 2-5, 5-6, 6-3, 3-7, 7-4, 4-1),  (1-3, 3-5, 5-6, 6-3, 3-7, 7-4, 4-1).

Якщо цикл через кожну вершину проходить лише один раз, то такий цикл називається простим. Для вершини 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).

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

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

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

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

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

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

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

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

Прикладом ейлерового і гамільтонового графів є багатокутник.

Завдання

1.    Намалювати граф, який містить 4 вершини, 2 ребра, 1 петлю, причому 1 вершина є ізольованою.

2.    Намалювати нуль-граф.

3.    Намалювати повні графи, які містять

            а) 4 вершини, б) 5 вершин.

4.    Зобразити плоский і просторовий графи з

           а) 3 вершинами, б) 4 вершинами.

5.    Визначити степінь всіх вершин графів із завдання №4.

6.    Намалювати граф з хоча б 2 зв’язними  вершинами.

7.    Намалювати повний зв’язний граф і не повний зв’язний граф.

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

            а) належить трикутнику і чотирикутнику, б) тільки трикутнику, в) тільки чотирикутнику.

9.    Обчислити довжини всіх циклів цих трьох вершин.

10.    Намалювати дерево і ліс.

11.    Задати орієнтований граф з трикутника і чотирикутника зі спільною стороною.

12.    Визначити цикли графа із завдання №11.

13.    Визначити вхідні, вихідні степені вершин графа із завдання №11.

14.    Намалювати ейлерів граф.

15.    Намалювати гамільтонів граф.