第6章特殊的图

第6章特殊的图教学要求了解二部图的概念了解欧拉图的概念了解哈密顿图的概念了解平面图的概念6.1二部图（仅讨论无向图）1.二部图与完全二部图：P140定义6.1问题：给定一个图，判断它是否是二部图？定理：P140定理6.12.匹配，极大匹配，最大匹配，完美匹配：P140定义6.23.完备匹配：P140定义6.3判定完备匹配的充要条件：P141定理6.2和定理6.34.二部图的应用：解决分配问题

例1P141例6.1

例2在新学期开始时，某大学的计算机系对课程进行安排，下表给出了计算机系教师能承担的课程情况,判定是否所有的课程都能有教师承担，并给出一种排课方案教师承担的课程赵老师(z)数据库原理(DB1)、大型数据库(DB2)、计算机组成原理(O)

钱老师(q)数据库原理(DB1)、大型数据库(DB2)、数据结构(D)

孙老师(s)数据库原理(DB1)、大型数据库(DB2)、数据结构(D)、Java(J)

李老师(l)Java(J)冯老师(f)数据结构(D)、Java(J)6.2欧拉图(对所有边的环游问题）1.欧拉通路、欧拉回路：P142定义6.4

注意：允许某个顶点通过两次以上，但每条边只能经过一次问题：无向图欧拉通路、欧拉回路的判别？无向图欧拉路的判别：P142定理6.4(欧拉路的充要条件）有向图欧拉路的判别：P142定理6.52.欧拉图：存在欧拉回路的图3.欧拉图的应用acdeb例：设某城市的街道布局如左图所示，每条边代表一条特定街道的一段街区，每个结点代表街区间的交点。扫雪车车库位于结点d，证明存在一条路线使得扫雪车清扫每个街区恰好一次且清扫完最后一个街区正好返回车库。同时为这个扫雪车找出完成任务的路线6.3哈密顿图（对所有点的环游问题）1.哈密顿通路与回路：P144定义6.5哈密顿图的判别：世界难题！2.哈密顿图：存在哈密顿回路的图3.哈密顿图的必要条件：P144定理6.66.4平面图（无向图）1.平面图的基本概念举例：设有一个电路有六个元件，三个分为一组，连接如（a）图，是否有这样的接线法，使得导线互不交叉？平面图的定义：P146定义6.62平面图的区域：P146定义6.7相关概念：外部面，内部面，边界，次数deg（R）（1）（2）3.平面图中的数量问题（1）P146定理6.9（描述平面图中面的次数与边数的数量关系）（2）欧拉公式（描述平面图中边,顶点及区域数量的关系）

n-m+r=2其中：n为平面图中的顶点数，m为边数，r为面数由欧拉公式可推得：定理1：设G为有v个结点e条边的连通平面图，若v≥3，则e≤3v-6由定理1可证明K5为非平面图定理2：设G为一个平面简单连通图，其结点数v≥4，边数为e，且G不以K3为其子图，则e≤2v-4由定理2可证明K3,3为非平面图说明：同一个平面图可以有不同形状的平面嵌入,它们是同构的4.平面图的判别：库拉托夫斯基定理两种对图的同胚操作：（两种操作是互逆的）⑴

对边e的切割操作。设G中有边e=(u,v)，取消e边，增加顶点w，以及边e1=(u,w),边e2=(w,v)⑵对顶点v的贯通操作。设G中有二度顶点v，它是边e1=(u,v),边e2=(v,w)的共同端点，取消顶点v，以及边e1，边e2，增加边e=(u,w)例：a为图G，b，c分别是边e切割和顶点v贯通操作的结果库拉托夫斯基定理：P149定理6.13和定理6.145阶无向完全图K5无向完全二部图K3,3例：下图a为一非平面图，b是a的子图，c为经同胚操作后的图，可证c为二部图，且为K3,3

5.对偶图与地图着色（1）对偶图的定义：P150定义6.11（2）对平面连通图G构造其对偶图G*的方法：a.在G的每一个面ri的内部作一个G*的顶点vi*b.若G中面ri与rj有公共边界，那么过边界的每一边ek作关联vi*与vj*的一条边ek*，ek*与G*的其他边不相交c.当ek为面ri的边界而非ri与其他面的公共边界时，作vi*的一条环与ek相交（且仅交于一处）。所作的环不与G*的边相交(3)地图的着色问题地图的着色可以用平面图的着色来刻画，而平面图的着色可以转换为同等的结点着色问题例：给出平面图G，对图G着色可使用Welch-Powell算法（4）四色定理：任意平面图都是4可着色的小结二部图的判别欧拉图的判别人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋