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