离散数学 欧拉图的判别法 定理131(1)无向图G是欧拉图当且仅当G是连通的且没有奇 度顶点 (2)无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度 顶点 (3)有向图D是欧拉图当且仅当D是强连通的且每个顶点的入 度等于出度 (4)有向图D是半欧拉图当且仅当D是单向连通的且恰有两个 奇度顶点,其中一个顶点的入度比出度大1,另一个顶点出度 比入度大1,其余顶点的入度等于出度 例1设G是非平凡的欧拉图,则G)≥2 证只需证明G的任意一条边e都不是桥设C是一条欧拉回路, e在C上,因而G-e仍是连通的,故e不是桥5 欧拉图的判别法 定理13.1 (1) 无向图G是欧拉图当且仅当G是连通的且没有奇 度顶点． (2) 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度 顶点． (3) 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入 度等于出度． (4) 有向图D是半欧拉图当且仅当D是单向连通的且恰有两个 奇度顶点, 其中一个顶点的入度比出度大1, 另一个顶点出度 比入度大1, 其余顶点的入度等于出度． 例1 设G是非平凡的欧拉图，则(G)2. 证 只需证明G的任意一条边e都不是桥. 设C是一条欧拉回路, e在C上，因而G−e仍是连通的，故e不是桥．