Графы и сети. Харитонова Е.В. - 19 стр.

UptoLike

Составители:

Рубрика:

● Гамильтонов цикл – это простой цикл, который проходит через каждую

вершину графа G.

Легко убедиться, что граф для игры Гамильтона действительно имеет га-

мильтонов цикл. Один из таких циклов изображен на рис. 1.39.

Пример. Граф на рис. 1.40 имеет гамильтонов цикл, изображенный на рис. 1.41.

Рис. 1.40 Рис. 1.41

ТЕОРЕМА 1.11. Для любой вершины из цикла Гамильтона существует

ровно два ребра из этого цикла, инцидентные данной вершине.

Доказательство. По ходу цикла для каждой вершины V имеется ребро к

циклу и ребро из цикла. Если бы существовало еще одно ребро цикла инци-

дентное вершине V, то цикл вернулся бы в вершину

V, и она опять появилась

бы в цикле, что противоречит определению гамильтонова цикла. Следователь-

но, существует ровно два ребра, которые инцидентны вершине V из цикла Га-

мильтона.

Заметим, что граф, у которого есть гамильтонов цикл, называют гамиль-

тоновым графом.

Пример. Граф Петерсена, изображенный на рис. 1.42 имеет гамильтонов путь, но не

имеет гамильтонова цикла. Путь показан на рис. 1.43.

Рис. 1.42 Рис. 1.43

ТЕОРЕМА 1.12. Если G = G(V, E) – связный граф с n вершинами, где n ≥

3, и для каждой пары различных несмежных вершин u, υ

∈

V, deg(u) + deg(υ) ≥

n, тогда граф G имеет гамильтонов цикл.

d ƒ

е j ƒ g b

d c

e b

i h

d c

j g