Алгоритм Havel-Хакой алгоритм в теории графов решения проблемы реализации графа . То есть он отвечает на следующий вопрос: существует ли конечный список неотрицательных целых чисел в невозрастающем порядке, существует ли простой граф , последовательность степеней которого является точно этим списком? Простой граф не содержит двойных ребер или петель. [1] Последовательность степеней - это список чисел в невозрастающем порядке, указывающий количество ребер, инцидентных каждой вершине в графе. [2] Если простой граф существует точно для данной последовательности степеней, список целых чисел называетсяграфический . Алгоритм Гавела-Хакими строит специальное решение, если существует простой граф для данной последовательности степеней, или доказывает, что нельзя найти положительный ответ. Эта конструкция основана на рекурсивном алгоритме . Алгоритм был опубликован Гавелом (1955) , а затем Хакими (1962) .
Алгоритм
Алгоритм Хавела-Хакими основан на следующей теореме.
Позволять конечный список неотрицательных целых чисел, который не увеличивается . Позволять- второй конечный список неотрицательных целых чисел, переставленный в невозрастающий. Список является графическим тогда и только тогда, когда список графический.
Если данный список наглядно, то теорема будет применяться не более чем установка времени на каждом последующем шаге . Обратите внимание, что может потребоваться снова отсортировать этот список. Этот процесс заканчивается, когда весь списоксостоит из нулей. Позволять - простой граф с последовательностью степеней : Пусть вершина иметь степень ; пусть вершины иметь соответствующие степени ; пусть вершины иметь соответствующие степени . На каждом шаге алгоритма строятся ребра графа с вершинами—Т.е, если можно сократить список к , затем добавляем ребра . Когда список не может быть сведен к списку неотрицательных целых чисел на любом этапе этого подхода, теорема доказывает, что список с самого начала не является графическим.
Доказательство
Ниже приводится краткое изложение, основанное на доказательстве алгоритма Хавела-Хакими в Приглашении к комбинаторике (Шахриари 2022).
Чтобы доказать, что алгоритм Гавела-Хакими всегда работает, предположим, что является графическим, и существует простой граф с порядком степеней . Затем добавляем новую вершину рядом с вершины со степенями чтобы получить последовательность степеней .
Чтобы доказать обратное, предположим, что является графическим, и существует простой граф с порядком степеней и вершины . Мы не знаем, какие вершины смежны с , так что у нас есть два возможных случая.
В первом случае примыкает к вершинам в . В этом случае мы удаляем со всеми его инцидентными ребрами, чтобы получить последовательность степеней .
Во втором случае не смежна с некоторой вершиной для некоторых в . Тогда мы можем изменить график чтобы примыкает к при сохранении той же последовательности степеней . С имеет степень , вершина должен быть смежным с некоторой вершиной в для : Пусть степень быть . Мы знаем, как последовательность степеней находится в невозрастающем порядке.
С , у нас есть две возможности: Либо , или же . Если, затем, поменяв местами вершины а также , мы можем настроить чтобы примыкает к вместо Если , то поскольку примыкает к большему количеству вершин, чем , пусть другая вершина быть рядом с и нет . Тогда мы можем настроить убрав края а также и добавляем края а также . Эта модификация сохраняет последовательность степеней, но вершина теперь рядом с вместо . Таким образом, любая вершина, не связанная с можно отрегулировать соответствующим образом, чтобы примыкает к при сохранении исходной последовательности степеней из . Таким образом, любая вершина, не связанная с может быть подключен к используя описанный выше метод, и тогда мы снова имеем первый случай, с помощью которого мы можем получить последовательность степеней . Следовательно, является графическим тогда и только тогда, когда также является графическим.
Временная сложность алгоритма является.
Примеры
Позволять - невозрастающая последовательность неотрицательных целых чисел конечной степени. Чтобы проверить, является ли эта последовательность степеней графической, мы применяем алгоритм Гавела-Хакими:
Сначала мы удаляем вершину с наивысшей степенью - в данном случае - и все его грани, чтобы получить (предполагая, что вершина с наивысшей степенью смежна с вершины со следующей высшей степенью). Переставим эту последовательность в порядке невозрастания, чтобы получить. Мы повторяем процесс, удаляя вершину со следующей высшей степенью, чтобы получить и переставляя, чтобы получить . Мы продолжаем это удаление, чтобы получить, а потом . Эта последовательность наглядно наглядна, поскольку представляет собой простой график изолированные вершины.
Чтобы показать пример неграфической последовательности, пусть - невозрастающая последовательность неотрицательных целых чисел конечной степени. Применяя алгоритм, сначала убираем степень вершину и все ее инцидентные ребра, чтобы получить . Мы уже знаем, что эта последовательность степеней не является графической, поскольку она утверждает, что имеетвершины, у которых одна вершина не смежна ни с одной из других вершин; таким образом, максимальная степень остальных вершин равна. Это означает, что две вершины соединены со всеми остальными вершинами, за исключением изолированной, поэтому минимальная степень каждой вершины должна быть; однако последовательность утверждает, что имеет вершину со степенью. Таким образом, последовательность не является графической.
Ради алгоритма, если бы мы повторили процесс, мы бы получили что еще более явно не является графическим. Одна вершина утверждает, что имеет степень, и все же только две другие вершины имеют соседей. Таким образом, последовательность не может быть графической.
Смотрите также
Заметки
- ^ Из Шахриари (2022, стр. 48): « Определение 2.17 (Графы и подграфы). Простой граф (или просто граф ) G - это пара множеств ( V, E ), где V - непустое множество, называемое множеством вершины из G и Е является (возможнопустым) множеством неупорядоченных пар различных элементов V . множество Е называется множество ребер из G . Если число вершин G конечно, то G является конечным графом (или конечный простой граф ) ".
- ^ Из Шахриари (2022, стр. 355): « Определение 10.6 (Последовательность степеней графа; Графические последовательности). Последовательность степеней графа - это список степеней его вершин в невозрастающем порядке. возрастающая последовательность неотрицательных целых чисел называется графической , если существует простой граф, последовательность степеней которого в точности совпадает с этой последовательностью ».
Рекомендации
- Гавел, Вацлав (1955), «Замечание о существовании конечных графов» , Časopis pro pěstování matematiky (на чешском языке), 80 : 477–480
- Хакими, С.Л. (1962), «О реализуемости набора целых чисел как степеней вершин линейного графа. I», Журнал Общества промышленной и прикладной математики , 10 : 496–506, MR 0148049.
- Шахриари, Шахриар (2022), Приглашение к комбинаторике, Cambridge U. Press.
- Уэст, Дуглас Б. (2001). Введение в теорию графов. Второе издание. Прентис Холл, 2001. 45-46.