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

Определение 1. Гамильтоновым путем в графе называется путь, проходящий через каждую вершину графа в точности по одному разу.

Пример 1. Рассмотрим граф

Он имеет гамильтоновы пути (x₃, x₄, x₅, x₁, x₂) и (x₃, x₄, x₂, x₅, x₁).

Определение 2. Гамильтоновым циклом в графе называется цикл, проходящий через каждую вершину графа в точности по одному разу.

Определение 3. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Пример 2. Рассмотрим граф

Данный граф является гамильтоновым, так как он имеет гамильтоновы циклы (x₁, x₇, x₆, x₃, x₄, x₅, x₂, x₁) и (x₁, x₆, x₃, x₄, x₅, x₂, x₇, x₁).

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

Теорема. Граф с m вершинами имеет гамильтонов цикл, если для любой его вершины A_i степень (A_i) ³ m/2.