圖論的 Ulam 猜想（重構猜想）
一、Ulam 是誰？
斯坦尼斯拉夫·烏拉姆（Stanisław Ulam，1909–1984） 是波蘭裔美國數學家，以參與曼哈頓計畫（氫彈設計）聞名，同時也是>蒙地卡羅方法的發明者之一。他一生橫跨數學、物理、計算機科學，是 20 世紀最具創造力的數學家之一 。
Ulam 猜想正式名稱為重構猜想（Reconstruction Conjecture），由 Paul J. Kelly 與 Ulam 於 1940 年代共同提出，是圖論中最著名的未解問題之一 。
二、核心問題：你能從「殘缺拼圖」還原原圖 嗎？
生活比喻
想像你有一張照片（圖 G），有人把照片中的每一個人依序「遮住一人」>，產生 n 張略有不同的殘缺照片。
問題是：只看這疊殘缺照片，能不能還原出原始的完整照片？
這就是 Ulam 猜想的核心。
三、正式定義
基本概念
設圖 G = (V, E)，點數為 n。
對每個頂點 vi ∈ V，定義頂點刪除子圖（vertex-deleted subgraph）：
Gi = G − vi
即從 G 中移除頂點 vi 及其所有相連的邊，得到一個有 n − 1 個點的子圖。
牌組（Deck）
所有頂點刪除子圖構成的多重集合稱為 G 的牌組：
D(G) = {G − v1, G − v2, …, G − vn}
每張 G − vi 稱為一張牌（card）
猜想陳述
Ulam 重構猜想：對任意兩個頂點數 n ≥ 3 的圖 G 與 H， 若 D(G) = D(H)（牌組 相同），則 G ≅ H（兩圖同構）。
白話版：「一個圖可以由它的所有頂點刪除子圖唯一決定。」
四、具體例子
設 G 為一個有 4 個頂點的路徑圖：
1 — 2 — 3 — 4其牌組 D(G) 含 4 張牌：
| 刪除頂點 | 剩餘子圖 |
|---|---|
| 刪 v1 | 2 — 3 — 4（路徑 P3） |
| 刪 v2 | 1 3 — 4（K1 + P2） |
| 刪 v3 | 1 — 2 4（P2 + K1） |
| 刪 v4 | 1 — 2 — 3（路徑 P3） |
Ulam 猜想主張：沒有任何其他非同構的圖會產生完全一樣的牌組。
五、已知的進展
已證明可重構的圖類
- 樹（Trees）
- 正則圖（Regular graphs）
- 可分離圖（Separable graphs，無端點）
- 最大平面圖（Maximal planar graphs）
- 單位區間圖（Unit interval graphs）
概率意義下的突破
Béla Bollobás 證明：幾乎所有圖都是可重構的——隨著點數 n → ∞，隨機圖不可重構的概率趨近於 0。甚至只需牌組中的 3 張牌，就能決定幾乎所有圖 。
至今仍未解決
儘管成立超過 80 年，一般情形至今仍是未解問題 。若能證明所有2-連通圖可重構，則整個猜想成立 。
六、相關延伸猜想
| 猜想 | 提出者 | 內容 |
|---|---|---|
| 重構猜想 | Kelly & Ulam（1942） | 頂點刪除牌組決定圖 |
| 邊重構猜想 | Harary（1964） | 邊刪除牌組決定圖（n ≥ 4） |
| 集合重構猜想 | Harary | 用集合（非多重集合）亦可重構 |
| 有向圖重構猜想 | 多人 | 推廣至有向圖 |
七、為何此猜想如此困難？
數學家 Bondy 將重構猜想列為圖論未解問題的第一位 。 難點在於：你必須證明「不存在任何反例」——而窮舉所有圖是不可能的任務。
這個猜想之所以迷人，是因為它陳述極簡、直覺上顯然為真，卻幾十年無人能完整證明——正是數學最引人入勝之處。
https://www.youtube.com/watch?v=MMN7gre1kGA↩︎
https://www.sciencedirect.com/science/article/pii/S0012365X22000991↩︎
https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎
https://users.utu.fi/harju/graphtheory/B2=Ulam.pdf↩︎
https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎
https://experts.illinois.edu/en/publications/on-reconstruction-of-graphs-from-the-multiset-of-subgraphs-obtain-2/↩︎
https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎
https://zh.wikipedia.org/zh-tw/重构猜想↩︎
https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎
https://www.sciencedirect.com/science/article/pii/S0012365X22000991↩︎
https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎
https://en.wikipedia.org/wiki/New_digraph_reconstruction_conjecture↩︎
https://www.ub.edu/comb/koljaknauer/conf/Kaschek.pdf↩︎
https://www.combinatorics.org/files/ejc-sample.pdf↩︎
https://zh.wikipedia.org/zh-hant/重构猜想↩︎
https://srsx.cbpt.cnki.net/WKH/WebPublication/wkTextContent.aspx?contentID=&colType=4&yt=2020&st=03↩︎
http://arxiv.org/pdf/2004.05527.pdf↩︎
https://www.thepaper.cn/newsDetail_forward_29072483↩︎
https://www.cpr.cuhk.edu.hk/wp-content/upload/resources/press/pdf/52b7ffdd7e4c3.pdf↩︎
https://www.jstor.org/stable/2316851↩︎
沒有留言:
張貼留言