Page 48 - 4386

Рисунок 4.5 – Один з варіантів рішення головоломки Гамільтона

Наведемо ряд тверджень, що дозволяють судити про

можливість відшукати гамільтоновий цикл у досліджуваному

графі.

1. Для будь-якої вершини із циклу Гамільтона існує рівно

два ребра із цього циклу, інцидентні даній вершині. Таким чином,

будь-який граф, що має вершину степеня 1, не є гамільтоновим.

Слід також зазначити, що для того, щоб граф мав цикл

Гамільтона, необхідно, щоб він був зв'язним.

2. Якщо граф G має ребро розрізу, то він не може мати цикл

Гамільтона. Якщо компоненти графа, отримані шляхом

видалення ребра розрізу, мають цикл Гамільтона, то граф G має

шлях Гамільтона.

3. Теорема Оре. Якщо G - зв'язний граф з n вершинами (n≥3)

і для кожної пари несуміжних вершин v, w∈V, сума степенів

вершин задовольняє умову δ(v)+δ(w)≥n, то граф G має цикл

Гамільтона.

4. Теорема Дирака (випливає з теореми Оре). Якщо

G - зв'язний граф з n вершинами (n≥3) і для кожної вершини v∈V

виконується умова δ(v)≥n/2, то граф G має цикл Гамільтона.
(2)
Очевидно, що в довільному повному графі K =(V, V ),
n
V={v , v , …, v }, n≥3 існує гамільтоновий цикл v v …v v . Для
1 2
n 1
2
1
n
47