文档介绍：第8章欧拉图本章学****目标本章主要介绍了从实际问题引出的一个特殊的图:欧拉图。通过本章学****读者应该掌握以下内容: (1 )欧拉通路、欧拉回路、欧拉图和半欧拉图的概念(2)欧拉图和半欧拉图的判定准则主要内容 欧拉图 欧拉图的定义 欧拉图的判定 求欧拉回路的算法 欧拉图的应用 欧拉图 欧拉图的定义定义 (1 )通过图中所有边一次且仅一次行遍所有顶点的通路,称为欧拉通路; (2 )通过图中所有边一次且仅一次行遍所有顶点的回路, 称为欧拉回路; (3)具有欧拉回路的图,称为欧拉图; (4)具有欧拉通路但无欧拉回路的图,称为半欧拉图。 欧拉图 欧拉图的定义在图 -1 中,( a) 存在欧拉通路,但不存在欧拉回路,因而它不是欧拉图。而( b) 中存在欧拉回路,所以( b)是欧拉图。(a) (b) v 1v 4 v 2v 3 v 4 v 1 v 2v 欧拉图 欧拉图的判定定理 无向图是欧拉图,当且仅当是连通的,且中所有顶点的度数都是偶数。推论无向连通图中存在欧拉回路,当且仅当中所有顶点的度数都是偶数。 欧拉图 欧拉图的判定定理 无向图是半欧拉图,当且仅当是连通的,且只有两个顶点的度数为奇数,而其他顶点的度数为偶数。证明设图 G中度数为奇数的顶点为 u,v,在图 G中附加一条新边,从而形成一个新图 G’。于是, G有一条 u与v间的欧拉通路,当且仅当 G’有一条欧拉回路。这也就是说, G 有一条 u与v间的欧拉通路,当且仅当 G’是连通的,且所有顶点的度数都是偶数,从而当且仅当 G是连通的,且只有 u,v 的度数为奇数,而其余顶点的度数均为偶数。推论无向连通图中顶点与间存在欧拉通路,当且仅当中与的度数为奇数,而其他顶点的度数为偶数。 欧拉图 欧拉图的判定 a bc d v 1v 2 v 3v 4 v 5v 6 (a) (b) v 1v 4 v 2v 3图 -2 图 -3 欧拉图 欧拉图的判定定理 有向图是欧拉图,当且仅当是强连通的,且中每个顶点的入度都等于出度。定理 有向图是半欧拉图,当且仅当是单向连通的, 且中恰有两个奇度顶点,其中一个的入度比出度大 1, 另一个的出度比入度大 1,而其他顶点的入度都等于出度。 欧拉图 求欧拉回路的算法设G 为欧拉图,一般说来, G 中存在若干条欧拉回路,下面介绍一种求欧拉回路的算法— Fleury 算法。算法如下: (1)任取 v 0∈ V(G) ,P 0 =V 0令; (2 )设 P i =v 0e 1v 1e 2 …e iv i 已经行遍,按下面方法从 E(G)- {e 1,e 2,…e i}中选取 e i+1: (a)e i+1与v i相关联; (b) 除非无别的边可供行遍,否则 e i+1不应该为 G i =G- (e 1e 2…e i)中的割边(桥); (3)当( 2)不能再进行时,算法停止。