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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм нахождения гамильтового цикла)
Строка 105: Строка 105:
 
   '''return''' false
 
   '''return''' false
  
* used отметки о посещении
+
* used {{---}} отметки о посещении
* vert текущая вершина
+
* vert {{---}} текущая вершина
* count количество посещённых вершин  
+
* count {{---}} количество посещённых вершин  
  
 
Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле. Этот алгоритм в худшем случае перебирает <tex>(n - 1)!</tex> путей, что даёт сложность работы <tex>O(n!)</tex>.
 
Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле. Этот алгоритм в худшем случае перебирает <tex>(n - 1)!</tex> путей, что даёт сложность работы <tex>O(n!)</tex>.

Версия 03:17, 30 декабря 2015

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

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

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


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


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


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


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

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

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

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

Теорема Оре

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

Теорема Поша

Теорема (Поша):
Пусть граф [math] G [/math] имеет [math]n \geqslant 3[/math] вершин и выполнены следующие два условия:
  • для всякого [math]k,\, 1 \leqslant 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],
тогда [math] G [/math] — гамильтонов граф.

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

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

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

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

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

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

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

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

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

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

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 to g.vertices
    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 будет храниться следующая вершина на гамильтоновом цикле. Этот алгоритм в худшем случае перебирает [math](n - 1)![/math] путей, что даёт сложность работы [math]O(n!)[/math].

Приведём алгоритм, основанный на динамическом программировании, который работает значительно быстрее. Алгоритм основан на следующей идее: будем для каждой пары из подмножества вершин и вершины считать, существует ли гамильтонов путь для этого подмножества вершин, заканчивающихся в выделенной вершине. Суммарно таких состояний будет [math]O(n2^n)[/math], для обсчёта каждого из них требуется [math]O(n)[/math] времени, то есть, суммарно алгоритм работает за [math]O(n^22^n)[/math] времени. Псевдокод, реализующий этот алгоритм, приведён ниже:

bool[][] get_dp_table(graph g):
  int n = g.vertices
  bool[][] result = new int[1 << n][n]
  for  i = 0 to n
    result[1 << i][i] = (0; i) in g.edges;
  for  i = 1 to 1 << n
    if (count(i) == 1)
      continue
    for  j = 0 to n
      if ((1 << j) & i != 0)
        for k = 0 to n
          if (k != j && (1 << k) & i != 0)
            result[i][j] = result[(1 << j) ^ i][k] && (k; j) in g.edges
  return result

В приведённом выше коде считаем, что n меньше количества бит в числовом типе данных, для операций над множествами используются побитовые логические операции в синтаксисе языка C. Функция count считает количество единичных бит в числе (она проста в реализации, но не относится к алгоритма, поэтому не приводится). Граф гамильтонов тогда, когда dp[(1 << n) - 1][i] && (i; 0) [math]\in[/math] g.edges для некоторого i.

Источники

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