Гамильтоновы графы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Хватала)
(Алгорит нахождения гамильтового цикла)
Строка 81: Строка 81:
 
}}
 
}}
  
==Алгорит нахождения гамильтового цикла==
+
==Алгоритм нахождения гамильтового цикла==
Основан на [[Обход в глубину, цвета вершин|обходе в глубину]].
+
 
===Псевдокод===
+
Приведём два алгоритма поиска гамильтонова цикла.
  search_cycle(0, 0, number_of_vertices);
+
 
bool search_cycle(int v, int w, int d)
+
  bool check_hamiltonian(graph g, bool[] used, int vert, int count, int[] next):
{
+
  if (count == g.vertices):
    if(w == v)
+
    next[vert] = 0
      return (d == 0);
+
    return (vert; 0) in g.edges
    visited[v] = true;
+
  for (i = 0; i < g.vertices; i++):
    for (t <tex>\in</tex> Adj[v])
+
    if (!used[i] && (vert; i) in g.edges):
       if(!visited[t])
+
      used[i] = true
          if(search_cycle(t, w, d - 1))
+
       next[vert] = i
            return true;
+
      if (check_hamiltonian(g, used, i, count + 1, next)):
    visited[v] = false;
+
        return true
    return false;
+
      used[i] = false
}
+
  return false
 +
 
 +
* used — отметки о посещении
 +
* vert — текущая вершина
 +
* count — количество посещённых вершин
 +
 
 +
Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле.
  
 
==Источники==
 
==Источники==

Версия 23:30, 17 января 2012

Граф додекаэдра с выделенным циклом Гамильтона

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

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


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


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


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


Очевидно, что любой гамильтонов граф также и полугамильтонов.

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

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

Теорема:
Если [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]n \geq 3[/math] вершин. Если для всякого [math]k,\, 1 \leq k \lt (n-1)/2[/math] число вершин со степенями, не превосходящими [math]k[/math], меньше чем [math]k[/math], и для нечетного [math]n[/math] число вершин степени [math](n-1)/2[/math] не превосходит [math](n-1)/2[/math], то G - гамильтонов граф.

Алгоритм нахождения гамильтового цикла

Приведём два алгоритма поиска гамильтонова цикла.

bool check_hamiltonian(graph g, bool[] used, int vert, int count, int[] next):
  if (count == g.vertices):
    next[vert] = 0
    return (vert; 0) in g.edges
  for (i = 0; i < g.vertices; i++):
    if (!used[i] && (vert; i) in g.edges):
      used[i] = true
      next[vert] = i
      if (check_hamiltonian(g, used, i, count + 1, next)):
        return true
      used[i] = false
  return false
  • used — отметки о посещении
  • vert — текущая вершина
  • count — количество посещённых вершин

Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле.

Источники

  • Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
  • Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
  • Гамильтонов граф