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

Граф – це упорядкована пара множин {V,E}, де V – множина вершин, E – множина ребер. Графи підрозділяються на орієнтовані й неорієнтовані.

Виділяють такі види графів: порожній, повний, тотожний, симетричний, регулярний (однорідний), дуальний, нуль-граф, псевдограф, мультиграф.

Графи можна задати:

• графічно;

• переліком елементів;

• матрицею суміжності;

• матрицею інциденцій.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 239-246, c. 248-260; 2, c. 239-246, c. 248-260; 3, c. 89-102; 6, c. 21-41, c. 178-189; 9, c. 156-181; 12, c. 297-309; 14, c. 11-53; 17, c. 64-128].

Тема 15. Ейлерові та гамільтонові ланцюги і цикли

Прийнято пов’язувати зародження теорії графів як математичної дисципліни з роботою Леонарда Ейлера 1736 р., у якій знайдено умову існування у зв’язному графі циклу, що містить всі ребра графа (без повторень). Такий цикл тепер називається ейлеровим. Як показує простий приклад, є графи, що не містять ейлерові цикли.

Гамільтоновим циклом у графі G=(X,Y) називається простий цикл Q=(X,Y₀), який містить всі вершини графа, незалежно від того, чи є G орієнтованим. Вимога простоти циклу є принциповою: за гамільтоновим циклом Q можна обійти всі вершини х графа G, відвідуючи кожну проміжну (тобто не початкову і не кінцеву) вершину тільки один раз. Сам граф G, в якому існує гамільтонів цикл, називається гамільтоновим графом.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 246-248, c. 304-322; 2, c. 246-248, c. 304-322; 4, c. 320-325; 8, c. 83-91; 12, c. 312-316, c. 350-353; 14, c. 53-77; 17, c. 64-128].

Тема 16. Планарність графів

Граф G=(X,Y) називається повним, якщо він не містить петель і кратних ребер, а також кожна пара вершин суміжна. Повний граф позначається K_n, де n – кількість вершин.

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

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

Граф G є плоским, якщо його ребра перетинаються лише у вершинах.

Граф G₁ є планарним, якщо існує ізоморфний до нього граф G, який є плоским.

Графи К₅ і К_3,3 відіграють фундаментальну роль у теорії планарності. Їх називають графами Понтрягіна-Курантовського. Граф G₁ є планарним лише тоді, коли він не містить підграфів Понтрягіна-Курантовського.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 242; 2, c. 242; 8, c. 126-151; 12, c. 316-317; 17, c. 64-128].

Тема 17. Відстані на графах

Найменша довжина ланцюга, що з'єднує вершини a і b графа G, називається відстанню між ними. Позначається d(a,b).

Відстань має властивості, що задовольняють аксіомам метрики.

1. Якщо між вершинами a і b існує відстань, то вона більше нуля, причому відстань від однієї вершини до цієї ж вершини дорівнює нулю.

d(a,b)0;

d(a,a)=0.

2. Відстань між вершинами a і b дорівнює відстані між вершинами b і a.

d(a,b)=d(b,a).

3. Якщо існує три вершини a, b і c, причому c знаходиться між вершинами a і b, то відстань між вершинами a і b буде менше чи дорівнюватиме сумі відстаней між вершинами a і c та вершинами c і b.

d(a,c)+ d(c,b) d(a,b).

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

Задачі відшукання найкоротших відстаней між вершинами графа (мережі) із заданими вагами ребер часто зустрічаються на практиці і мають очевидний економічний зміст. Це саме можна сказати і про задачі пошуку оптимальних шляхів в орієнтованих мережах. Один з ефективних алгоритмів розв’язку таких задач – алгоритм Дейкстри.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 292-304; 2, c. 292-304; 17, c. 64-128].