资源描述：
《离散数学(chapter10一些特殊的图)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学主讲教师邓毅雄8/10/20211离散数学第10章一些特殊的图§10.1二部图§10.2欧拉图§10.3哈密尔顿图§10.4平面图§10.5树8/10/20212离散数学亚瑟国王的配婚问题：150个卫士和150个宫女来自不同的家族，有的家族之间有历史恩怨，彼此不愿意成婚。亚瑟国王要求其一大臣将他们配对成婚，否则将把该大臣投入监狱。大臣要求男女各站一边，彼此愿意成婚的举手，结果大臣认为无法配对成婚。但国王不理解他的解释，他的命运？8/10/20213离散数学用图表示卫士与宫女愿意成婚的关系：卫士宫
2、女8/10/20214离散数学1994年全国大学生数学建模竞赛B题：锁具装箱问题某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}6个数(单位略)中任取一数.由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数;相邻两槽高度之差不能为5.满足以上条件制造出来的所有互不相同的锁具称为一批. 出来的所有互不相同的锁具称为一批.从顾客的利益出发,自然希望在每批锁具中"一把钥匙开一把锁".8/10/20215离散数学但是在当前工艺条件下,对于同一批中两
3、个锁具是否能够互开,有以下试验结果:若二者相对应的5个槽的高度中有4个相同,另一个的高度差为1,则可能互开;在其它情形下,不可能互开.原来,销售部门在一批锁具中随意地取每60个装一箱出售.团体顾客往往购买几箱到几十箱,他们抱怨购得的锁具会出现互相开的情形.现聘聘请你为顾问,回答并解决以下问题:8/10/20216离散数学1)每一批锁具有多少个,装多少箱.2)为销售部门提供一种方案,包括如何装箱(仍是60个锁具一箱),如何给箱子以标志,出售时如何利用这些标志,使团体顾客不再或减少抱怨.3)采取你提出的方案
4、,团体顾客的购买量不超过多少箱,就可以保证一定不会出现互4)按照原来的装箱办法,如何定量地衡量团体顾客抱怨互开的程度(试对购买一、二箱者给出具体结果).8/10/20217离散数学可以证明：(1)槽高的和为奇数(或偶数)的锁之间不能互开；(2)一批锁具中，槽高的和为奇数与偶数的各占一半。8/10/20218离散数学此问题涉及到“互开”关系，用图表示这种互开关系：奇偶以上两个问题对应图有什么特点？8/10/20219离散数学二部图(偶图)：若无向图G=的顶点集V能划分成两个子集V1和V2，使得G
5、中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图(偶图)。V1,V2称为互补顶点子集。§10.1二部图完全二部图(完全偶图)：若V1中任一顶点与V2中每个顶点均有且仅有一条边相关联，则称G为完全二部图(完全偶图)。8/10/202110离散数学K2,3K3,3一个无向图G=是二部图当且仅当G中无奇数长度的回路。二部图判定定理若
6、V1
7、=n，
8、V2
9、=m，则记完全二部图G为Kn,m圈的长度都是偶数8/10/202111离散数学例1：判断下列图是否为二部图。v4v3v2v1v5v
10、6v7v8同构于v4v3v2v1v5v6同构于v6v4v3v2v1v5v7v8v4v3v2v1v5v68/10/202112离散数学匹配：设E’是图G=(V,E)的边集的子集，如果E’中的边是相互不相邻的，则称E’是G的一个匹配。v4v3v2v1v5v68/10/202113离散数学设M是G的一个匹配，v是G的一个点，如果v是M中某边的端点，则称v为M饱和的。如果G中所有点都是M饱和的，则称M为完美匹配。v4v3v2v1v5v68/10/202114离散数学最大匹配：边数最多的匹配。匹配数：最大匹配中元
11、素的个数。亚瑟王的配婚问题，就是寻找完美匹配。锁具装箱问题要求匹配数。有关图的完美匹配的存在性的判断：(1)Hall定理（二部图）；(2)Tutte定理（一般情况）。8/10/202115离散数学例要给四位教师（赵、钱、孙、李）从离散数学（DM）、操作系统（OS）、C++（C）、数据库（DB）中各安排一门课程。现知道赵老师能教离散数学，钱老师能教操作系统和数据库，孙老师能教离散数学、C++和数据库，李老师能教操作系统和C++。问如何安排才能使每个教师不教自己不熟悉的课程？解用结点表示教师和课程，教师能教
12、课程用边连接相关的结点，得如图所示的二部图。赵钱孙李DMOSCDB图10-9课程安排图8/10/202116离散数学图论中的第一个问题：哥尼斯堡七桥问题ABCD°AB°C°D°欧拉于1736年解决了此问题，从而使他成了图论和拓扑学的创始人。8/10/202117离散数学欧拉通路(欧拉回路)：经过图中每条边一次且仅一次并且行遍每个顶点的通路(回路)，称为欧拉通路(欧拉回路)。§10.2欧拉图（一笔画问题）欧拉图：存在欧拉回路的图。8/10/2
