Алгоритм Гавела — Хакими для проверки что список называется графическим кратко

Привет, Вы узнаете о том , что такое алгоритм гавела-хакими, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое алгоритм гавела-хакими , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

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

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

Алгоритм

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

Пусть есть конечный список неотрицательных целых чисел в невозрастающем порядке. Об этом говорит сайт https://intellect.icu . Список является графическим, тогда, и только тогда, когда список графический.

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

Примеры

Граф со списком валентностей 4,4,3,3,2,2,1,1.

• Применим алгоритм к списку . Мы поочередно применяем теорему и упорядочивание. То что в результате получается список из нулей означает, что список графический.

  

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

  

Вау!! 😲 Ты еще не читал? Это зря!

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

Исследование, описанное в статье про алгоритм гавела-хакими, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое алгоритм гавела-хакими и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.