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

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

Алгоритм предложен Вацловом Гавелом в 1955 и переоткрыт Луисом Хакими в 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{matrix}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{matrix}}$

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

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

См. также

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

Примечания

• Havel, Václav (1955), "POZNÁMKA O EXISTENCI KONEČNÝCH GRAFŮ", Časopis pro pěstování matematiky, 80: 477—480
• Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10: 496—506.