2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 12:36 


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

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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 12:52 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 13:16 


20/12/14
148
mihaild в сообщении #1585739 писал(а):
Скорее если мы добавляем ребра по одному и уже добавили достаточно, чтобы гарантировать связность, оставшиеся можно добавлять вообще как угодно, и ничего не сломается.


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

-- 17.03.2023, 14:22 --

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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 13:33 
Заслуженный участник
Аватара пользователя


16/07/14
9219
Цюрих
denny в сообщении #1585742 писал(а):
где представленный алгоритм сразу останавливается
Представленный - это Гавела-Хакими? Ну да, он для графов, не для мультиграфов.
denny в сообщении #1585742 писал(а):
то конечно можно самому переписать алгоритм, но не получается, даже для простейших случаев
А чем Вас не устраивает метод по Вашей ссылке на stackexchange?
denny в сообщении #1585742 писал(а):
Кажется вот здесь
есть ответ
Кажется для такой задачи это слишком сложно.

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 13:43 


20/12/14
148
На 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.

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 16:56 


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

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

На первый вопрос можно ответить численно, проверив следующие критерии:
  • Сумма порядков является четной
  • Полусумма порядков больше или равна числу вершин, уменьшенному на $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]$
Граф:
Изображение

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 17:06 
Заслуженный участник
Аватара пользователя


16/07/14
9219
Цюрих
denny, да, всё правильно. Вопрос, как по степеням вершин эффективно определить, существует ли планарный граф с такими степенями, вроде бы открыт. Для мультиграфа это может быть проще, но сходу ничего найти не удалось.
mihaild в сообщении #1585739 писал(а):
оставшиеся можно добавлять вообще как угодно, и ничего не сломается
Тут я, кстати, проврался немного. Если петли запрещены, то даже с мультиграфом можно всё сломать. Например если с графом $(4, 2, 2)$ добавить ребро между двумя двойками.

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 21:17 


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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 22:28 
Заслуженный участник
Аватара пользователя


01/09/13
4688
denny в сообщении #1585765 писал(а):
хотя предполагается что это должна быть "молекула тетразета"

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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 22:36 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
denny в сообщении #1585765 писал(а):
простой, но непланарный граф:
Изображение
Он планарный, потому что его можно изобразить на плоскости без самопересечений, а только это и важно.

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение17.03.2023, 22:47 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение18.03.2023, 07:42 


20/12/14
148
Geen в сообщении #1585811 писал(а):
denny в сообщении #1585765 писал(а):
хотя предполагается что это должна быть "молекула тетразета"

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

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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение18.03.2023, 08:44 
Заслуженный участник
Аватара пользователя


01/09/13
4688
denny в сообщении #1585823 писал(а):
В статье написано, что в ходе итераций можно менять способ выбора вершин, получая разные результаты.

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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение18.03.2023, 08:45 


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

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

 Профиль  
                  
 
 Re: Havel-Hakimi алгоритм для графов с кратными ребрами
Сообщение21.03.2023, 13:19 
Заслуженный участник
Аватара пользователя


16/07/14
9219
Цюрих
denny в сообщении #1585827 писал(а):
Но верен ли данный критерий? Доказать бы...
Так процитированная вами теорема 7 ровно его верность и утверждает, и доказательство в статье есть.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group