图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
欧拉图与哈密顿图 欧拉图 ·哈密顿图 最短路问题与货郎担问题
2 欧拉图与哈密顿图 • 欧拉图 • 哈密顿图 • 最短路问题与货郎担问题
欧拉图的定义 定义:通过图中所有边一次且仅一次行遍图中所有顶点的通路称为 欧拉通路;通过图中所有边一次且仅一次行遍图中所有顶点的 回路称为欧拉回路; 具有欧拉回路的图称为欧拉图;具有欧拉通路,但无欧拉回路 的图称为半欧拉图 规定:平凡图(N是欧拉图 定义:经过所有顶点的通路称为生成通路 说明:欧拉图是图中经过所有边的简单的生成通路; 欧拉回路是经过所有边的简单的生成回路
3 欧拉图的定义 定义: 通过图中所有边一次且仅一次行遍图中所有顶点的通路称为 欧拉通路;通过图中所有边一次且仅一次行遍图中所有顶点的 回路称为欧拉回路; 具有欧拉回路的图称为欧拉图;具有欧拉通路, 但无欧拉回路 的图称为半欧拉图. 规定: 平凡图(N1)是欧拉图。 定义: 经过所有顶点的通路称为生成通路. 说明: 欧拉图是图中经过所有边的简单的生成通路; 欧拉回路是经过所有边的简单的生成回路
欧拉图的判别(无向图) 定理:无向图G是欧拉图,当且仅当G是连通图,且G中没有奇度顶点 证明:若G是平凡图,结论显然成立.下面假设G为非平凡图 设G=<V,E>是含有m条边的n阶非平凡无向图,其中:V={v1 (必要性) 因为G为欧拉图,所以G中存在欧拉回路。设C是G中的欧拉 匈∈VvV都在C上,因此,v和是连通的,所以G为连通 路,Vv; 又v1∈V,v在C上每出现一次获得2度。若出现k次就获得2k 度,即:dv)=2k,所以,G中无奇度顶点
4 欧拉图的判别(无向图) 定理: 无向图G是欧拉图, 当且仅当G是连通图, 且G中没有奇度顶点. (必要性.) 因为G为欧拉图, 所以G中存在欧拉回路。设C是G中的欧拉回 路, ∀vi, vj ∈ V, vi, vj都在C上, 因此, vi和vj是连通的, 所以G为连通 图. 又∀vi ∈ V, vi在C上每出现一次获得2度。若出现k次就获得2k 度, 即: d(vi) = 2k, 所以, G中无奇度顶点。 证明: 若G是平凡图, 结论显然成立. 下面假设G为非平凡图. 设G = <V, E>是含有m条边的n阶非平凡无向图, 其中: V = { v1, v2, …, vn }
欧拉图的判别(无向图) 定理:无向图G是欧拉图,当且仅当G是连通图,且G中没有奇度顶点 证明:(续) (充分性) 由G为非平凡的连通图可知,G中边数m≥1。对m作归纳 (1)m=1时,由G的连通性和无奇度顶点可知,G只能是一个环,因 此,G为欧拉图 (2)设m≤k(k≥1)时,结论成立,要证明m=K+1时,结论也成立 由G的连通性和无奇度顶点可知:8(G)≥2。又由扩大路径法可以 证明G中存在长度大于或等于3的圈 设C为G中一个圈,删除C上的全部边,得G的生成子图G’。设G有 s个连通分支G'1,G'2,…,G,每个连通分支至多有k条边,且无奇度顶 点,并且设G与c的公共顶点为v(=1s) 5
5 欧拉图的判别(无向图) (充分性.) 由G为非平凡的连通图可知, G中边数m ≥ 1。对m作归纳。 (1) m = 1时, 由G的连通性和无奇度顶点可知, G只能是一个环, 因 此, G为欧拉图。 (2) 设m ≤ k(k ≥ 1)时, 结论成立．要证明m = K+1时, 结论也成立。 由G的连通性和无奇度顶点可知: δ(G) ≥ 2。又由扩大路径法可以 证明G中存在长度大于或等于3的圈。 设C为G中一个圈, 删除C上的全部边, 得G的生成子图G’。设G’有 s个连通分支G’1, G’2, …, G’s, 每个连通分支至多有k条边, 且无奇度顶 点, 并且设G’i与C的公共顶点为vji*(i = 1..s)。 定理: 无向图G是欧拉图, 当且仅当G是连通图, 且G中没有奇度顶点. 证明: (续)