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

Материал из Викиконспекты
Перейти к: навигация, поиск

Основные определения

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


Определение:
Гамильтоновым циклом называют замнутый гамильтонов путь.


Определение:
Граф называется гамильтоновым, если он содержит гамильтонов цикл.

Достаточные условия гамильтоновости графа

Теорема Дирака

Теорема:
Если [math]n \ge 3[/math] и [math]deg\ v \ge n/2[/math] для любой вершины [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] - гамильтонов граф.

Теорема Оре

Теорема:
Если [math]n \ge 3[/math] и [math]deg\ u + deg\ v \ge n[/math] для любых двух различных несмежных вершин [math]u[/math] и [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] - гамильтонов граф.

Теорема Редеи-Камиона

Теорема:
Любой сильносвязный турнир - гамильтонов.

Теорема Гуйя-Ури

Теорема:
Пусть G - сильносвязный ориентированный граф.
[math] \begin{matrix} deg^+ v \geq n/2 \\ deg^- v \geq n/2 \\ \end{matrix} \Bigg\} \Rightarrow [/math] G - гамильтонов.


Теорема Хватала

Теорема (Хватал):
Пусть:
  • [math] G [/math]связный граф,
  • [math] n = |VG| \geq 3 [/math] — количество вершин,
  • [math] d_1 \leq d_2 \leq \ldots \leq d_n [/math] — его последовательность степеней.

Тогда если [math] \forall k \in \mathbb N [/math] верна импликация:

[math] d_k \leq k \lt n/2 \rightarrow d_{n - k} \geq n - k, (*) [/math]
то граф [math] G [/math] гамильтонов.

Теорема Поша

Теорема:
Пусть граф G имеет [math]p \geq 3[/math] вершин. Если для всякого [math]n,\, 1 \leq n \lt (p-1)/2[/math] число вершин состепенями, не превосходящими [math]n[/math], меньше чем [math]n[/math], и для нечетного [math]p[/math] число вершин степени [math](p-1)/2[/math] не превосходит [math](p-1)/2[/math], то G - гамильтонов граф