Гипотеза реконструкции

Нерешенная задача по математике :

Определяются ли графы однозначно своими подграфами?

(еще нерешенные задачи по математике)

Неформально говоря, гипотеза реконструкции в теории графов гласит, что графы однозначно определяются своими подграфами. Это из-за Келли и посуда .

Официальные заявления

Граф и связанная с ним колода подграфов с удалением одной вершины. Обратите внимание, что на некоторых карточках изображены изоморфные графы.

Учитывая график $G=(V,E)$, удаленными вершинами подграф с $G$ — подграф, образованный удалением ровно одной вершины из $G$. По определению это индуцированный подграф графа $G$.

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

Используя эти определения, гипотезу можно сформулировать следующим образом:

• Гипотеза реконструкции: любые два гипоморфных графа по крайней мере с тремя вершинами изоморфны.

(Требование, чтобы графы имели хотя бы три вершины, необходимо, поскольку оба графа с двумя вершинами имеют одинаковые колоды.)

Повредить предложил более сильную версию гипотезы:

• Гипотеза о реконструкции множеств: любые два графа по крайней мере с четырьмя вершинами с одинаковыми наборами подграфов с удаленными вершинами изоморфны.

Учитывая график $G=(V,E)$, удаленными ребрами подграф с $G$ — это подграф, образованный удалением ровно одного ребра из $G$.

Для графика $G$, реберная колода G , обозначаемая $ED(G)$, является мультимножеством всех классов изоморфизма подграфов с удаленными ребрами $G$. Каждый график в $ED(G)$ называется краевой картой .

• Гипотеза о краевой реконструкции: (Харари, 1964) Любые два графа, имеющие не менее четырех ребер и имеющие одинаковые реберные колоды, изоморфны.

Узнаваемые свойства

В контексте гипотезы о реконструкции свойство графа называется распознаваемым, если его можно определить по колоде графа. Известны следующие свойства графов:

• Порядок графа – Порядок графа $G$, $|V(G)|$ узнаваем по $D(G)$ как мультимножество $D(G)$ содержит каждый подграф $G$ созданный путем удаления одной вершины $G$. Следовательно $|V(G)|=|D(G)|$
• Количество ребер графа – количество ребер в графе. $G$ с $n$ вершины, $|E(G)|$ узнаваем. Прежде всего заметим, что каждое ребро $G$ происходит в $n-2$ члены $D(G)$. Это верно по определению $D(G)$ что гарантирует, что каждое ребро будет включено каждый раз, когда каждая из вершин, с которыми оно инцидентно, включена в член $D(G)$, поэтому ребро появится в каждом члене $D(G)$ за исключением двух, в которых его конечные точки удалены. Следовательно, $|E(G)|=\sum {\frac {q_{i}}{n-2}}$ где $q_{i}$ количество ребер в i- м члене $D(G)$.
• Последовательность степеней - последовательность степеней графа. $G$ узнаваем, поскольку узнаваема степень каждой вершины. Чтобы найти степень вершины $v_{i}$– вершина, отсутствующая в i -м члене $D(G)$— мы рассмотрим граф, созданный путем его удаления, $G_{i}$. Этот граф содержит все ребра, не инцидентные $v_{i}$, так что если $q_{i}$ это количество ребер в $G_{i}$, затем $|E(G)|-q_{i}=\deg(v_{i})$. Если мы можем определить степень каждой вершины в графе, мы можем определить последовательность степеней графа.
• (Вершинная) связность . По определению, граф представляет собой $n$-vertex-connected при удалении любой вершины создает $n-1$-вершинно-связный граф; таким образом, если каждая карта является $n-1$-вершинно-связный граф, мы знаем, что исходный граф был $n$-вершинно-связный. Мы также можем определить, был ли исходный граф связным, поскольку это эквивалентно наличию любых двух из $G_{i}$ находясь на связи.
• Полином Тутте
• Характеристический полином
• Планарность
• Типы остовных деревьев в графе
• Хроматический полином
• Быть идеальным графом , или интервальным графом , или некоторыми другими подклассами идеальных графов.

Проверка

Гипотезы реконструкции и реконструкции множеств были проверены Бренданом Маккеем для всех графов с не более чем 13 вершинами .

показал, В вероятностном смысле Бела Боллобас что почти все графы реконструируемы. Это означает, что вероятность того, что случайно выбранный граф на $n$ вершины не реконструируются, переходит в 0, поскольку $n$ уходит в бесконечность. Фактически было показано, что не только почти все графы реконструируемы, но и то, что для их восстановления не требуется вся колода — почти все графы обладают тем свойством, что в их колоде существуют три карты, однозначно определяющие граф.

семейства

Гипотеза проверена для ряда бесконечных классов графов (и, тривиально, их дополнений).

• Обычные графики - Регулярные графы реконструируются путем прямого применения некоторых фактов, которые можно узнать из колоды графов. Учитывая $n$-регулярный график $G$ и его колода $D(G)$, мы можем признать, что колода представляет собой правильный граф, узнав последовательность ее степеней. Давайте теперь рассмотрим одного члена колоды $D(G)$, $G_{i}$. Этот граф содержит некоторое количество вершин со степенью $n$ и $n$ вершины со степенью $n-1$. Мы можем добавить вершину в этот граф, а затем соединить ее с $n$ вершины степени $n-1$ создать $n$-регулярный граф, изоморфный графу, с которого мы начали. Следовательно, все регулярные графы восстанавливаемы по своим колодам. Особый тип регулярного графа, который представляет интерес, — это полный граф.
• Деревья
• Несвязные графики
• Графики единичных интервалов
• Сепарабельные графы без конечных вершин
• Максимальные планарные графы
• Максимальные внешнепланарные графы
• Внепланарные графы
• Критические блоки

Сокращение

Гипотеза о реконструкции верна, если все 2-связные графы реконструируемы.

Двойственность

Гипотеза о реконструкции вершин подчиняется двойственности: если $G$ можно восстановить по его вершинной колоде $D(G)$, то его дополнение $G'$ можно реконструировать из $D(G')$ следующим образом: Начните с $D(G')$, возьмите дополнения к каждой карте, чтобы получить $D(G)$, используйте это для восстановления $G$, затем снова возьмите дополнение, чтобы получить $G'$.

Реконструкция ребер не подчиняется такой двойственности: действительно, для некоторых классов графов, реконструируемых по ребрам, неизвестно, реконструируемы ли их дополнения.

Другие структуры

Было показано, что следующие объекты вообще не реконструируются:

• Орграфы : известны бесконечные семейства нереконструируемых орграфов, включая турниры (Стокмейер ) и нетурниры (Стокмейер ). Турнир реконструируем, если он не сильно связан. Для орграфов была выдвинута более слабая версия гипотезы о реконструкции, см. новую гипотезу о реконструкции орграфа .
• Гиперграфики ( Кочай ).
• Бесконечные графы . Если T — дерево, каждая вершина которого имеет счетную бесконечную степень, то объединение двух непересекающихся копий T гипоморфно, но не изоморфно T .
• Локально конечные графы — графы, в которых каждая вершина имеет конечную степень. Вопрос о реконструируемости локально конечных бесконечных деревьев (гипотеза Харари-Швенка-Скотта 1972 года) был давней открытой проблемой до 2017 года, когда Боулер и др. обнаружили нереконструируемое дерево максимальной степени 3.

См. также

• Новая гипотеза реконструкции орграфа
• Частичная симметрия

Дальнейшее чтение

Дополнительную информацию по этой теме можно найти в опросе Нэша-Уильямса .