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

Нерешенная проблема в математике:

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

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

Формальные заявления

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

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

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

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

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

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

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

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

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

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

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

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

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

Порядок графика - Порядок графа ${ displaystyle G}$ , ${ Displaystyle | V (G) |}$ узнаваем из ${ Displaystyle D (G)}$ как мультимножество ${ Displaystyle D (G)}$ содержит каждый подграф ${ displaystyle G}$ создается путем удаления одной вершины ${ displaystyle G}$ . Следовательно ${ Displaystyle | V (G) | = | D (G) |}$ ^[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)}$ .^[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})}$ . Если мы можем сказать степень каждой вершины в графе, мы можем определить последовательность степеней графа.^[5]
(Vertex-) Связь - По определению граф ${ displaystyle n}$ -vertex-connected при удалении любой вершины создает ${ displaystyle n-1}$ -связный граф; таким образом, если каждая карта является ${ displaystyle n-1}$ -связный граф, мы знаем, что исходный граф был ${ displaystyle n}$ -вершинно-связанные. Мы также можем определить, был ли исходный граф связан, поскольку это эквивалентно наличию любых двух из ${ displaystyle G_ {i}}$ будучи подключенным.^[5]
Полином Тутте
Характеристический полином
Планарность
Типы остовные деревья в графике
Хроматический полином
Быть идеальный график или интервальный график, или некоторые другие подклассы совершенных графов^[6]

Проверка

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

В вероятностном смысле это было показано Béla Bollobás что почти все графы реконструируемы.^[8] Это означает, что вероятность того, что случайно выбранный граф на ${ displaystyle n}$ вершины не восстанавливаются, переходит в 0 при ${ 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 '}$ .

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

Другие конструкции

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

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

Смотрите также

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

Дополнительную информацию по этой теме см. В опросе автора Нэш-Вильямс.^[17]