1、1/609.6 二部图 (一 ) 二部图(二 ) 完全二部图(三 )判定 定理2/60例假设 5个教师共讲授 8门课程。令课程和教师是图的顶点，只要某教师能够讲授某课程，就在该课程与该教师之间画一条边，如下图所示 ：课程教师3/60二部图（二分图、偶图）定义：设 G=(V,E)是一个图，若存在顶点集 的一个划分 V1, V2，使得：对于任意的 eE，存在 v1V1， v2V2满足v1, v2=e, 则称（ V1， V2）是图 G的顶点的二分类。称图 G为二部图，或称二分图，也称偶图，又称 G为具有二分类（ V1， V2）的偶图。4/60完全二部图G=(V, E) 是一个二部图，（ V1， V2
2、）是 G的二分类，若对于任意的 v1V1， v2V2，有v1,v2 E，说 G是一个完全二部图。5/60完全二部图 Kn,m一个完全二部图 G，（ V1， V2）是它的二分类，|V1|=n， |V2|=m，记 G为 Kn,m。图 9.17 两个完全二部图二部图的判别法 定理 无向图 G=是二部图当且仅当 G的所有回路的长度均是 偶数 。例 下述各图都是二部图 61 23 4 56 77/60例 (习题 9.26, p123)已知： a， b， c， d， e， f， g的下述事实：(a)说汉语、日语；(b)说日语、法语；(c)说德语、法语、西班牙语；(d)说汉语、德语、俄语、葡萄牙语；(e)说
3、俄语、朝语；(f)说朝语、西班牙语；(g)说葡萄牙语。试问：能否将七个人分成两组，使同一组中没有两个人能互相交谈？并用图论方法，说明你的结论。abcdefg8/60例 (习题 9.26, p123)abcdefgabcdefg解： 能！ 将顶点分成 a,c,e,g与 b,d,f这两组后，关系图可以表示成二分图的形式，即各组中没有两个人能互相交谈。9/609.7 平面图与平面图的着色(一 ) 平面图的定义(二 ) 欧拉公式 (定理 1)(三 ) 两种必要条件 (定理 2定理 3)(四 ) 充分必要条件 (库拉道夫斯基定理 )(五 ) 四色猜想(六 ) 对偶图(七 ) 五色定理10/60平面图的问题一个怎样的图，可以边不相交的画在一块平面上 ?
