Re: [問題] 六角蓋塔
將問題用圖論的語言重新改寫：
(*) 對於有頂點集 V、邊集 E 的圖 G
f: V → Z 滿足 f(v) ≧ #{u∈V: uv∈E, f(u) < f(v)}
求 Σ_{v∈V} f(v) 的最大可能值 t(G)
# 跟絕對值一樣，都是代表數個數
→
09/28 00:50,
09/28 00:50
以上便是在說明上界 t(G) ≦ |E|
用圖論的語言來說：
Σ_{v∈V} f(v) ≦ Σ_{v∈V} #{u∈V: uv∈E, f(u) < f(v)}
= Σ_{v∈V} Σ_{u∈V} χ(f(u) < f(v))
= Σ_{uv∈E} χ(f(u) < f(v)) + χ(f(v) < f(u))
= Σ_{uv∈E} χ(f(u) ≠ f(v)) ≦ |E|
其中 χ(True) = 1, χ(False) = 0
從而有 t(G) = max_f Σ_{v∈V} f(v) ≦ |E|
※ 以下證明 t(G) ≧ |E|
概念上是找到一個總和達到 |E| 的填數字方法：
每一步都在圖中找度數最大的點，填上其在剩下的圖中之度數，然後將之從圖中去除
此頂點目前的鄰居在接下來填的數字必定小於此頂點目前的度數
這是因為這些鄰居的度數頂多跟此頂點一樣，但隨著此頂點的刪去，度數也就跟著少 1 了
較嚴格地來證明：
首先對於無邊的圖 G，這顯然是對的，因為都 (只能) 是 0，當然只有單點的圖也成立
假設對於所有頂點數為 n 的圖皆成立，接著考慮 |V| = n+1 的圖 G
令 x 為使 deg_G(v) 達到最大值的任一點，f' 為使 G-x 達到 t(G-x) 的某函數
取 f(v) = { deg_G(x)，若 v = x
{ f'(v)，若 v ≠ x
‧ 對於 v ≠ x，由於 f(x) = deg_G(x) ≧ deg_G(v) ≧ f(v)
故 f(v) = f'(v) ≧ #{u∈V-x: uv∈E(G-x), f(u) < f(v)}
= #{u∈V: uv∈E, f(u) < f(v)}
‧ 另一方面，對於 x，考慮與其相鄰的 v
f(v) ≦ deg_{G-x}(v) < deg_G(v) ≦ deg_G(x) = f(x)
因此 f(x) = #{u∈V: ux∈E, f(u) < f(v)}
最後 Σ_{v∈V} f(v) = f(x) + Σ_{v∈V-x} f(v) = f(x) + Σ_{v∈V-x} f'(v)
= deg_G(x) + |E(G-x)| = |E|
由數學歸納法得證
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.73.207 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1601253355.A.4B2.html
※ 編輯: arthurduh1 (140.109.73.207 臺灣), 09/28/2020 16:52:50
討論串 (同標題文章)
