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

Алгоритм предложен в 1955 и переоткрыт в 1962.

Алгоритм

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

Пусть ${\displaystyle s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k}}$ есть конечный список неотрицательных целых чисел в невозрастающем порядке. Список ${\displaystyle s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k}}$ является графическим, тогда, и только тогда, когда список ${\displaystyle d_{1}-1,\dots ,d_{s}-1,t_{1},\dots ,t_{k}}$ графический.

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

Примеры

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

  ${\displaystyle {\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}}}$

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

  ${\displaystyle {\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}}}$

См. также

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

Примечания

• (1955), , Časopis pro pěstování matematiky , 80 : 477—480
• (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the , 10 : 496—506 .