圖論：Ulam 猜想

 

圖論的 Ulam 猜想（重構猜想）

---

一、Ulam 是誰？

斯坦尼斯拉夫·烏拉姆（Stanisław Ulam，1909–1984） 是波蘭裔美國數學家，以參與曼哈頓計畫（氫彈設計）聞名，同時也是>蒙地卡羅方法的發明者之一。他一生橫跨數學、物理、計算機科學，是 20 世紀最具創造力的數學家之一 。

Ulam 猜想正式名稱為重構猜想（Reconstruction Conjecture），由 Paul J. Kelly 與 Ulam 於 1940 年代共同提出，是圖論中最著名的未解問題之一 。

---

二、核心問題：你能從「殘缺拼圖」還原原圖 嗎？

生活比喻

想像你有一張照片（圖 G），有人把照片中的每一個人依序「遮住一人」>，產生 n 張略有不同的殘缺照片。

問題是：只看這疊殘缺照片，能不能還原出原始的完整照片？

這就是 Ulam 猜想的核心。

---

三、正式定義

基本概念

設圖 G = (V, E)，點數為 n。

對每個頂點 v_i ∈ V，定義頂點刪除子圖（vertex-deleted subgraph）：

G_i = G − v_i

即從 G 中移除頂點 v_i 及其所有相連的邊，得到一個有 n − 1 個點的子圖。

牌組（Deck）

所有頂點刪除子圖構成的多重集合稱為 G 的牌組：

D(G) = {G − v₁, G − v₂, …, G − v_n}

每張 G − v_i 稱為一張牌（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 將重構猜想列為圖論未解問題的第一位 。 難點在於：你必須證明「不存在任何反例」——而窮舉所有圖是不可能的任務。

這個猜想之所以迷人，是因為它陳述極簡、直覺上顯然為真，卻幾十年無人能完整證明——正是數學最引人入勝之處。

^{14151617181920}

⁂

---

1. https://www.youtube.com/watch?v=MMN7gre1kGA↩︎

2. https://www.sciencedirect.com/science/article/pii/S0012365X22000991↩︎

3. https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎

4. https://users.utu.fi/harju/graphtheory/B2=Ulam.pdf↩︎

5. https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎

6. https://experts.illinois.edu/en/publications/on-reconstruction-of-graphs-from-the-multiset-of-subgraphs-obtain-2/↩︎

7. https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎

8. https://zh.wikipedia.org/zh-tw/重构猜想↩︎

9. https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎

10. https://www.sciencedirect.com/science/article/pii/S0012365X22000991↩︎

11. https://en.wikipedia.org/wiki/Reconstruction_conjecture↩︎

12. https://en.wikipedia.org/wiki/New_digraph_reconstruction_conjecture↩︎

13. https://www.ub.edu/comb/koljaknauer/conf/Kaschek.pdf↩︎

14. https://www.combinatorics.org/files/ejc-sample.pdf↩︎

15. https://zh.wikipedia.org/zh-hant/重构猜想↩︎

16. https://srsx.cbpt.cnki.net/WKH/WebPublication/wkTextContent.aspx?contentID=&colType=4&yt=2020&st=03↩︎

17. http://arxiv.org/pdf/2004.05527.pdf↩︎

18. https://www.thepaper.cn/newsDetail_forward_29072483↩︎

19. https://www.cpr.cuhk.edu.hk/wp-content/upload/resources/press/pdf/52b7ffdd7e4c3.pdf↩︎

20. https://www.jstor.org/stable/2316851↩︎

AM-GM 算數幾何平均不等式

 

算術－幾何平均不等式：從 Cauchy 的故事說起

「兩數之和的一半，永遠不小於兩數乘積的平方根。」 這句話看似簡單，背後卻有一段跨越兩百年的數學故事。

---

一、Cauchy 是誰？

奧古斯丁－路易·柯西（Augustin-Louis Cauchy，1789–1857） 是法國數學史上最多產的數學家之一， 一生發表超過 800 篇論文，涵蓋分析學、代數、光學與天文學。

他生於法國大革命爆發的同一年，成長於動盪時代， 卻在數學世界建立了無比嚴謹的秩序。

Cauchy 最重要的貢獻，是將「極限」與「連續」賦予嚴格定義， 奠定了現代微積分的邏輯基礎。 他的名字至今仍出現在無數定理與公式之中： Cauchy 數列、Cauchy 積分公式、Cauchy–Schwarz 不等式……

📌 有人說：「如果牛頓發明了微積分，那麼 Cauchy 把它變得可信。」

---

二、為什麼需要 AM-GM 不等式？

動機一：最佳化問題

人類很早就面對這樣的問題：

「用固定長度的籬笆，圍出最大面積的矩形，應該怎麼圍？」

設周長固定為 2n，兩邊長為 x 與 n − x， 面積為 x(n − x)。

我們直覺上猜測「正方形最大」， 但要嚴格證明這件事，就需要 AM-GM 不等式。

動機二：嚴格化數學直覺

在 Cauchy 的年代，許多數學結論靠的是「感覺正確」， 缺乏嚴謹證明。Cauchy 致力於將這些直覺轉化為 可驗證、可推廣的嚴格定理。

AM-GM 不等式正是這種精神的體現： 把「均勻分配乘積最大」這個直覺， 鑄造成一個對任意 n 個數都成立的數學真理。

動機三：跨領域的普適性

AM-GM 不等式一旦建立，應用範圍遠超幾何： 統計學、物理學、資訊理論、金融數學…… 處處都需要「比較平均數與乘積」的工具。

---

三、什麼是 AM-GM 不等式？

對任意 n 個非負實數 a₁, a₂, …, a_n， 算術平均數（AM）永遠大於等於幾何平均數（GM）：

$$ \frac{a_1 + a_2 + \cdots + a_n}{n} \geq \sqrt[n]{a_1 \cdot a_2 \cdots a_n} $$

等號成立條件：所有數完全相等，即 a₁ = a₂ = ⋯ = a_n。

---

四、直觀感受：幾個例子

數組	算術平均（AM）	幾何平均（GM）	AM ≥ GM？
1, 9	5	3	✅
4, 4	4	4	✅（等號成立）
1, 2, 3	2	≈ 1.817	✅

📌 關鍵觀察：只有當所有數相等時，AM 才等於 GM； 只要數字「不均勻」，AM 就會嚴格大於 GM。

---

五、證明一：兩數版本（配方法）

命題：對任意 a, b ≥ 0，證明 $\dfrac{a+b}{2} \geq \sqrt{ab}$。

證明：

任意實數的平方非負，故：

$$(\sqrt{a} - \sqrt{b})^2 \geq 0$$

展開得：

$$a - 2\sqrt{ab} + b \geq 0$$

移項整理：

$$\frac{a + b}{2} \geq \sqrt{ab}$$

等號成立條件：$\sqrt{a} = \sqrt{b}$，即 a = b。◼

💡 這個證明只用到「平方非負」這一個最基本的事實， 卻推出了如此有力的結論——這正是數學之美。

---

六、證明二：n 數版本（Cauchy 前進後退法，1821）

這是 Cauchy 在 1821 年著作《分析教程》(Cours d’analyse) 中提出的天才證明， 分「前進」與「後退」兩個步驟。

步驟 A：先證 n = 2^k 的情形（前進歸納）

• 基底：n = 2 已由配方法證明。
• 歸納步驟：假設 n = m 時成立，證 n = 2m 時也成立。

將 2m 個數分成前後兩組各 m 個， 對每組用歸納假設得到各組的幾何平均 G₁、G₂， 再對 G₁、G₂ 使用兩數 AM-GM，即可完成。

由此對所有 n = 2^k（k = 1, 2, 3, …）成立。✅

歸納步驟：假設 n = m 時成立，證明 n = 2m 時也成立。

設有 2m 個數 a₁, …, a_2m，令：

$$ A = \frac{a_1+\cdots+a_{2m}}{2m}, \quad G = \sqrt[2m]{a_1 \cdots a_{2m}} $$

將前 m 個數與後 m 個數分組，由歸納假設：

$$ \frac{a_1+\cdots+a_m}{m} \geq \sqrt[m]{a_1\cdots a_m} = G_1 $$

$$ \frac{a_{m+1}+\cdots+a_{2m}}{m} \geq \sqrt[m]{a_{m+1}\cdots a_{2m}} = G_2 $$

對 G₁, G₂ 再用兩數 AM-GM：

$$ A = \frac{G_1 + G_2}{2} \cdot \frac{\text{(兩組AM之和)}}{2} \geq \sqrt{G_1 G_2} = \sqrt[2m]{a_1 \cdots a_{2m}} = G $$

故 n = 2m 時成立。由此對所有 n = 2^k 成立。✅

步驟 B：從 2^k 推回任意 n（後退歸納）

假設 n 個數的 AM-GM 成立，證 n − 1 個數也成立。

對 n − 1 個數 a₁, …, a_n − 1，令其算術平均為：

$$A = \frac{a_1 + \cdots + a_{n-1}}{n-1}$$

補入第 n 個數 a_n = A（補入平>均數本身）， 對這 n 個數套用已知的 AM-GM：

$$A \geq \sqrt[n]{a_1 \cdots a_{n-1} \cdot A}$$

兩邊取 n 次方後除以 A，整理得：

$$\frac{a_1 + \cdots + a_{n-1}}{n-1} \geq \sqrt[n-1]{a_1 \cdots a_{n-1}}$$

n − 1 個數的 AM-GM 成立。◼

🔑 Cauchy 的天才之處：不直接對所有 n 歸納， 而是「先跳躍到更大的 2^k，再倒退回來」， 繞開了直接歸納難以逾越的障礙。

---

七、AM-GM 的應用場景

AM-GM 不等式看似純粹，實則無處不在：

• 幾何最佳化：固定周長的矩形，正方形面積最大
• 圖論：Turán 定理的核心——均分兩組點數，邊數最多
• 統計學：解釋為何變異數恆  ≥ 0
• 金融投資：幾何平均報酬率 ≤ 算術平均報酬率， 說明「波動拖累複利成長」的本質
• 物理學：最小作用量原理推導的輔助工具

---

八、一句話總結

AM-GM 不等式告訴我們： 「均勻分配，永遠比不均勻分配更能極大化乘積。」

Cauchy 用一個優雅的前進後退法， 將這個直覺鑄造成永恆的數學真理。

---

圖論 - 1 定義 - bipartite graph 二分圖 二部圖

前篇：圖論 - 1 定義 - 1

1️⃣ 簡易版定義

二部圖是一種特殊的圖，把所有「點」分成兩組，每條「邊」只能連 接不同組的點，同組內的點之間沒有任何邊。

舉個生活例子：把「棒球球員」放 A 組、「棒球球隊」放 B 組，邊代表「某球員曾效力某球隊」。同組內部不會連線 —— 這就是一個二部圖！

---

2️⃣ 專業版定義

設圖 G = (V, E)，其中 V 為點集合、E 為邊集合。

若存在一個分割 V = X ∪ Y，使得：

X ∩ Y = ∅

且所有邊 e ∈ E 均滿足：

e = {x, y},  x ∈ X, y ∈ Y

則稱 G 為二部圖（Bipartite Graph），(X, Y) 稱為其二部分割（bipartition）。

特殊情形——完全二部圖 K_m, n>：若 |X| = m、|Y| = n，且 X 中每點都與 Y 中每點相連，共有 m × n 條邊，則稱為完全二部圖。

📌 關鍵性質：一個圖是二部圖，若且唯若它不含奇數長度的環（odd cycle）。

---

3️⃣ 結構圖解（Mermaid 心智圖）

 
graph LR
  subgraph X組["X 組（左側點）"]
    x1((x₁))
    x2((x₂))
    x3((x₃))
  end
  subgraph Y組["Y 組（右側點）"]
    y1((y₁))
    y2((y₂))
    y3((y₃))
  end
  x1 --- y1
  x1 --- y2
  x2 --- y2
  x2 --- y3
  x3 --- y1
  x3 --- y3  

 

---

✅ 每條邊只跨越 X 與 Y 兩組之間，X 內、Y 內沒有任何邊。