Алгоритм Гавела — Хакими — рекурсивный алгоритм позволяющий определить появляется ли данный список целых чисел как список всех валентностей некоторого конечного простого графа. При положительном ответе на этот вопрос список называется графическим.
Алгоритм предложен Вацловом Гавелом[чеш.] в 1955 и переоткрыт Луисом Хакими[англ.] в 1962.
Алгоритм основан на следующей теореме.
Пусть s , d 1 , … , d s , t 1 , … , t k {\displaystyle s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k}} есть конечный список неотрицательных целых чисел в невозрастающем порядке. Список s , d 1 , … , d s , t 1 , … , t k {\displaystyle s,d_{1},\dots ,d_{s},t_{1},\dots ,t_{k}} является графическим, тогда, и только тогда, когда список d 1 − 1 , … , d s − 1 , t 1 , … , t k {\displaystyle d_{1}-1,\dots ,d_{s}-1,t_{1},\dots ,t_{k}} графический.
Описанную операцию следует применять поочерёдно с упорядочиванием списка. Если в какой-то момент получаем список из нулей то изначальный список являлся графическим. Если же в списке появится отрицательное число то изначальный список не являлся графическим.