第11章 特殊图 电子科大离散数学内部教学课件.ppt

第11章 特殊图 11.0 内容提要 几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图； 欧拉图、哈密顿图、偶图、平面图的判定； 偶图的匹配、图的着色； 欧拉图、哈密顿图、偶图、平面图的应用 10.1 本章学习要求 11.2 欧拉图 11.2.1 欧拉图的引入与定义 定义11.2.1 设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为欧拉图(Eulerian Graph)。 规定：平凡图为欧拉图。 以上定义既适合无向图，又适合有向图。 欧拉通路和欧拉回路的特征 欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路； 欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路。 如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。 例11.2.1 判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？ 11.2.2 欧拉图的判定 定理11.2.1 无向图G = V, E具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。 分析 只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。 证明 若G为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。 必要性： 设G具有一条欧拉通路L = ，则L经过G中的每条边，由于G中无孤立结点，因而L经过G的所有结点，所以G是连通的。 对欧拉通路L的任意非端点的结点 ，在L中每出现 一次，都关联两条边 和 ，而当 重复出现时，它又关联另外的两条边，由于在通路L中边不可能重复出现，因而每出现一次都将使获得2度。若在L中重复出现p次，则deg( )= 2p。 若端点 ≠ ，设 、 在通路中作为非端点分别出现p1和p2次，则 deg( )= 2p1+1，deg( ) = 2p2+1 因而G有两个度数为奇数的结点。 若端点 = ，设在通路中作为非端点出现p3次，则 deg( )= 1+2p3+1 = 2(p3+1) 因而G无度数为奇数的结点。 充分性：构造性证明。 我们从两个奇度数结点之一开始(若无奇度数结点，可从任一结点开始)构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终(若无奇度数结点，则以回到原出发点而告终)。如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，我们去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。 因为原来的图是连通的，因此，这个子图必与我们已经过的通路在一个或多个结点相接。从这些结点中的一个开始，我们再通过边构造通路，因为结点的度数全是偶数，因此，这条通路一定最终回到起点。我们将这条回路加到已构造好的通路中间组合成一条通路。如有必要，这一过程重复下去，直到我们得到一条通过图中所有边的通路，即欧拉通路。 由定理11.2.1的证明知：若连通的无向图有两个奇度数结点，则它们是G中每条欧拉通路的端点。 结论 推论11.2.1 无向图G = V, E具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。 定理11.2.2 有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。 推论11.2.2 有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。 欧拉通路与欧拉回路判别准则 对任意给定的无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。 利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有4个结点的度数均为奇数；也很容易得到例11.2.1的结论。 定义11.2.2 设G = V, E，e∈E，如果 p(G-e)＞p(G) 称e为G的桥(Bridge)或割边(Cut edge)。 显然，所有的悬挂边都是桥。 Fleury算法 算法11.2.1 求欧拉图G = V, E的欧拉回路的Fleury算法： （1）