欧拉图的判别(无向图) 定理:无向图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中没有奇度顶点. 证明: (续)