2015-04-01
1036
Определение 1. Гамильтоновым путем в графе называется путь, проходящий через каждую вершину графа в точности по одному разу.
Пример 1. Рассмотрим граф
Он имеет гамильтоновы пути (x 3, x 4, x 5, x 1, x 2) и (x 3, x 4, x 2, x 5, x 1).
Определение 2. Гамильтоновым циклом в графе называется цикл, проходящий через каждую вершину графа в точности по одному разу.
Определение 3. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.
Пример 2. Рассмотрим граф
Данный граф является гамильтоновым, так как он имеет гамильтоновы циклы (x 1, x 7, x 6, x 3, x 4, x 5, x 2, x 1) и (x 1, x 6, x 3, x 4, x 5, x 2, x 7, x 1).
Всякий полный граф является гамильтоновым, так как он содержит такой простой цикл, которому принадлежат все вершины графа.
Теорема. Граф с m вершинами имеет гамильтонов цикл, если для любой его вершины Ai степень (A i) > m /2.
