Дискретная математика. Громов Ю.Ю - 73 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

73
Рис. 38
Например, на рис. 37, а, б и в изобра-
жены соответственно негамильтонов, по-
лугамильтонов и гамильтонов графы.
Название «гамильтонов цикл» воз-
никло в связи с тем, что ирландский мате-
матик и астроном Уильям Гамильтон
(1805 − 1865) занимался исследованием
существования таких циклов в графе, соот-
ветствующем додекаэдру (правильному
двенадцатиграннику).
Этот граф, изображённый на рис. 38,
является гамильтоновым графом. В нём
рёбра, принадлежащие гамильтонову циклу, показаны сплошными ли-
ниями.
Отметим, что необходимое и достаточное условие гамильтоновости
графа до сих пор не получено. Поиск такого критерия остаётся одной из
главных нерешённых задач теории графов. Разработаны лишь достаточ-
ные условия, одно из которых сформулировал Габриэль Дирак (1925 –
1984).
Теорема (Дирака). Если в связном графе G, имеющем n
≥
3 вершин,
степень каждой вершины больше или равна
2n
, то граф G является
гамильтоновым графом. ■
Например, гамильтонов граф на рис. 37, в имеет четыре вершины и
степень каждой из них не меньше чем два. Заметим, что граф на рис. 38
тоже гамильтонов, хотя он имеет двадцать вершин, а степень каждой
вершины равна трём.
Задачи и упражнения
1. Для каких значений m и n следующие графы являются эйлеро-
выми графами:
а) полный граф F
n
;
б) полный двудольный граф K
m, n
;
в) колесо W
n
(n
≥
3).
2. Найдите (с помощью алгоритма Флёри) эйлеров цикл в заданном
эйлеровом графе, а также разбиение его рёбер на простые циклы.
3. Для каких значений m и n следующие графы являются гамильто-
новыми:
а) полный граф F
n
;
б) полный двудольный граф K
m, n
;
в) колесо W
n
(n
≥
3).

Страницы