图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
欧拉图与哈密顿图 欧拉图 ·哈密顿图 最短路问题与货郎担问题
2 欧拉图与哈密顿图 • 欧拉图 • 哈密顿图 • 最短路问题与货郎担问题
欧拉图的定义 定义:通过图中所有边一次且仅一次行遍图中所有顶点的通路称为 欧拉通路;通过图中所有边一次且仅一次行遍图中所有顶点的 回路称为欧拉回路; 具有欧拉回路的图称为欧拉图;具有欧拉通路,但无欧拉回路 的图称为半欧拉图 规定:平凡图(N是欧拉图 定义:经过所有顶点的通路称为生成通路 说明:欧拉图是图中经过所有边的简单的生成通路; 欧拉回路是经过所有边的简单的生成回路
3 欧拉图的定义 定义: 通过图中所有边一次且仅一次行遍图中所有顶点的通路称为 欧拉通路;通过图中所有边一次且仅一次行遍图中所有顶点的 回路称为欧拉回路; 具有欧拉回路的图称为欧拉图;具有欧拉通路, 但无欧拉回路 的图称为半欧拉图. 规定: 平凡图(N1)是欧拉图。 定义: 经过所有顶点的通路称为生成通路. 说明: 欧拉图是图中经过所有边的简单的生成通路; 欧拉回路是经过所有边的简单的生成回路
欧拉图的判别(无向图) 定理:无向图G是欧拉图,当且仅当G是连通图,且G中没有奇度顶点 证明:若G是平凡图,结论显然成立.下面假设G为非平凡图 设G=是含有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 = 是含有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中没有奇度顶点. 证明: (续)
欧拉图的判别(无向图) 定理:无向图G是欧拉图,当且仅当G是连通图,且G中没有奇度顶点 证明:(续) (充分性)由归纳假设可知:G’1,G'2;…,G都是欧拉图,因此, 都存在欧拉回路C(i=1.s) 现在将C还原即将删除的边重新加上),并从C上的某顶点v开 始进行遍历,每遇到v就行遍G中的欧拉回路Ci=1.s,最后, 回到v,得回路C”:vr…v1* 此回路C”经过G中每条边一次且仅一次。因此,C”是G中的欧 拉回路 所以,G为欧拉图
6 欧拉图的判别(无向图) (充分性.) 由归纳假设可知: G’1, G’2, …, G’s都是欧拉图, 因此, 都存在欧拉回路C’i(i = 1..s)。 现在将C还原(即将删除的边重新加上), 并从C上的某顶点vr开 始进行遍历, 每遇到vji*, 就行遍G’i中的欧拉回路C’i(i=1..s), 最后, 回到vr, 得回路C”: vr… vj1* … vj1* … vj2* … vj2* … vjs* … vjs* … vr。 此回路C”经过G中每条边一次且仅一次。因此, C”是G中的欧 拉回路。 所以, G为欧拉图。 定理: 无向图G是欧拉图, 当且仅当G是连通图, 且G中没有奇度顶点. 证明: (续)
半欧拉图的判别(无向图) 定理:无向图G是半欧拉图,当且仅当G是连通的,且G中恰有两个 奇度顶点 明 (必要性) 设G是m条边的n阶无向图。因为G为半欧拉图,因而G中存在欧 拉通路(但不存在欧拉回路 设r= v: e: v1…v1,e1V1为G中一条欧拉通路,vn≠v1。显然, G是连诵性。 v∈v(G,若V不在的端点出现,显然dv为偶数;若v在端点出 现过,则d()为奇数 因为r只有两个端点且不同,所以G中只有两个奇数顶点
7 半欧拉图的判别(无向图) 定理: 无向图G是半欧拉图, 当且仅当G是连通的, 且G中恰有两个 奇度顶点。 (必要性) 设G是m条边的n阶无向图。因为G为半欧拉图, 因而G中存在欧 拉通路(但不存在欧拉回路)。 设Γ = vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路, vi0 ≠ vim。显然, G是连通性。 ∀v ∈ V(G), 若v不在Γ的端点出现, 显然d(v)为偶数; 若v在端点出 现过, 则d(v)为奇数. 因为Γ只有两个端点且不同, 所以 G中只有两个奇数顶点。 证明:
半欧拉图的判别(无向图) 定理:无向图G是半欧拉图,当且仅当G是连通的,且G中恰有两个 奇度顶点。 证明:(续) 充分性) 设G的两个奇度顶点分别为u和v。对G加新边(uo,Vo),得G =GU(uo,vo),则G'是连通的且无奇度顶点的图 由前述定理可知,G”为欧拉图。因此,存在欧拉回路C,故,C ( Uo v)为G中一条欧拉通路 所以,G为半欧拉图
8 半欧拉图的判别(无向图) (充分性) 设G的两个奇度顶点分别为u0和v0。对G加新边(u0, v0), 得G’ = G∪(u0, v0), 则G’是连通的且无奇度顶点的图。 由前述定理可知, G’为欧拉图。因此, 存在欧拉回路C, 故, C － (u0, v0)为G中一条欧拉通路。 所以, G为半欧拉图。 定理: 无向图G是半欧拉图, 当且仅当G是连通的, 且G中恰有两个 奇度顶点。 证明: (续)
半欧拉图的判别(有向图) 定理:有向图D是欧拉图,当且仅当D是强连通的,且每个顶点 的入度都等于出度 定理:有向图D是半欧拉图,当且仅当D是单向连通的,且D中 恰有两个奇度顶点,其中一个的入度比出度大1,另一个 的出度比入度大1,而其余顶点的入度都等于出度 定理:G是非平凡的欧拉图,当且仅当G是连通的,且是若干个边不 重的圈之并
9 半欧拉图的判别(有向图) 定理: 有向图D是欧拉图, 当且仅当D是强连通的, 且每个顶点 的入度都等于出度。 定理: 有向图D是半欧拉图, 当且仅当D是单向连通的, 且D中 恰有两个奇度顶点, 其中一个的入度比出度大1, 另一个 的出度比入度大1, 而其余顶点的入度都等于出度。 定理: G是非平凡的欧拉图, 当且仅当G是连通的, 且是若干个边不 重的圈之并
欧拉图的性质:例子 例:设G是非平凡的且非环的欧拉图,证明 (1)(G)≥2 (2)yu,v∈V(G),u≠v,则G中都存在包含u和v的简单回路 证明: (1)由G是欧拉图,可知Ve∈E(G,存在圈C:e在C中。因此,p(Ge) p(G),所以,e不是桥。由e的任意性可知:(G)≥2,即G是2边-连通图 (2)u,veV(G),u≠V,由G的连通性可知:u和v之间必存在路径r1 设G’=G一E(I,则在G’中u与V还必连通,否则,u与v必处于G的不 同的连通分支中,这说明r1中存在G中的桥,这与(1)矛盾。 于是,在G中存在U到v的路径r2,显然1与I2边不重,这说明:u和v处 于由r1Ur2形成的简单回路上。 10
10 欧拉图的性质: 例子 (1) 由G是欧拉图, 可知 ∀e ∈ E(G), 存在圈C: e在C中。因此, p(G-e) = p(G), 所以, e不是桥。由e的任意性可知: λ(G) ≥ 2, 即G是2边-连通图。 (2) ∀u, v∈V(G), u ≠ v, 由G的连通性可知: u和v之间必存在路径Γ1。 设G’ = G − E(Γ1), 则在G’中u与v还必连通, 否则, u与v必处于G’的不 同的连通分支中, 这说明Γ1中存在G中的桥, 这与(1)矛盾。 于是, 在G’中存在u到v的路径Γ2, 显然Γ1与Γ2边不重, 这说明: u和v处 于由Γ1∪Γ2形成的简单回路上。 例: 设G是非平凡的且非环的欧拉图, 证明: (1) λ(G) ≥ 2 (2) ∀u, v ∈ V(G), u ≠v, 则G中都存在包含u和v的简单回路 证明: