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

Неформально гипотеза реконструкции в теории графов утверждает, что графы однозначно определяются своими подграфами. Это связано с Келли ^[1] и Уламом . ^{[2] [3]}

Формальные заявления [ править ]

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

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

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

С этими определениями гипотезу можно сформулировать так:

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

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

Харари ^[4] предложил более сильную версию гипотезы:

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

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

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

• Гипотеза реконструкции ребер: (Harary, 1964) ^[4] Любые два графа с не менее чем четырьмя ребрами и с одинаковыми ребрами-колодами изоморфны.

Узнаваемые свойства [ править ]

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

• Порядок графа - порядок графа , узнаваем из как мультимножество содержит каждый подграф созданного путем удаления одну вершины . Следовательно ^[5]${\ displaystyle G}$${\ Displaystyle | V (G) |}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ displaystyle G}$${\ displaystyle G}$${\ Displaystyle | V (G) | = | D (G) |}$
• Количество ребер графа - количество ребер в графе с вершинами распознается. Сначала обратите внимание, что каждое ребро входит в члены . Это верно по определению, которое гарантирует, что каждое ребро включается каждый раз, когда каждая из вершин, с которой оно инцидентно, включается в член , поэтому ребро будет встречаться в каждом члене, за исключением двух, в которых его конечные точки находятся удалено. Следовательно, где - количество ребер в i- м члене . ^[5]${\ displaystyle G}$${\ displaystyle n}$${\ displaystyle | E (G) |}$${\ displaystyle G}$${\ displaystyle n-2}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ displaystyle | E (G) | = \ sum {\ frac {q_ {i}} {n-2}}}$${\displaystyle q_{i}}$${\displaystyle D(G)}$
• Последовательность степеней - последовательность степеней графа узнаваема, потому что степень каждой вершины узнаваема. Для того, чтобы найти степень вершины -The вершину отсутствует в I - е члена - мы рассмотрим граф , созданный путем удаления его, . Этот граф содержит все ребра, не инцидентные с , поэтому, если - количество ребер в , то . Если мы можем сказать степень каждой вершины в графе, мы можем сказать последовательность степеней графа. ^[5]${\displaystyle G}$${\displaystyle v_{i}}$${\displaystyle D(G)}$${\displaystyle G_{i}}$${\displaystyle v_{i}}$${\displaystyle q_{i}}$${\displaystyle G_{i}}$${\displaystyle |E(G)|-q_{i}=\deg(v_{i})}$
• (Vertex-) Connectivity - По определению, граф связан с вершинами, когда удаление любой вершины создает граф, связанный с вершинами; таким образом, если каждая карта является -вершинно-связным графом, мы знаем, что исходный граф был -вершинно-связным. Мы также можем определить, был ли исходный граф связан, поскольку это эквивалентно наличию любых двух из соединяемых. ^[5]${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle G_{i}}$
• Полином Тутте
• Характеристический полином
• Планарность
• Типы остовных деревьев в графе
• Хроматический полином
• Будучи идеальный график или интервальный график , или некоторые другие подклассы совершенных графов ^[6]

Подтверждение [ править ]

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

В вероятностном смысле Бела Боллобас показал, что почти все графы реконструируемы. ^[8] Это означает, что вероятность того, что случайно выбранный граф на вершинах не восстанавливается, стремится к 0, как и к бесконечности. Фактически, было показано, что не только почти все графы реконструируемы, но и что для их восстановления не требуется вся колода - почти все графы обладают тем свойством, что в их колоде есть три карты, которые однозначно определяют граф.${\displaystyle n}$${\displaystyle n}$

Семейства реконструируемых графов [ править ]

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

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

Сокращение [ править ]

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

Двойственность [ править ]

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

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

Другие конструкции [ править ]

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

• Орграфы : известны бесконечные семейства невосстановимых орграфов, включая турниры (Stockmeyer ^[12] ) и нетурниры (Stockmeyer ^[13] ). Турнир реконструируем, если он не сильно связан. ^[14] Для орграфов была выдвинута более слабая версия гипотезы реконструкции, см. Новую гипотезу реконструкции орграфа .
• Гиперграфы ( Коджай ^[15] ).
• Бесконечные графы . Пусть Т дерево на бесконечном числе вершин, что каждая вершина имеет бесконечную степень, и пусть п Т быть несвязный из п копия Т. Эти графики гипоморфные, и , таким образом , не восстановит. Каждый подграф любого из этих графов с удаленными вершинами изоморфен: все они являются несвязным объединением бесконечного числа копий T.
• Локально конечные графы. Вопрос о реконструируемости для локально конечных бесконечных деревьев (гипотеза Харари-Швенка-Скотта от 1972 года) был давней открытой проблемой до 2017 года, когда Боулер и др. Нашли невосстановимое дерево максимальной степени 3. ^[16]

См. Также [ править ]

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

Дальнейшее чтение [ править ]

Дополнительную информацию по этой теме см. В обзоре Nash-Williams . ^[17]

Ссылки [ править ]