第8章 几种典型图(4}.pptVIP

第10章 几种典型图 10.1 欧拉图 10.2 哈密顿图 10.3 平面图 10.4 二分图 10.5 例题选解 习 题 十 8.4 二 分 图 定义8.4.1 若无向图G=〈V，E〉的顶点集V能分成两个子集V1和V2，满足 （1）V=V1∪V2，V1∩V2=； （2）e=（u，v）∈E，均有u∈V1，v∈V2。则称G为二分图，V1和V2称为互补顶点子集，常记为G=〈V1，V2，E〉。如果V1中每个顶点都与V2中所有顶点邻接，则称G为完全二分图，并记为Kr，s，其中r=|V1|，s=|V2|。 例如，图8.4.1中的三个图均是二分图，其中图（b）是完全二分图K3，3，图（c）是K2，4。 显然，在完全二分图中Kr，s中，顶点数n=r+s，边数m=rs。 一个无向图如果能画成上面的样式，很容易判定它是二分图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二分图，如图8.4.2中（a）可改画成图（b），图（c）可改画成图（d）。可以看出，它们仍是二分图。 定理8.4.1 非平凡无向图G是二分图当且仅当G中无奇数长度的回路。 证明 先证必要性。设G=〈V1，V2，E〉为二分图，对G中任一长度为k的回路c：vi1vi2…vikvi1，不妨假设vi1∈V1，则必有vi2∈V2，vi3∈V1，…，即下标为奇数的顶点属于V1，下标为偶数的顶点属于V2，因为（vik，vi1）∈c，所以k为偶数。因此，G中任一回路的长度为偶数。 再证充分性。设G中无奇数长度的回路，不妨设G是连通图，将G的顶点集V按下面要求分成两个子集V1和V2： V1={vi|vi∈V且vi与某一给定顶点v0的距离是偶数}，V2=V1-V2 【例8.4.1】 六名间谍a，b，c，d，e，f被擒，已知a懂汉语、法语和日语，b懂德语、俄语和日语，c懂英语和法语，d懂西班牙语，e懂英语和德语，f懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。 解 以六人a，b，c，d，e，f为顶点，在有共同懂得语言的人的顶点间连边得图G（如图8.4.3（a）所示），因为G中没有奇圈，所以G是二分图（如图8.4.3（b）所示），故至少应有两间房间即可。 【例8.4.2】 设（n,m）图G是二分图，证明m≤n2/4。 证明 设G=〈V1，V2，E〉，|V1|=n1，|V2|=n2，则n=n1+n2，m≤n1n2。 由（a-b）2=a2+b2-2ab≥0，得 二分图的主要应用是匹配，“匹配”是图论中的一个重要内容，它在所谓“人员分配问题”和“最优分配问题”等运筹学中的问题上有重要的应用。 ? 首先看实际中常碰见的问题：给n个工作人员安排m项任务，n个人用X={x1，x2，…，xn}表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中k（k≥1）个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？ 例如，现有x1，x2，x3，x4，x5五个人，y1，y2，y3，y4，y5五项工作。已知x1能胜任y1和y2，x2能胜任y2和y3，x3能胜任y2和y5，x4能胜任y1和y3，x5能胜任y3、y4和y5。如何安排才能使每个人都有工作做，且每项工作都有人做？ 显然，我们只需做这样的数学模型：以xi和yj（i，j=1，2，3，4，5）为顶点，在xi与其胜任的工作yj之间连边，得二分图G，如图8.4.4所示，然后在G中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题 下面给出一些基本概念和术语，假设G是任一无向图。 匹配 设M是E（G）的一个子集，如果M中任二边在G中均不邻接，则称M是G的一个匹配。M中一条边的两个端点，叫做在M是配对的。 饱和与非饱和 若匹配M的某条边与顶点v关联，则称M饱和顶点v，且称v是M―饱和的。否则称v是M―不饱和的。 完美匹配 G中每一个顶点都是关于匹配M饱和的。 完全匹配 设二分图G=〈V1,，V2，E〉，M是G中匹配，若v∈V1，v均是M―饱和的，则称M是V1对