第九章图.ppt

《第九章图.ppt》由会员分享，可在线阅读，更多相关《第九章图.ppt（15页珍藏版）》请在三一办公上搜索。

1、第九章 图,9.1 图的基本概念9.2 图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路9.4 欧拉图9.5 哈密尔顿图 9.6 二部图 9.7 平面图与平面图的着色,例,假设5个教师共讲授8门课程。令课程和教师是图的顶点，只要某教师能够讲授某课程，就在该课程与该教师之间画一条边，如下图所示：,课程,教师,二部图，或称二分图，也称偶图,定义：设G=(V,E)是一个图，若存在顶点集 的一个划分V1,V2，使得：对于任意的eE，存在v1V1，v2V2满足 v1,v2=e,则称（V1，V2）是图G的顶点的二分类。称图G为二部图，或称二分图，也称偶图，又称G为具有二分类（V1，

2、V2）的偶图。,完全二部图,G=(V,E)是一个二部图，（V1，V2）是G的二分类，若对于任意的v1V1，v2V2，有 v1,v2 E，说G是一个完全二部图。,完全二部图Kn,m,一个完全二部图G，（V1，V2）是它的二分类，|V1|=n，|V2|=m，记G为Kn,m。,图9.17 两个完全二部图,定理,一个图是二部图当且仅当它的所有回路的长度均是偶数。,是,不是,定理的证明：“”,如果 是二部图，（V1，V2）是它的二分类。令（vi0，vi1，vi(l-1)，vi0）是G中的一条长度为l的回路。不失一般性，设 vioV1。因此，由二部图的定义知 vi0，vi2，vi(l-2)V1，而 vi1

3、，vi3，vi(l-1)V2，所以,l-1 是奇数，即 l是偶数。,定理的证明：“”,先假设G是连通的。取定v0V，定义V的两个子集如下：V1=vivi 到v0的距离是偶数，V2=VV1。任取e=vi,vjE。若vi,vjV1，由V1的定义知，从vi到v0有一条初等通路，其长为偶数，而v0到vj也有一条长为偶数的初等通路，再加上边vi,vj，得到一条回路，此回路的长度是“偶数+偶数+1”，即为奇数，与题设矛盾。矛盾说明 vi与vj不可能同时属于V1。同样可以证明vi与vj不可能同时属于V2，即(V1，V2)是V的一个二分类，也即G是一个二部图。,定理的证明：“”(续),如果G不连通，设 G为

4、k个独立的连通分枝（子图）。对于G的每一个连通分枝，由上面的证明可以得到每一个独立子图的二分类，分别设为(V1(1),V2(1)，(V1(k),V2(k)。令 V1(1)V1(2)V1(k)=V1，V2(1)V2(2)V2(k)=V2，则G是一个具有二分类（V1，V2）的二部图。,例 G=(V,E)是一个简单无向图。若G是一个二部图（偶图），且每一个顶点的度数都是3度，V1,V2是G作为二部图顶点集一个划分。证明:|V1|=|V2|。,证明方法一：根据二分图的定义知：图共有3|V1|条边，每条边对应2个度数，故图的总度数为6|V1|.根据图的定义知：图的总度数为 3|V1|+3|V2|=6|V

5、1|即|V1|=|V2|,例 G=(V,E)是一个简单无向图。若G是一个二部图（偶图），且每一个顶点的度数都是3度，V1,V2是G作为二部图顶点集一个划分。证明:|V1|=|V2|。,证明方法二：根据二分图的定义知：V1的每个顶点都是3度，故图共有3|V1|条边。V2的每个顶点都是3度，故图也共有3|V2|条边。于是 3|V1|=3|V2|即|V1|=|V2|,例,解:,例(习题9.26,p123),已知：a，b，c，d，e，f，g的下述事实：(a)说汉语、日语；(b)说日语、法语；(c)说德语、法语、西班牙语；(d)说汉语、德语、俄语、葡萄牙语；(e)说俄语、朝语；(f)说朝语、西班牙语；(g)说葡萄牙语。试问：能否将七个人分成两组，使同一组中没有两个人能互相交谈？并用图论方法，说明你的结论。,例(习题9.26,p123),解：能！将顶点分成a,c,e,g与b,d,f这两组后，关系图可以表示成二分图的形式，即各组中没有两个人能互相交谈。,第九章 图,9.1 图的基本概念9.2 图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路9.4 欧拉图9.5 哈密尔顿图 9.6 二部图 9.7 平面图与平面图的着色,