Алгоритм Гавела — Хакими — рекурсивный алгоритм позволяющий определить появляется ли данный список целых чисел как список всех валентностей некоторого конечного простого графа. При положительном ответе на этот вопрос список называется графическим.
Алгоритм предложен в 1955 и переоткрыт в 1962.
Алгоритм Алгоритм основан на следующей теореме.
Пусть есть конечный список неотрицательных целых чисел в невозрастающем порядке. Список является графическим, тогда, и только тогда, когда список графический.
Описанную операцию следует применять поочерёдно с упорядочиванием списка. Если в какой-то момент получаем список из нулей то изначальный список являлся графическим. Если же в списке появится отрицательное число то изначальный список не являлся графическим.
Примеры
Применим алгоритм к списку . Мы поочерёдно применяем теорему и упорядочивание. То что в результате получается список из нулей означает, что список графический.
Применим алгоритма к списку . То что в результате получается список из отрицательных чисел означает, что список не является графическим.
См. также Теорема Эрдёша — Галлаи
Примечания
.
Категория:Алгоритмы на графах