У теорії графів неформально гіпотеза реконструкції стверджує, що графи однозначно визначаються своїми підграфами. Її запропонували КелліKelly, P. J., [(http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674) A congruence theorem for trees], Pacific J. Math. 7 (1957), 961–968. та Улам.Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.
Формальні формулювання
Нехай задано граф . Підграф, отриманий видаленням вершини, — це підграф, утворений шляхом видалення рівно однієї вершини з . За означенням, це індукований підграф графа .
Для графа колода графа G, що позначається , — це мультимножина класів ізоморфізму всіх підграфів, отриманих видаленням однієї вершини з . Кожен граф у називається карткою. Два графи, які мають однакові колоди, називаються гіпоморфними.
За цих означень гіпотезу можна сформулювати так:
Гіпотеза реконструкції: будь-які два гіпоморфні графи з принаймні трьома вершинами є ізоморфними.
(Вимога наявності щонайменше трьох вершин є необхідною, оскільки обидва графи з двома вершинами мають однакові колоди.)
ХараріHarary, F., On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52. запропонував сильнішу версію цієї гіпотези:
Гіпотеза множинної реконструкції: будь-які два графи з принаймні чотирма вершинами, що мають однакові множини підграфів, отриманих видаленням однієї вершини, є ізоморфними.
Нехай задано граф . Підграф, отриманий видаленням ребра, — це підграф, утворений шляхом видалення рівно одного ребра з .
Для графа реберна колода графа G, що позначається , — це мультимножина вс registration класів ізоморфізму всіх підграфів, отриманих видаленням одного ребра з . Кожен граф у називається реберною карткою.
Гіпотеза реберної реконструкції: (Харарі, 1964) будь-які два графи з принаймні чотирма ребрами, що мають однакові реберні колоди, є ізоморфними.
Розпізнавані властивості
У контексті гіпотези реконструкції властивість графа називається розпізнаваною, якщо її можна визначити за колодою графа. Наступні властивості графів є розпізнаваними:
Порядок графа — порядок графа , , є розпізнаваним з , оскільки мультимножина містить кожен підграф, утворений видаленням однієї вершини з . Отже, . Кількість ребер графа — кількість ребер у графі з вершинами, , є розпізнаваною. Зауважимо, що кожне ребро графа входить до елементів . Це випливає з означення : кожне ребро зберігається щоразу, коли в картці присутні обидві його інцидентні вершини, тобто воно відсутнє лише в тих двох картках, де видалено одну з його кінцевих вершин. Отже, , де — кількість ребер у i-тій картці з . Кількість підграфів порядку (лема Келлі) — узагальнюючи підхід до підрахунку ребер, можна стверджувати, що для деякого підграфа з вершинами у графі з вершинами кількість появ у (позначається ) є відновлюваною. Кожен екземпляр у з’являється рівно в усіх тих картках, де не видалено жодну вершину з , тобто у картках. Тому , де — i-та картка. Послідовність степенів — послідовність степенів графа є розпізнаваною, оскільки степінь кожної вершини можна визначити. Щоб знайти степінь вершини — вершини, відсутньої в i-тій картці , — розглянемо граф , утворений її видаленням. Він містить усі ребра, не інцидентні . Якщо — кількість ребер у , то . Знаючи степені всіх вершин, можна відновити послідовність степенів графа. (Вершинна) зв’язність — за означенням, граф є -вершинно-зв’язним, якщо видалення будь-якої вершини породжує -вершинно-зв’язний граф; отже, якщо кожна картка є -вершинно-зв’язною, то вихідний граф був -вершинно-зв’язним. Також можна визначити, чи був початковий граф зв’язним, оскільки це еквівалентно тому, що будь-які два графи є зв’язними. Многочлен Тутте Характеристичний многочлен Планарність Кількість остовних дерев у графі Хроматичний многочлен Належність до досконалих графів або інтервальних графів, а також до деяких інших підкласів досконалих графівvon Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
Перевірка
Гіпотези реконструкції та множинної реконструкції були перевірені для всіх графів з не більш ніж 13 вершинами Бренданом Маккеєм.McKay, B. D., Small graphs are reconstructible, Australas. J. Combin. 15 (1997), 123–126.
У ймовірнісному сенсі Бела Боллобаш довів, що майже всі графи є реконструйовними.Bollobás, B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4. Це означає, що ймовірність того, що випадково вибраний граф з вершинами не є реконструйовним, прямує до 0 при . Більше того, показано, що для майже всіх графів для реконструкції не потрібна вся колода: існують три картки, які однозначно визначають граф.
Реконструйовні родини графів
Гіпотезу перевірено для низки нескінченних класів графів (і, тривіально, для їх доповнень):
Регулярний графи — регулярні графи реконструйовні шляхом прямого застосування розпізнаваних із колоди фактів. Нехай — -регулярний граф з колодою . Регулярність розпізнається за послідовністю степенів. Розглянемо картку : вона містить деяку кількість вершин степеня та вершин степеня . Додавши вершину і з’єднавши її з вершинами степеня , отримаємо -регулярний граф, ізоморфний початковому. Отже, всі регулярні графи є реконструйовними з їх колод. Особливим прикладом є повний граф.) Дерева Незв’язні графи Одиничний інтервальний графи Розкладний граф без кінцевих вершин Максимальний планарний графи Максимальний зовнішньопланарний графи Зовнішньопланарний графи Критичні блоки
Зведення Гіпотеза реконструкції є істинною, якщо всі 2-вершинно-зв’язні графи є реконструйовними.Yang Yongzhi: The reconstruction conjecture is true if all 2-connected graphs are reconstructible. Journal of graph theory 12, 237–243 (1988)
Дуальність
Гіпотеза вершинної реконструкції задовольняє таку дуальність: якщо можна реконструювати з його вершинної колоди , то його доповнення можна реконструювати з так: починаємо з , беремо доповнення кожної картки, отримуємо , реконструюємо , а потім знову беремо доповнення, щоб одержати .
Реберна реконструкція такої дуальності не має: зокрема, для деяких класів реберно-реконструйовних графів невідомо, чи є їх доповнення реберно-реконструйовними.
Інші структури
Показано, що такі структури загалом не є реконструйовними:
Орграфи: відомі нескінченні родини нереконструйовних орграфів, зокрема турніри (СтокмайєрStockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory 1 (1977), 19–25.) і нетурніри (СтокмайєрStockmeyer, P. K., A census of non-reconstructable digraphs, I: six related families, J. Combin. Theory Ser. B 31 (1981), 232–239.). Турнір є реконструйовним, якщо він не є сильно зв’язним.Harary, F. and Palmer, E., On the problem of reconstructing a tournament from sub-tournaments, Monatsh. Math. 71 (1967), 14–23. Для орграфів сформульовано слабшу версію гіпотези реконструкції, див. new digraph reconstruction conjecture. Гіперграфи, зокрема всі k-однорідні гіперграфи для k>2 (КокейKocay, W. L., A family of nonreconstructible hypergraphs, J. Combin. Theory Ser. B 42 (1987), 46–63.). Нескінченні графи. Якщо T — дерево, в якому кожна вершина має зліченно нескінченний степінь, то об’єднання двох неперетинних копій T є гіпоморфним, але не ізоморфним до T (ФішерFisher, Joshua, A counterexample to the countable version of a conjecture of Ulam, J. Combin. Theory 7 (4) (1969), 364–365.)) Локально скінченні графи, тобто графи, у яких кожна вершина має скінченний степінь. Питання реконструйовності локально скінченних нескінченних дерев (гіпотеза Харарі—Швенка—Скотта 1972 року) довго залишалося відкритим, доки у 2017 році Боулер та ін. не знайшли нереконструйовне дерево з максимальним степенем 3.Bowler, N., Erde, J., Heinig, P., Lehner, F. and Pitz, M. (2017), A counterexample to the reconstruction conjecture for locally finite trees. Bull. London Math. Soc..
Див. також
New digraph reconstruction conjecture Часткова симетрія
Додаткова література Докладніший огляд наведено в роботі Неша-Вільямса.Nash-Williams, C. St. J. A., The Reconstruction Problem, in Selected topics in graph theory, 205–236 (1978).
Примітки