Havel-Hakimi алгоритм для графов с кратными ребрами

[denny]

Разбираюсь с этим вопросом.
Суть такова: дан список порядков вершин графа, надо убедиться, можно ли построить связный граф, возможно с кратными ребрами.
Мне не нравится, что все там стали копипастить одну и ту же теорему.
Хочется пощупать, как это все работает, и собственно попытаться построить примеры графов!

Изучил вот эту статью, там ближе к концу есть замечательная подсказка:
можно организовать алгоритм Havel-Hakimi так, что он выдаст обязательно связный граф, если это возможно. А если невозможно, в определенный момент это станет понятно и можно выдать False.
Это то, что нужно, но как изменить алгоритм, чтобы он включал возможные multiedge графы? Ясно, что можно вычитать не 1, а другие числа каждую итерацию, но как их подобрать?

[mihaild]

Скорее всего никак (кроме как взять уже совсем другой алгоритм), потому что проблема для мультиграфа гораздо проще, чем для графа, плюс тут Вы требуете связности. Для Вашей постановки, если мы добавляем ребра по одному и уже добавили достаточно, чтобы гарантировать связность, оставшиеся можно добавлять вообще как угодно, и ничего не сломается. В варианте с графом же очень легко добавить несколько ребер так, что продолжить не получится, хотя изначальная проблема решение имела.

[denny]

mihaild в сообщении #1585739 писал(а):

Скорее если мы добавляем ребра по одному и уже добавили достаточно, чтобы гарантировать связность, оставшиеся можно добавлять вообще как угодно, и ничего не сломается.

Да, когда я это понял, то обрадовался, но проблема с теми списками, где представленный алгоритм сразу останавливается. Самое простое "молекула азота" с degrees [3, 3].
И если ситуация для мультиграфа "проще" (в чем как-то не уверен), то конечно можно самому переписать алгоритм, но не получается, даже для простейших случаев (

-- 17.03.2023, 14:22 --

Кажется вот здесь есть ответ

[mihaild]

denny в сообщении #1585742 писал(а):

где представленный алгоритм сразу останавливается

Представленный - это Гавела-Хакими? Ну да, он для графов, не для мультиграфов.

denny в сообщении #1585742 писал(а):

то конечно можно самому переписать алгоритм, но не получается, даже для простейших случаев

А чем Вас не устраивает метод по Вашей ссылке на stackexchange?

denny в сообщении #1585742 писал(а):

Кажется вот здесь
есть ответ

Кажется для такой задачи это слишком сложно.

Я не очень понимаю - Вы хотите именно модифицировать Гавела-Хакими, или просто найти мультиграф хоть как?

(Оффтоп)

ИМХО ссылки на архив гораздо лучше давать на страницу статьи, а не на pdf - прямое преобразование гораздо проще обратного в данном случае.

[denny]

На codegolf стоило одному найти теорему, где указан простой численный критерий возможности построения мультиграфа, так все ее только и копируют. Мне бы хотелось найти не только критерий, но само построение (которое в процессе может выдать негативный ответ).

Да, достаточно построить хоть какой-то мультиграф или получить отрицательный ответ.

Почему сложно, сейчас пробую написать простенькую программку по этому алгоритму, думаю это, что нужно:

Theorem 7 (connected loopless multigraph construction). Let $d$ be a multigraphical
degree sequence, and let us repeatedly select the largest remaining degree vertex and
the smallest non-zero remaining degree vertex, and connect them with a single edge.
This construction procedure results in a connected graph if and only if $d$ was potentially
connected.

[denny]

Итак, получается следующая картина.

Задача. Дан список порядков вершин предполагаемого графа, надо:

• Убедиться, что существует "химическая формула" для такого списка, т.е. связный мультиграф.
• Если существует, построить любой пример.

На первый вопрос можно ответить численно, проверив следующие критерии:

• Сумма порядков является четной
• Полусумма порядков больше или равна числу вершин, уменьшенному на $1$
• Наибольший порядок меньше или равен сумме остальных порядков

Мне было интересно попытаться построить сам граф, да и вопрос существования решить не численным, а алгоритмическим путем.
В данной статье приведены необходимые алгоритмы, которые я реализовал на Wolfram Mathematica.

Краткое описание:

1. Произвольным образом привязываем к каждому порядку номер вершины (вложенный список, словарь и т.д.)
2. Сортируем порядки по убыванию
3. Выбираем (один из) наибольших и (один из) наименьших
4. Уменьшаем каждый из них на 1 и добавляем ребро, соединяющее соответствующие вершины
5. Удаляем порядки равные 0. Если (в одной из итераций) оба порядка стали нулевыми,
   значит полученный мультиграф будет несвязным. Мы можем продолжить его построение,
   либо сразу сделать останов с сообщением Non connected
6. Если остался один ненулевой элемент, значит граф (даже несвязный!) построить нельзя.
   Останов с сообщением None
7. Если осталось пустое множество, мы достигли результата, либо продолжаем итерации с п.2

Данный алгоритм строит один из возможных графов. Например, для списка порядков
$[3,3,3,3]$ получается следующий простой, но непланарный граф:

хотя предполагается что это должна быть "молекула тетразета":


Но химическое соединение может быть непланарным, поэтому свою задачу алгоритм выполняет.
И еще пример результата работы алгоритма:
Список порядков: $[5, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1]$
Граф:

[mihaild]

denny, да, всё правильно. Вопрос, как по степеням вершин эффективно определить, существует ли планарный граф с такими степенями, вроде бы открыт. Для мультиграфа это может быть проще, но сходу ничего найти не удалось.

mihaild в сообщении #1585739 писал(а):

оставшиеся можно добавлять вообще как угодно, и ничего не сломается

Тут я, кстати, проврался немного. Если петли запрещены, то даже с мультиграфом можно всё сломать. Например если с графом $(4, 2, 2)$ добавить ребро между двумя двойками.

[denny]

mihaild, спасибо за внимание к вопросу!
Ну, планарность (пока) не рассматриваем. То есть, непланарные графы принимаются,
как вполне возможные химические соединения.
А насчет петель не очень понял. Я, к сожалению, занимаюсь графами на уровне интуиции.
Если это self-loop, т.е. замыкание вершины на себя, то безусловно запрещено.
Философски атом, конечно, связан сам с собой но мы такое не учитываем.
А вот любые петли по графу разрешены, и таких молекул полно!

[Geen]

denny в сообщении #1585765 писал(а):

хотя предполагается что это должна быть "молекула тетразета"

алгоритм тяготеет к простым связям (а 4 азота вкучку - выглядит немного как перебор)

[svv]

denny в сообщении #1585765 писал(а):

простой, но непланарный граф:

Он планарный, потому что его можно изобразить на плоскости без самопересечений, а только это и важно.

[Geen]

забавная пирамидка будет для $N_6$ (оно же $C_6H_6$ с точки зрения алгоритма)

[denny]

Geen в сообщении #1585811 писал(а):

denny в сообщении #1585765 писал(а):

хотя предполагается что это должна быть "молекула тетразета"

алгоритм тяготеет к простым связям (а 4 азота вкучку - выглядит немного как перебор)

Да, я заметил! Мультиграф получается редко (но получается).
В статье написано, что в ходе итераций можно менять способ выбора вершин, получая разные результаты.

[Geen]

denny в сообщении #1585823 писал(а):

В статье написано, что в ходе итераций можно менять способ выбора вершин, получая разные результаты.

Бензол не получить...

[denny]

Меня беспокоит вот что. В основном коде для Mathematica, который выводит рендеры графов, я использовал встроенную проверку $ConnectedGraphQ$. Но мне хотелось сделать code-golf версию, которая просто прокручивает входной список и выдает $True$ или $False$.
Если список порядков графический, в конце останется пустой список (и обратное верно).

А вот будет ли граф связным? Я заметил, что для несвязных графов в какой-то итерации обнуляются сразу два порядка. Из статьи следует, что если мы один раз "поймали" несвязность, то так оно и есть.
Но верен ли данный критерий? Доказать бы...

[mihaild]

denny в сообщении #1585827 писал(а):

Но верен ли данный критерий? Доказать бы...

Так процитированная вами теорема 7 ровно его верность и утверждает, и доказательство в статье есть.