15. 1 欧拉图 例 判断下列各图是否是 欧拉图。
(1)
(2)
(3)
(4)
集合与图论
(5)
(6)
1.18
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
(5)
(5)是一个非连通图，所以肯定不是 欧拉图。
集合与图论
1.19
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
(2)
(3)
设G是n(n>2)阶无向图，若对于G 中每一对不相邻的顶点u、v，均有：
d(u)+d(v) ≥n-1 则G中存在哈密尔顿通路。
集合与图论
1.44
哈尔滨工业大学软件学院 李东 副教授
定理15.7的推论 设G是n(n>2)阶无向简单图，若对于G
中每一对不相邻的顶点u、v，均有： d(u)+d(v) ≥n，
(1)
(2)
(3)
(4)
集合与图论
(6) (5)
1.11
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
(1)
(6)
上两图中，度数为奇数的顶点个数都 是4。所以根据定理15.2，它们不可能存 在欧拉通路，更无欧拉回路，因此都不是
欧拉图。
集合与图论
1.12
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
有哈密尔顿通路，但无哈密尔顿 回路，所以不是哈密尔顿图。
有哈密尔顿回路，所以 是哈密尔顿图。
(2)
集合与图论
1.30
哈尔滨工业大学软件学院 李东 副教授
(3) (4)
(5)
(6)
以上4图都有哈密尔顿回路，所以都
是哈密尔顿图。
集合与图论
1.31
哈尔滨工业大学软件学院 李东 副教授
15. 2 哈密尔顿图 例 判断下列各图是否是哈密尔顿图。
所以只具有哈密尔顿通路，而不具有哈密 尔顿回路的图不是哈密尔顿图，只是半哈密尔 顿图。
集合与图论
1.28
哈尔滨工业大学软件学院 李东 副教授
15. 2 哈密尔顿图 例 判断下列各图是否是哈密尔顿图。
(1)
(2)
(3)
(4)
集合与图论
(6) (5)
1.29
哈尔滨工业大学软件学院 李东 副教授
(1)
集合与图论
1.36
哈尔滨工业大学软件学院 李东 副教授
此条件只是哈密尔顿图的必要条件， 不满足上述条件的图，一定不是哈密尔顿 图。但满足的，也不一定是哈密尔顿图。
集合与图论
1.37
哈尔滨工业大学软件学院 李东 副教授
15. 2 哈密尔顿图
证明：因为G是哈密尔顿图,所以G
中存在哈密尔顿通路. 设C为一条哈密尔顿通路，则V1中的
证明：设v为图G的割点，令：V1={v}. 则p(G-V1) ≥2. 而|V1|=1.
所以由定理15.6可知：
有割点的图一定不是哈密尔顿图。
集合与图论
1.40
哈尔滨工业大学软件学院 李东 副教授
利用定理15.6及其推论判断如下 4图是否是哈密尔顿图。
a
u
v (1)
a (3)
b
c
集合与图论
b
d
c
(2) e
无向图G为欧拉图，当且 仅当G是连通图且无奇度顶点。
集合与图论
1.9
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
n 定理15.2
无向图G是半欧拉图当且 仅当G是连通的且G中恰有两 个奇度顶点。
集合与图论
1.10
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图 例 判断下列各图是否是 欧拉图。
集合与图论
1.26
哈尔滨工业大学软件学院 李东 副教授
15. 2 哈密尔顿图
从定义可以看出，存在哈密尔顿通 路（回路）的图一定是连通图。
具有哈密尔顿通路但不具有哈密尔顿回路
的图叫做半哈密尔顿图.
平凡图是哈密尔顿图.
集合与图论
1.27
哈尔滨工业大学软件学院 李东 副教授
哈密尔顿回路一定是哈密尔顿通路， 但哈密尔顿通路不一定是哈密尔顿回路。
(4)
1.41
哈尔滨工业大学软件学院 李东 副教授
u
有割点u,v，所以不是 哈密尔顿图。
v
(1)
a
b
d
c
令V1={a,b,c,d,e},则p(G-V1) =6 >|V1|=5,所以不是哈密尔顿图。
(2) e
集合与图论
1.42
哈尔滨工业大学软件学院 李东 副教授
a
(3)
令V1={a,b,c},则p(G-V1) =4
集合与图论
1.23
哈尔滨工业大学软件学院 李东 副教授
00
01
10
图D为欧拉图，因
11
为D是连通图，且
所有顶点的入度等
于出度(都等于2)。
集合与图论
1.24
哈尔滨工业大学软件学院 李东 副教授
15.2 哈密尔顿图
n 引子：“周游世界问题”
该问题是基于正十二面体的一个数学游戏：
是否存在经过所 有顶点一次且仅一次 的回路或通路？
则G中存在哈密尔顿回路，即G是哈密 尔顿图.
集合与图论
1.45
哈尔滨工业大学软件学院 李东 副教授
15. 2 哈密尔顿图
n 定理15.7的推论
设G是n(n>2)阶无向图，若
δ (G ) ≥ n ， 2
则G是哈密尔顿图。
集合与图论
1.46
哈尔滨工业大学软件学院 李东 副教授
集合与图论
1.21
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
(1)
此图为有向连通图，且所有顶点的 出度均等于入度。所以根据定理15.3的 推论，它们是 欧拉图。
集合与图论
1.22
哈尔滨工业大学软件学院 李东 副教授
例 设有向图D=<V,E>,其中V={vi|0≤i≤3}， E={ej|0≤j≤7}.若以i的二进制表示标记vi ， 则v0，v1，v2，v3分别记做00，01，10，11 。类似地，若以j的二进制表示标记ej ，则e0 ，e1，…，e7分别记做000，001，010， …,111。边abc从顶点ab到bc(a,b,c=0,1)， 例如，边001从00到01。试画出D的图形， 并证明它是 欧拉图。
(1)
(2)
(3)
(4)
集合与图论
(5)
(6)
1.32
哈尔滨工业大学软件学院 李东 副教授
(5)
此图明显不是哈密尔顿图。
集合与图论
1.33
哈尔滨工业大学软件学院 李东 副教授
(2)
(3)
此3图只有哈密尔顿通路， 但无哈密尔顿回路，所以不是 哈密尔顿图。
(6)
集合与图论
1.34
哈尔滨工业大学软件学院 李东 副教授
顶点在C上可能相邻，也可能不相邻. 即：p(C-V1) ≤|V1|. 由于C-V1是G-V1的子图，所以C-V1的连
通分支数不会超过G -V1的连通分支数.
所以：p(G-V1) ≤p(C-V1) ≤|V1|.
因此：p(G-V1)≤|V1|.
集合与图论
1.38
哈尔滨工业大学软件学院 李东 副教授
15. 2 哈密尔顿图
具有欧拉通路但不具有欧拉 回路的图叫做半欧拉图.
集合与图论
1.4
哈尔滨工业大学软件学院 李东 副教授
特别地，规定平凡图是欧拉图。
集合与图论
1.5
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
n 例，判断下列各图是否是 欧拉图。
集合与图论
1.6
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
集合与图论
1.16
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
n 定理15.4
一个有向图D是半欧拉图，当且仅当 D是单向连通的，且D中恰有两个奇度顶 点外，其余顶点的入度等于出度。
这两个奇度顶点中，一个顶点的入 度比出度大1。
另一个顶点的入度比出度小1。
集合与图论
1.17
哈尔滨工业大学软件学院 李东 副教授
n 定理15.6 的推论
设无向图G = <V, E>为半哈密尔顿 图，非空集合V1是V的任意真子集， 则：
p(G-V1) ≤|V1|+1 其中p(G-V1) 是从G中删除V1后， 所得图的连通分支数。
集合与图论
1.39
哈尔滨工业大学软件学院 李东 副教授
例15.4
设G为n阶无向连通图，证明：若G有 割点，则图G一定不是哈密尔顿图。
b
>|V1|,所以不是哈密尔顿图。
c
此图称为彼得森图，在数学上
已经证明其不存在哈密尔顿回路。
(4)
此图虽然满足对于任意的V1，有 p(G-V1) ≤|V1|，但由于其不存在哈密尔 顿回路，所以不是哈密尔顿图。
集合与图论
1.43
哈尔滨工业大学软件学院 李东 副教授
15. 2 哈密尔顿图
n 定理15.7
(4)
(5)
上两图中，度数为奇数的顶点个数 都是2。所以根据定理15.2，它们具有 欧拉通路，但无欧拉回路，因此都是半 欧拉图。
集合与图论
1.13
哈尔滨工业大学软件学院 李东 副教授
15. 1 欧拉图
(2)
(3)
上两图中，不存在度数为奇数的顶点 。所以根据定理15.2，它们均有欧拉通 路，且这些欧拉通路为欧拉回路，因此 它们都是欧拉图。