Гамильтоновы графы

В средине 19 века ирландский математик Уильям Гамильтон опубликовал задачу о «кругосветном путешествии». Требуется обойти все вершины графа (столицы государств) по одному разу и вернуться в исходную вершину.

.

Рис. 65. Задача о «кругосветном путешествии»

Если граф имеет простой цикл, содержащий все вершины графа, то этот цикл называется гамильтоновым циклом, а сам граф называется гамильтоновым графом.

Гамильтонов цикл не обязательно содержит все ребра графа. Совершенно очевидно, что гамильтоновы графы являются связными.

Решение задачи о «кругосветном путешествии».

Находясь в любой вершине, мы можем повернуть вправо (П) или влево (Л). Условимся вместо ПП писать П ² и т.д. Тогда решение может быть задано формулой

(Л³ П³ (ЛП)²)² = ЛЛЛ ППП ЛП ЛП ЛЛЛ ППП ЛП ЛП.

Решение не единственно. Можно начинать в обратном порядке. Можно сделать круговую перестановку.

Дата добавления: 2014-01-06