8.4 Ore定理(1962)
Ore定理的内容是:
对于n个节点的简单图(n>2),如果每一对非相邻节点的度数和至少为n,那么这个图是哈密尔顿图。
这个定理其实是不实用的,条件太苛刻,但是作为一个著名的定理,这里我还是给出证明过程。首先一定要至少三个点,因为两点成环,必须存在平行边,这个就不需要证明了,下面正式进入证明环节。
利用反证法证明,首先假设满足上述条件的图G不是哈密尔顿图。既然不是哈密尔顿图,那么我们就增加边,让它慢慢变成哈密尔顿图。假设最后在x和y两点加了一条边,形成了哈密尔顿图,把这个图成为
G
l
a
s
t
G_{last}
Glast,而增加之前的成为
G
b
e
f
o
r
e
G_{before}
Gbefore。
所以在
G
b
e
f
o
r
e
G_{before}
Gbefore上x和y是不相连的。假设
G
b
e
f
o
r
e
G_{before}
Gbefore这条哈密尔顿路径是
z
1
z_1
z1到
z
n
z_n
zn。根据前面证明狄拉克定理用到的鸽笼原理,或者叫鸽巢原理。
z
1
z_1
z1到
z
n
z_n
zn之间有n-2个位置,但是他们入度和,或者说邻居总和是n,所以和狄拉克定理的证明一样,一定存在一个点是
x
0
x_0
x0的邻居而路径上下一个点是
x
n
x_n
xn的邻居。那么证明了
G
b
e
f
o
r
e
G_{before}
Gbefore就存在哈密尔顿环路,与假设矛盾。Q.E.D.(证明完毕)
可以说,Dirac定理是奥尔定理的一个特殊场景。但是仔细比较发现,Dirac定理发表于1952年,而Ore定理发表于1962年,整整十年时间,才从特殊到了一般。可见数学是一条崎岖坎坷的路。
相关文章
- 【SPOJ】Highways(矩阵树定理)
- Kuangbin【唯一分解定理】 西格玛函数
- (《机器学习》完整版系列)第12章 计算学习理论——12.7 定理的证明技巧(烧脑的数学,好玩的技巧)
- 考研数二第十三讲 从洛必达法则说起—微分中值定理在极限中的简单应用
- UVa 10294 Arif in Dhaka (First Love Part 2) (Polya定理)
- 高数 | 罗尔(Rolle)中值定理及其推广 证明
- 赛思互动:管理学最重要的八大定理
- 【bzoj5028】小Z的加油店 扩展裴蜀定理+差分+线段树
- 【poj2154】Color Polya定理+欧拉函数
- 【bzoj1441】Min 扩展裴蜀定理
- 【bzoj5056】OI游戏 最短路+矩阵树定理
- 【bzoj1965】 [Ahoi2005]SHUFFLE 洗牌 欧拉定理