文档介绍:图论及其应用
应用数学学院
1
本次课主要内容
(二)、E图和H图的关系
超哈密尔顿图问题
(一)、超H图与超H迹
2
定义1 若图G是非H图,但对于G中任意点v,都有G-v是H图,则称G是超H图。
(一)、超H图与超H迹
定理1 彼得森图是超H图。
1
7
6
5
4
3
2
彼得森图
10
9
8
证明: (1) 证明彼得森图是非H图。
3
若不然,设C是G的H圈。
1
6
5
4
3
2
7
彼得森图
10
9
8
又对于边28,23来说,在前面情况下,必有一条在C中。分两种情形讨论。
对于边12, 17,15来说,必然有两条边在C中。不失一般性,假定17,12在C中,那么,56,54也必然在C中。
4
1
6
5
4
3
2
7
彼得森图
10
9
8
但这样得到圈:17(10)821。所以该情形不能存在。
情形1:假如28在C中,则39,34在C中,从而7(10), 8(10)在C中
5
但这样得到圈:123971。所以该情形也不能存在。
情形2:假如23在C中,则86,8(10)在C中,从而39, 79在C中.
1
6
5
4
3
2
7
彼得森图
10
9
8
1
6
5
4
3
2
7
彼得森图
10
9
8
上面推理说明,G中不存在H圈,即彼得森图是非H图。
6
由对称性,只需考虑下面两种情形: (a) G-1,(b)G-6
(2) 证明对任意点v,G-v是H图。
(a) G-1中有H圈:54328(10)7965
3
6
5
4
2
10
7
G-1
9
8
(b) G-6中有H圈:54397(10)8215
1
5
4
3
2
7
G-6
10
9
8
由(1)与(2),G是超H图。
7
定义2 若G中没有H路,但是对G中任意点v,G-v存在H路,则称G是超可迹的。
数学家加莱曾经猜想:不存在超可迹的图。但该猜想被Horton和Thomassen以构图的方式否定了。
定理2 Thomassen图是超可迹图。
a
b
d
e
f
c
Thomassen图
Ⅰ
Ⅱ
Ⅲ
Ⅳ
8
定理证明分为两部分: (1) 证明G中不存在H路;(2) 证明对G中任意点v,有G-v存在H路。
(1) 证明G中不存在H路。
如图所示,将G用虚线分成对称的4部分:Ⅰ,Ⅱ,Ⅲ,Ⅳ 。
a
b
d
e
f
c
Thomassen图
Ⅰ
Ⅱ
Ⅲ
Ⅳ
假设G有H路P,设该路的起点为α,终点为β。
不失一般性,设α∈ Ⅰ∪{a}。
断言1: Ⅰ∪{a} 中不存在以a , c , d三点中任意两点为端点的H路。
若不然,将推出彼得森图是H图。
9
a
b
d
e
f
c
Thomassen图
Ⅰ
Ⅱ
Ⅲ
Ⅳ
断言2: Ⅰ∪Ⅱ ∪ {a, b} 中不存在以a 为端点的H路。
若不然,设Q是一条以a为起点的Ⅰ∪Ⅱ ∪ {a, b} 中的H路。那么,从a出发,沿着该路行走有两种可能: (1) 遍历了Ⅰ中所有点之后,从c或d进入Ⅱ,但这形成了Ⅰ ∪{a} 中的以a, c或a, d为端点的H路,与断言1矛盾!
(2) 没有遍历完Ⅰ ∪{a} 中的顶点,假若从c进入Ⅱ,那么,必须遍历完Ⅱ ∪ {b} 的所有顶点后,才能从e进入Ⅰ。但这也会与断言1产生矛盾。
10