Алгоритм Гавела — Хакими

Алгоритм Гавела — Хакими — рекурсивный алгоритм позволяющий определить появляется ли данный список целых чисел как список всех валентностей некоторого конечного простого графа. При положительном ответе на этот вопрос список называется графическим.

Алгоритм предложен Шаблон:Iw в 1955 и переоткрыт Шаблон:Iw в 1962.

Алгоритм

Алгоритм основан на следующей теореме.

Пусть $s,d_1,\dots ,d_s,t_1,\dots ,t_k$ есть конечный список неотрицательных целых чисел в невозрастающем порядке. Список $s,d_1,\dots ,d_s,t_1,\dots ,t_k$ является графическим, тогда, и только тогда, когда список $d_1-1,\dots ,d_s-1,t_1,\dots ,t_k$ графический.

Описанную операцию следует применять поочерёдно с упорядочиванием списка. Если в какой-то момент получаем список из нулей то изначальный список являлся графическим. Если же в списке появится отрицательное число то изначальный список не являлся графическим.

Примеры

Граф со списком валентностей 4,4,3,3,2,2,1,1.

• Применим алгоритм к списку $4,4,3,3,2,2,1,1$. Мы поочерёдно применяем теорему и упорядочивание. То что в результате получается список из нулей означает, что список $4,4,3,3,2,2,1,1$ графический.

  $\begin{array}{cccccccc}4& 4& 3& 3& 2& 2& 1& 1\\ & 3& 2& 2& 1& 2& 1& 1\\ & 3& 2& 2& 2& 1& 1& 1\\ & & 1& 1& 1& 1& 1& 1\\ & & 1& 1& 1& 1& 1& 1\\ & & & 0& 1& 1& 1& 1\\ & & & 1& 1& 1& 1& 0\\ & & & & 0& 1& 1& 0\\ & & & & 1& 1& 0& 0\\ & & & & & 0& 0& 0\end{array}$

• Применим алгоритма к списку $7,6,3,3,2,2,1,1$. То что в результате получается список из отрицательных чисел означает, что список $7,6,3,3,2,2,1,1$ не является графическим.

  $\begin{array}{cccccccc}7& 6& 3& 3& 2& 2& 1& 1\\ & 5& 2& 2& 1& 1& 0& 0\\ & & 1& 1& 0& 0& -1& 0\end{array}$

См. также

• Теорема Эрдёша — Галлаи

Примечания

• Шаблон:Citation
• Шаблон:Citation.