Page 302 - 6197

Простий цикл, який вміщує всі вершини графа насить
назву гамільтоновий цикл.
Приклад Д3.4. Простий цикл графа (рис. Д3.5)
V VV V V V V V V , який вміщує всі вершини, є гамільтоновим
0 1 2 5 7 6 4 3 0
циклом.
Каркасним підграфом G графа G називається граф
p
G V ,E  , для якого E  E . Таким чином, число вершин
p p p
каркасного графа G співпадає з числом вершин графа G , але
p
множина ребер графа G є підмножиною множини E .
p
На рис. Д3.7 зображений каркасний граф G , який є
p
підграфом графа G (рис. Д3.5). Як неважко переконатись
число вершин графа G - n  , що співпадає з числом
7
p
вершин графа G , а число ребер графа G - m  . Тоді як
7
p p
число ребер графа G m  10.

Рисунок Д3.7 – Каркасний граф G
p
Термін дерево можна визначати одним із трьох способів:
 зв’язаний граф, що має n вершин і n  1 ребер;
 зв’язаний граф, що не має циклів;
 граф, у якому пара вершин з’єднана одним і тільки
одним простим шляхом.

302