离散数学一些特殊的图ppt教学.ppt
《离散数学一些特殊的图ppt教学.ppt》由会员分享,可在线阅读,更多相关《离散数学一些特殊的图ppt教学.ppt(37页珍藏版)》请在三一文库上搜索。
1、1,第8章 一些特殊的图,8.1 二部图 8.2 欧拉图 8.3 哈密顿图 8.4 平面图,2,8.1 二部图,二部图 完全二部图 匹配 极大匹配 最大匹配 匹配数 完备匹配,3,二部图,定义 设无向图 G=, 若能将V 分成V1 和 V2 (V1V2=V, V1V2=), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图(二分图), 记为, 称V1和V2为互补顶点子集. 又若G 是简单图, 且V1中每个顶点均与V2中每个顶点都相 邻, 则称G为完全二部图, 记为Kr,s, 其中r=|V1|, s=|V2|.,(a),(b),以上两个图都是二部图,其中(b)图是完
2、全二部图。,4,例 完全二分图Km, n=(V1,V2,E)共有 多少条边?,解 因为V1中每个顶点都与V2 中每个顶点相邻接,所以V1 中每个顶点关联 |V2| = n 条边; 而V1 中有m个顶点, 所以Km, n共有mn条边。,5,二部图的判别法,定理 无向图G=是二部图当且仅当G中 无奇圈 。即G中的每一条回路都是由偶 数条边组成。,证明:当G(V1,V2)是二部图时,G中的任意一条回路的各边必须往返于V1,V2之间,因此其回路必由偶数条边组成。,6,例:判断下图是否为二部图。,解:图中的每一条回路都是由偶数条边组成。所以此图为二部图。,7,匹配,设G = (V, E)是具有互补顶点子
3、集V1和V2的二 分图, M E, 若M中任意两条边都不相邻, 则称 M为G中的匹配(对集)。 如果M是G的匹配, 且M中再加入任何一条边就都是不匹配了, 则称M为极大匹配。 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为1。,8,如在下图中,如果用a1,a2,a3,a4表示4位教师,b1,b2,b3表示三门待开的课程。当某位教师能开某门课程时,则把它们的对应顶点用边连接起来。如果规定一个教师只能担任一门课程,那么匹配M就表示了一种排课方案。为了使排课方案能最大限度地作到“各尽其能”,这就是最大匹配的概念。,9,匹配 (续),设M为G中一个匹配 ai与bj被M匹配: (ai,b
4、j)M ai为M饱和点: M中有边与ai关联 ai为M非饱和点: M中没有边与ai关联 M为完美匹配: G的每个顶点都是M饱和点,10,定义 设G=为二部图, |V1|V2|, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完备匹配. 当|V1|=|V2|时, 完备匹配变成完美 匹配.,(1),(2),(3),图中红边组成各图的一个匹配,(1)为完备的, 但不是完 美的; (2)不是完备的, 其实(2)中无完备匹配; (3) 是完美的.,匹配 (续),例:如图,11,例 求下图的饱和点,并判断哪个图是完美匹配?,解:关于M1, a,b,e,d是饱和点f,c是非饱和
5、点 M1不是完美匹配 M2是完美匹配,所以M2中 a,b,c,d,e,f都是饱和点。,12,设G=V1,V2,E是二部图,M是G的一个匹配,如果对G的任意匹配M,都有|M|M|,则M为G的最大匹配 为了寻求二部图的最大匹配,以下引进交替通路和增长通路两个概念。,定义 设G=V1,V2,E是二部图,M是G的匹配,P是G中的一条路,如果P是由G中属于M的边和不属于M的边交替组成,则称P为G的M交替通路。如果交替通路的始点和终点都是M的非饱和点,则称为G的M增长通路。,13,例如,在图中匹配M=(a1,b2), (a2,b3), (a3,b5), 路 L1:a1b2a2b3a3, L2:a2b3a3
6、b5a4, L3:b1a3b5a4, L4:b1a1b2a2b3a3b5a4 都是M的交替通路,其中后两条交替通路L3和L4的始点和终点都是M的非饱和点,所以这两条路是M增长通路。,卡盟 卡盟,Microsoft Office PowerPoint,是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示,也可以将演示文稿打印出来,制作成胶片,以便应用到更广泛的领域中。利用Microsoft Office PowerPoint不仅可以创建演示文稿,还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。 Microsoft Office PowerPoint做出来的东西叫演
7、示文稿,其格式后缀名为:ppt、pptx;或者也可以保存为:pdf、图片格式等,15,设G=V1,V2,E是二部图,M是G的一个匹配,P是G中的一条M增长通路。把P中所有属于M的边从M中去掉,而把P中所有不属于M的边添加到M中,得到一个新的边集M,则M也是一个匹配,其所含边数比匹配M所含的边数多1。,16,例如在图中,把M增长通路L3:b1a3b5a4中属于M的边(a3,b5) 从M中去掉,而把L3中不属于M的边(a3,b1)和(a4,b5) 添加到M中,得到一个新的边集M=(a1,b2),(a2,b3),(a3,b1), (a4,b5),显然M也是匹配且M的边数比M的边数多l,即|M|M|+
8、1。,17,由此可见,利用增长通路可以增加匹配所含的边数。不断地寻求G的增长通路,直到再也找不到新的增长通路,就可得到一个最大匹配。将这个结论写成下列的定理。 定理 设G=V1,V2,E是二部图,M为G的最大匹配的充分必要条件是G中不存在M增长通路。,证明:设M为G的最大匹配,下证G中不存在M可扩路。 如果G中存在一条M可扩路,则可以得到比M的边数多1的匹配,所以M不是最大匹配,矛盾。所以G中不存在M可扩路。 设G中不存在M可扩路,下证M为G的最大匹配。 设M1是最大匹配,证明|M|=|M1|。 考察属于M而不属于M1和属于M1而不属于M中的边,由这些边连同它们的端点一起构成G的子图H。,18
9、,在子图H中,任一顶点至多与M中的一条边关联且与M1中一条边关联。因而任一顶点的度数是1或2。故H的连通分支是一条路,或者是一个回路。 如果H的连通分支是一条路P,则它是M交替路,也是M1交替路。如果P的两个端点均与M中的边关联,则P是M1可扩路。由假设知,M1是最大匹配,所以,不存在M1可扩路,得到矛盾。如果P的两个端点均与M1的边关联,那么P是一条M可扩路与题设矛盾。故P只能是一个端点与M中的边关联,另一个端点与M1中的边关联,这样P中属于M的边数与属于M1的边数相等。,19,如果H的连通分支是一个回路,回路中的边交替地属于M和M1,因而属于M的边数与属于M1的边数相等。 从上面可以看到,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 一些 特殊 ppt 教学
链接地址:https://www.31doc.com/p-2252405.html