Новая гипотеза реконструкции орграфа
Гипотеза реконструкции Станислава Улама — одна из самых известных открытых проблем теории графов . Используя терминологию Фрэнка Харари [1] это можно сформулировать следующим образом: если G и H — два графа по крайней мере с тремя вершинами, а ƒ — биекция из V ( G ) в V ( H ) такая, что G \{ v } и H \ {ƒ( v )} изоморфны для всех вершин v в V ( G ), то G и H изоморфны.
В 1964 году Харари [2] распространил гипотезу реконструкции на ориентированные графы по крайней мере с пятью вершинами как так называемую гипотезу реконструкции орграфа. Многие результаты, подтверждающие гипотезу реконструкции орграфа, появились в период с 1964 по 1976 год. Однако эта гипотеза оказалась ложной, когда П. К. Стокмейер обнаружил несколько бесконечных семейств пар контрпримеров орграфов (включая турниры) сколь угодно большого порядка. [3] [4] [5] Ложность гипотезы о реконструкции орграфа вызвала сомнение в самой гипотезе о реконструкции. Стокмейер даже заметил, что «возможно, значительные усилия, затрачиваемые на попытки доказать гипотезу (реконструкции), должны быть уравновешены более серьезными попытками построить контрпримеры». [3]
В 1979 году Рамачандран возродил гипотезу реконструкции орграфа в несколько более слабой форме, названной гипотезой новой реконструкции орграфа . В орграфе количество дуг, инцидентных (соответственно, в) вершине v , называется исходящей степенью ( входящей степенью ) вершины v и обозначается od ( v ) (соответственно id ( v )). Новую гипотезу орграфа можно сформулировать следующим образом: [6] [7]
Если D и E — любые два орграфа, а ƒ — биекция V ( D ) в V ( E ) такая, что D \{ v } и E \{ƒ( v )} изоморфны и ( od ( v ), id ( v )) = ( od (ƒ( v )), id (ƒ( v ))) для всех v в V ( D ), то D и E изоморфны.
Гипотеза о реконструкции нового орграфа сводится к гипотезе о реконструкции в неориентированном случае, поскольку если все подграфы с удаленными вершинами двух графов изоморфны, то соответствующие вершины должны иметь одинаковую степень. Таким образом, гипотеза о реконструкции нового орграфа сильнее, чем гипотеза о реконструкции, но слабее, чем опровергнутая гипотеза о реконструкции орграфа. Было показано, что несколько семейств орграфов удовлетворяют новой гипотезе о реконструкции орграфа, и они включают все орграфы в известных парах контрпримеров к гипотезе о реконструкции орграфа.
Скидки
[ редактировать ]- Все орграфы являются N-реконструируемыми, если все орграфы с 2-связными базовыми графами N-реконструируемы. [8]
- Все орграфы являются N-реконструируемыми тогда и только тогда, когда любой из следующих двух классов орграфов является N-реконструируемым, где diam(D) и radius(D) определяются как диаметр и радиус основного графа D. [9]
- Орграфы с diam(D) ≤ 2 или diam(D) = diam(D с ) = 3
- Орграфы D с 2-связными базовыми графами и радиусом (D) ≤ 2
Текущий статус
[ редактировать ]По состоянию на 2024 год не известно ни одного контрпримера гипотезе о реконструкции нового орграфа. Эта гипотеза теперь также известна как гипотеза реконструкции, связанной со степенью .
Ссылки
[ редактировать ]- ^ Харари, Фрэнк (1969), Теория графов , Ридинг, Массачусетс: Аддисон-Уэсли, MR 0256911 .
- ^ Харари, Франк (1964), «О восстановлении графа по набору подграфов», в книге Фидлер, М. (ред.), Теория графов и ее приложений (Proc. Sympos. Smolenice, 1963) , Publ. Дом Чехословацкой академии. Sci., Прага, стр. 47–52, MR 0175111.
- ^ Перейти обратно: а б Стокмейер, Пол К. (1977), «Ложность гипотезы реконструкции турниров» , Журнал теории графов , 1 (1): 19–25, doi : 10.1002/jgt.3190010108 , MR 0453584 . Опечатка, Дж. График Th. 62 (2): 199–200, 2009, дои : 10.1002/jgt.20398 , MR 2555098 .
- ^ Стокмейер, Пол К. (1981), «Перепись нереконструируемых орграфов. I. Шесть родственных семейств», Журнал комбинаторной теории , серия B, 31 (2): 232–239, doi : 10.1016/S0095-8956(81) 80027-5 , МР 0630985 .
- ^ Стокмейер, Пол К. (1991), Перепись нереконструируемых орграфов II: Семья турниров , Препринт .
- ^ Рамачандран, С. (1979), «Гипотеза о реконструкции орграфа», Информационный бюллетень теории графов , 8 (4), Университет Западного Мичигана .
- ^ Рамачандран, С. (1981), «О новой гипотезе реконструкции орграфа», Журнал комбинаторной теории , серия B, 31 (2): 143–149, doi : 10.1016/S0095-8956(81)80019-6 , MR 0630977 .
- ^ Рамачандран, С; Моникандан, С. (2006), «Все орграфы являются N-реконструируемыми, если все орграфы с 2-связными базовыми графами N-реконструируемы» , Utilitas Mathematica , 71 , UTIL MATH PUBL INC: 225–234, MR 2278835
- ^ Рамачандран, С. (2012), «Достаточные условия для N-восстановимости всех орграфов» , Utilitas Mathematica , 88 , UTIL MATH PUBL INC: 183–188, MR 2975831