六角蓋塔 - 拼圖

將問題用圖論的語言重新改寫：

(*) 對於有頂點集 V、邊集 E 的圖 G

f: V → Z 滿足 f(v) ≧ #{u∈V: uv∈E, f(u) < f(v)}

求 Σ_{v∈V} f(v) 的最大可能值 t(G)

# 跟絕對值一樣，都是代表數個數



以上便是在說明上界 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|

由數學歸納法得證


--