图的遍历性与可平面性.PPT

第十一章 图的遍历性与可平面性 11.1 欧拉图 1727年欧拉(Euler, 1707-1783)的一个朋友告诉他一个令许多人感到困惑问题：在哥尼斯堡(K?nisberg，东普鲁士故都)，有七座桥将普莱格尔(Pregel)河中的克奈芳福岛(kneiphof)以及河岸连接起来，岛上建有大教堂和康德(Kant)的墓，游人要通过这些桥在小岛与河岸之间走过，如图所示。如果从 A, B, C, D四个地点中任何一点出发，是否能经过每一座桥恰好一次，再回到原地？ 定义11.1.1　设L为图G的一条链，若L包含G的所有边，则称L为G的欧拉链； 若G的欧拉链 L是闭链，则称L为G的欧拉闭链；若G中含有一条欧拉闭链，则称图G为欧拉图。 若欧拉图G没有孤立点，则G是连通的。 定理11.1.1 设G为连通图，则G为欧拉图的充要条件是G中每个顶点都是偶度点。 证 必要性 设L为图G的一条欧拉闭链，v为G的任意一个顶点，L经过v点k次，则L每次经过v点都要有进有出，即L每次经过都使顶点v的度数增加2，故d(v)=2k。 充分性 对图G的边数用归纳法。 首先，若图G中只有3条边，则命题显然成立。 然后，对于一般情形，由图G中每个顶点都是偶度点可知G中一定有一个圈C。 从G中删去C的全部边后的图记为G’, 即G’=G-EC的连通分支记为G1, G2, ?, Gk 每个连通分支Gi 都与圈C有公共的顶点 vi (i =1, 2, ?, k), 又因为在圈C上的顶点的度数都是2，所以在G’中每个顶点的度数都是G中对应顶点的度数减去2。于是图G’中的每个顶点仍都是偶度点,当然Gi中每个顶点也都是偶度点。 例11.1.1 求欧拉图G的欧拉闭链。 推论11.1.1 设G为连通图，则G是欧拉图的充要条件是G为若干个边不交的圈的并。 推论11.1.2 设G为连通图，则G中有欧拉链的充分必要条件是G中至多有两个奇度点。 证 首先我们知道任何图的奇度点的个数必是偶数。 必要性：设G中有欧拉链L，其端点为u和v，则与定理11.1.1必要性的证明同样地有G的顶点，除u和v以外，都是偶度点。 充分性：若图G中没有奇度点，则由定理11.1.1知，G为欧拉图，即G中有一条欧拉闭链，故G中有一条欧拉链；若图G中有2个奇度点u和v，可设图G’=G+(u, v)，则G’为欧拉图，故G’有一条欧拉闭链，而这条欧拉闭链在G中就是一条欧拉链。 定义11.1.2 设 L为有向图G中的一条链， 若L包含G的所有弧，则称L为G的欧拉有向链； 若L是包含G的所有弧的有向闭链，则称L为G的欧拉有向闭链； 若G中有一条欧拉有向闭链，则称G为欧拉有向图。 当欧拉有向图G连通时，有向图G必是强连通的。 推论11.1.3 设G为弱连通有向图，则G是欧拉有向图的充要条件是G为若干个弧不重的圈的并。 推论11.1.4 设G为弱连通有向图，则G中有欧拉有向链的充要条件是G中至多有两个奇度点，并且其中一个是出度比入度多1，另一个是出度比入度少1。 例11.2.2 若给无向图G的每条边指定一个方向而成为一条弧，并使所得的有向图（仍记为G）成为强连通图，则称G为可定向的。试证明任意一个欧拉图G是可定向的。 证 设G为欧拉图，则G中含有一条欧拉闭链L。我们可给闭链L上的每条边指定一个方向，使L上任意两条邻接的边都取相同的方向，即使得与两条邻接的边都关联的顶点既是其中一条边的起点，又是另一条边的终点。这样就给G的每条边都指定了一个方向，而L就是G中一条欧拉有向闭链，故G是强连通的。 * * A B C D A D B C 根据归纳法假设可知, 每个Gi都是欧拉图于是都有一条欧拉闭链Li 。当然，顶点vi闭链Li上。 并集C∪L1∪L2∪?∪Lk就是图G的一条欧拉闭链。 v1 v2 vk-1 ? ? vk 1 2 3 4 5 欧拉图G *