作者arthurduh1 (arthurduh1)
看板puzzle
标题Re: [问题] 六角盖塔
时间Mon Sep 28 08:35:53 2020
将问题用图论的语言重新改写：
(*) 对於有顶点集 V、边集 E 的图 G
f: V → Z 满足 f(v) ≧ #{u∈V: uv∈E, f(u) < f(v)}
求 Σ_{v∈V} f(v) 的最大可能值 t(G)
# 跟绝对值一样，都是代表数个数
1F：→ LPH66: 每对相邻格子至多贡献 1 给两格之一 (可能没有贡献) 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://webptt.com/cn.aspx?n=bbs/puzzle/M.1601253355.A.4B2.html
※ 编辑: arthurduh1 (140.109.73.207 台湾), 09/28/2020 16:52:50