第九章图.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第九章 图,9.1,图的基本概念,9.2,图中的通路、图的连通性和图的矩阵表示,9.3,带权图与带权图中的最短通路,9.4,欧拉图,9.5,哈密尔顿图,9.6,二部图,9.7,平面图与平面图的着色,例,假设,5,个教师共讲授,8,门课程。令课程和教师是图的顶点，只要某教师能够讲授某课程，就在该课程与该教师之间画一条边，如下图所示,：,课程,教师,二部图，或称二分图，也称偶图,定义：设,G=(V,E),是一个图，,若存在顶点集 的一个划分,V,1,V,2,，使得：,对于任意的,e,E,，,存在,v,1,V,1,，,v,2,V,2,满足,v,1,v,2,=e,则称（,V,1,，,V,2,）是图,G,的顶点的二分类。,称图,G,为二部图，或称二分图，也称偶图，,又称,G,为具有二分类（,V,1,，,V,2,）的偶图。,完全二部图,G=(V,E),是一个二部图，（,V,1,，,V,2,）是,G,的二分类，若对于任意的,v,1,V,1,，,v,2,V,2,，有,v,1,v,2,E,，,说,G,是一个完全二部图。,完全二部图,K,n,m,一个完全二部图,G,，（,V,1,，,V,2,）是它的二分类，,|V,1,|=n,，,|V,2,|=m,，记,G,为,K,n,m,。,图,9.17,两个完全二部图,定理的证明,：,“,”,先假设,G,是连通的。取定,v,0,V,，定义,V,的两个子集如下：,V,1,=v,i,v,i,到,v,0,的距离是偶数,，,V,2,=V,V,1,。,任取,e=v,i,v,j,E,。若,v,i,v,j,V,1,，由,V,1,的定义知，从,v,i,到,v,0,有一条初等通路，其长为偶数，而,v,0,到,v,j,也有一条长为偶数的初等通路，再加上边,v,i,v,j,，得到一条回路，此回路的长度是“偶数,+,偶数,+1”,，即为奇数，与题设矛盾。矛盾说明,v,i,与,v,j,不可能同时属于,V,1,。同样可以证明,v,i,与,v,j,不可能同时属于,V,2,，即,(V,1,，,V,2,),是,V,的一个二分类，也即,G,是一个二部图。,定理的证明：“,”,(,续,),如果,G,不连通，设,G,为,k,个独立的连通分枝（子图）。,对于,G,的每一个连通分枝，由上面的证明可以得到每一个独立子图的二分类，分别设为,(V,1,(1),V,2,(1),),，,，,(V,1,(k),V,2,(k),),。,令,V,1,(1),V,1,(2),V,1,(k),=V,1,，,V,2,(1),V,2,(2),V,2,(k),=V,2,，,则,G,是一个具有二分类（,V,1,，,V,2,）的二部图。,例,G=(V,E),是一个简单无向图。若,G,是一个二部图（偶图），且每一个顶点的度数都是,3,度，,V,1,V,2,是,G,作为二部图顶点集一个划分。证明,:|,V,1,|=|V,2,|,。,证明方法一,：根据二分图的定义知：,图共有,3|V,1,|,条边，每条边对应,2,个度数，,故图的总度数为,6|V,1,|.,根据图的定义知：图的总度数为,3|V,1,|+3|V,2,|=6|V,1,|,即,|V,1,|=|V,2,|,例,G=(V,E),是一个简单无向图。若,G,是一个二部图（偶图），且每一个顶点的度数都是,3,度，,V,1,V,2,是,G,作为二部图顶点集一个划分。证明,:|,V,1,|=|V,2,|,。,证明方法二,：根据二分图的定义知：,V,1,的每个顶点都是,3,度，故图共有,3|V,1,|,条边。,V,2,的每个顶点都是,3,度，故图也共有,3|V,2,|,条边。,于是,3|V,1,|=3|V,2,|,即,|V,1,|=|V,2,|,例,解,:,例,(,习题,9.26,p123),已知：,a,，,b,，,c,，,d,，,e,，,f,，,g,的下述事实：,(a),说汉语、日语；,(b),说日语、法语；,(c),说德语、法语、西班牙语；,(d),说汉语、德语、俄语、葡萄牙语；,(e),说俄语、朝语；,(f),说朝语、西班牙语；,(g),说葡萄牙语。,试问：能否将七个人分成两组，使同一组中没有两个人能互相交谈？并用图论方法，说明你的结论。,a,b,c,d,e,f,g,例,(,习题,9.26,p123),a,b,c,d,e,f,g,a,b,c,d,e,f,g,解：能！将顶点分成,a,c,e,g,与,b,d,f,这两组后，关系图可以表示成二分图的形式，即各组中没有两个人能互相交谈。,第九章 图,9.1,图的基本概念,9.2,图中的通路、图的连通性和图的矩阵表示,9.3,带权图与带权图中的最短通路,9.4,欧拉图,9.5,哈密尔顿图,9.6,二部图,9.7,平面图与平面图的着色,