Оглавление
Гипотеза о реконструкции
-
Гипотеза о реконструкции графов
- Гипотеза утверждает, что любой граф можно восстановить по его колоде карт.
- Колода карт – это набор карт, каждая из которых представляет собой подграф исходного графа.
-
Свойства графов и их колоды
- Порядок построения графа можно определить по его колоде.
- Количество ребер в графе можно вычислить, зная количество ребер в каждом подграфе.
- Последовательность степеней вершин в графе можно определить, зная количество ребер в подграфах.
- Связность графа можно проверить, изучив связность подграфов.
-
Проверка гипотезы
- Гипотеза была проверена для графов с не более чем 13 вершинами.
- Почти все графы поддаются реконструкции, и для их восстановления достаточно трех карт из колоды.
-
Восстанавливаемые классы графов
- Регулярные графы и их дополнения могут быть восстановлены.
- Деревья, несвязанные графы, графики единичных интервалов и другие классы графов также поддаются реконструкции.
-
Двойственность и другие структуры
- Гипотеза о восстановлении вершин двойственна гипотезе о восстановлении ребер.
- Орграфы, гиперграфы и бесконечные графы не поддаются реконструкции.
- Локально конечные графы могут быть невосстанавливаемыми.
-
Дополнительные структуры и вопросы
- Существуют бесконечные невосстанавливаемые орграфы, включая турниры и не-турниры.
- Вопрос о восстанавливаемости для локально конечных бесконечных деревьев оставался открытым до 2017 года.
-
Рекомендации
- Для получения дополнительной информации предлагается ознакомиться с опросом Нэша-Уильямса.
Полный текст статьи: