欧拉图的判别(无向图) 定理:无向图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是连通的, 且是若干个边不 重的圈之并