Лекція 9. Ейлерові графи. Гамільтонові графи

видатного математика ХVIII сторіччя Л. Ейлера була задача щодо кенігсберзьких

мостів.

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

коли:
1) G – зв’язний;
2) усі його вершини мають
парні степені.
Графи,

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

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

Гамільтона, який 1859 року вперше почав вивчати ці питання. Він розглядав задачу мандрівника: обійти всі столиці заданих країн (вершини графа) по одному разу і повернутися в першу.
ЗАУВАЖЕННЯ. Гамільтонів цикл існує далеко не в кожному графі. Через кожні дві вершини графа може проходити простий цикл, а гамільтонів цикл при цьому може бути відсутній.

називають напівгамільтоновим.

мати ані кратних ребер, ані петель, ані ізольованих вершин.
Кожний

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

Еквівалентні є такі означення дерева:
а) дерево – це зв’язний граф

без циклів;
б) дерево – це зв’язний граф, у якому кожне ребро є перешийком;
в) дерево – це зв’язний граф, цикломатичне число якого дорівнює нулеві;
m – n + 1 = 0 або m = n – 1, тобто у кожному дереві кількість ребер є на одиницю менша за кількість вершин.
г) дерево – це граф, у якому для кожних двох вершин існує лише один з’єднувальний ланцюг.

циклових ребер дає в наслідок дерево
T = ( X′,

U′) таке, що:
1) X′ = X, тобто множина вершин дерева T збігається з множиною вершин графа G;
2) U′ ⊆ U, тобто кожне ребро дерева є водночас ребром графа G.
Кожне дерево T, яке задовольняє умовам 1) та 2) називається кістяковим деревом графа G.

ЗАУВАЖЕННЯ. Через те, що вилучання циклових ребер можна провадити у різні способи, то один і той самий граф має багато кістякових дерев.

які не ввійшли до T, називатимемо хордами.
Теорема. Якими б не

були остовне дерево і хорда u цього дерева, у графі G існує єдиний цикл, який має хорду u і не має інших хорд.
Д о в е д е н н я.
Нехай u = {a, b}. У дереві T є єдиний ланцюг, який з’єднує вершини a та b.
Долучаючи до цього ланцюга ребро u, здобуваємо потрібний цикл.

лісу: граф G, усі компоненти зв’язності якого є деревами, називається

лісом.

Граф G

(один з яких корінь), та відношень („батьківських”), що утворюють ієрархічну

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

Піддерево, корінь якого знаходиться в лівому (правому) нащадку вершини, називається лівим (правим) піддеревом цієї вершини.

цього вузла до будь-якого листа.
Висота дерева співпадає з висотою

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

рівнях менше чим n вузли мають степінь 2, а на

рівні n – степінь 0.

а) неповне бінарне дерево

б) повне бінарне дерево

2 або 0.
Нестрого бінарне дерево містить вузли зі степенем

1.

а) строго
бінарне дерево

б) нестрого
бінарне дерево

зображені:
1) Електричні і транспортні мережі;
2) Карти автомобільних, залізничних та повітряних

шляхів;

і комп'ютерні мережі;
7) Ієрархічна структура книг;

можливість переливання крові:
9) Лабіринти;
10) Різні математичні об'єкти (відношення, алгоритми, програми

тощо)

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

(електромереж, телефонних, залізничних ліній).
Теорія ігор, головоломки.
Комунальне господарство, планування.
Складання розкладу.
Проектування комп'ютерних мереж.