离散数学与复习题 张蕾 .ppt

第8章 欧拉图 本章学习目标 本章主要介绍了从实际问题引出的一个特殊的图：欧拉图。通过本章学习，读者应该掌握以下内容： （1）欧拉通路、欧拉回路、欧拉图和半欧拉图的概念 （2）欧拉图和半欧拉图的判定准则 主要内容 8.1 欧拉图 8.1.1 欧拉图的定义 8.1.2 欧拉图的判定 8.1.3 求欧拉回路的算法 8.1.4 欧拉图的应用 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 8.1 欧拉图 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5.2 带权图的关键路径 定理7.5.1 设PE={v|TE（v）已经算出}，TE=V-PE，若TE??，则存在u?TE，使得 ?PE 定义7.5.7 在保证收点vn的最早完成时间TE（vn）不增加的条件下，自发点v1最迟到达vi所需要的时间，称为vi的最晚完成时间，记作TL（vi）。 各项活动所允许的最迟的开工时间，其计算公式为： TL（vn）=TE（vn）， TL（vi）=, 其中 为vi的后继元素集合，wij为边vi，vj的权值。 7.5.2 带权图的关键路径 定理7.5.2 设PL={v|TL（v）已经算出}，TL=V-PL，若TL??，则存在v?TL，使得 ?PL 。 定理7.5.3 TS（vi）=0当且仅当vi处于关键路径上。 例7.5.2 计算图7.5-2中各顶点的最早、最晚及缓冲时间，并求出所有关键路径。 * 8.1.1 欧拉图的定义 定义 8.1.1 （1）通过图中所有边一次且仅一次行遍所有顶点的通路，称为欧拉通路； （2）通过图中所有边一次且仅一次行遍所有顶点的回路，称为欧拉回路； （3）具有欧拉回路的图，称为欧拉图； （4）具有欧拉通路但无欧拉回路的图，称为半欧拉图。 8.1.1 欧拉图的定义 在图8.1-1中，（a）存在欧拉通路，但不存在欧拉回路，因而它不是欧拉图。而（b）中存在欧拉回路，所以（b）是欧拉图。 8.1.2 欧拉图的判定 定理8.1.1 无向图是欧拉图，当且仅当是连通的，且中所有顶点的度数都是偶数。 推论 无向连通图中存在欧拉回路，当且仅当中所有顶点的度数都是偶数。 8.1.2 欧拉图的判定 定理8.1.2 无向图是半欧拉图，当且仅当是连通的，且只有两个顶点的度数为奇数，而其他顶点的度数为偶数。 证明 设图G中度数为奇数的顶点为u，v，在图G中附加一条新边，从而形成一个新图G’。于是，G有一条u与v间的欧拉通路，当且仅当G’有一条欧拉回路。这也就是说，G有一条u与v间的欧拉通路，当且仅当G’是连通的，且所有顶点的度数都是偶数，从而当且仅当G是连通的，且只有u,v的度数为奇数，而其余顶点的度数均为偶数。 推论 无向连通图中顶点与间存在欧拉通路，当且仅当中与的度数为奇数，而其他顶点的度数为偶数。 8.1.2 欧拉图的判定 图8.1-2 图8.1-3 8.1.2 欧拉图的判定 定理8.1.3 有向图是欧拉图，当且仅当是强连通的，且中每个顶点的入度都等于出度。 定理8.1.4 有向图是半欧拉图，当且仅当是单向连通的，且中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其他顶点的入度都等于出度。 8.1.3 求欧拉回路的算法 设G为欧拉图，一般说来，G中存在若干条欧拉回路，下面介绍一种求欧拉回路的算法—Fleury算法。算法如下： （1）任取v0∈V(G)，P0=V0令； （2）设Pi=v0e1v1e2 …eivi 已经行遍，按下面方法从E(G)-{e1,e2,…ei}中选取ei+1： （a） ei+1与vi相关联； （b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-(e1e2…ei)中的割边（桥）； （3）当（2）不能再进行时，算法停止。 8.1.3 求欧拉回路的算法 例如在图8.1-4中， 就是图的一条欧拉