Открыть главное меню

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

Алгоритм предложен Вацловом Гавелом[cs] в 1955 и переоткрыт Луисом Хакими[en] в 1962.

Содержание

АлгоритмПравить

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

Пусть   есть конечный список неотрицательных целых чисел в невозрастающем порядке. Список   является графическим, тогда, и только тогда, когда список   графический.

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

ПримерыПравить

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

См. такжеПравить

ReferencesПравить