67. Поняття дерева.

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

Для довільного графа G = (V, Е) з n вершинами та m ребрами наступні твердження є рівносильні: 1)граф G – дерево. 2) G – зв’язний граф та m = n-1; 3) 2) G – ациклічний граф; m = n-1.

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

68. Цикломатичне число графа.

Нехай граф G має k компонент зв’язності. Це число – цикломатичне число графа.

Цикломатичне число характеризує к-ть ребер, які необхідно вилучити з графа, щоб отримати його кістяковий ліс. цикломатичне число є додатнім. цикломатичне число дерева = 0.

69. Кістякове дерево зв’язного графа.

див. пит. 67

70. Алгоритм Крускала

1) вибрати в графі G ребро мінімальної ваги. Присвоїти і=2.

2)якщо і= n, то закінччуємо роботу алгоритму. В іншому випадку:

3)побудувати граф G', додаючи до отриманого на попередньому етапі графа ребро мін. довжини, обране серед множини ребер, кожне з яких інцидентне якій-небудь вершині графа G, але яке не міститься в графі G'. і=і+1, і переходимо до кроку 2.

71. Поняття Ейлерових графів.

Цикл, який містить всі ребра графа, назив Ейлеровим. Ейлеровим ланцюгом назив. ланцюг, що проходить через всі ребра графа. Граф ейлерів, якщо:

1)G – ейлерів граф

2)кожна вершина має парний степінь.

3) множину ребер графа можна розбити на прості цикли, які не перетинаються по ребрах. Цикли, що містять усі ребра графа, називаються ейлеревими, а графи, які мають цей цикл – ейлеревими. Іншими словами Ейлерові графи – це такі графи, які можна зобразити одним розчерком пера, причому процес цього починається й закінчується в одній і тій самій вершині. Ейлер розв’язав поставлену задачу і сформулював теорему Ейлера: скінчений неорієнтований граф G є ейлеревим тоді й тільки тоді, коли він зв’язний і степені всіх його вершин парні.

73. Поняття гамільтонових графів.

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

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

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

75. Поняття укладання графа. Пласкі та планарні графи.

Див. на листку А4.

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