《一些特殊的图离散数学离散数学（第四版）清华出课件》由会员分享，可在线阅读，更多相关《一些特殊的图离散数学离散数学（第四版）清华出课件（38页珍藏版）》请在金锄头文库上搜索。
1、第八章一城特弯的6270013604PM第四郡分,图论(掌谁敦师,自能农)无向图G是二部图当丘仅占G中元奇数长度的宅仝邗零(兀仝偶图)=rKaa6270013604PM第四部分,图论(提谁敦师,自能农)匹配*设G=是简单无向图,EscSE,若B#中任意两边疹不相邻,则称E*为G中的匹配(或边独立集)。若在B*卜一加y,与v关联,则秘v为Tf饱和点,否则称v为M非饱和G中每个双评是M龟和怡,刹诊以是G市的光大匹酯6270013604PM第四部分,图论(提谁敦师,自能农)3*完备匹配设G=是二部图,若G中的余,匹配M饰和V,或V,中所有顶点,则积M为完备匹配。注意:完备匹配一定是最大匹配,但仅:I
2、VulzD7|才5亦美陆技E%啬丈【沥仁到Va的完符匹配H0人口6272013604PM第四部分,图论(提谁敦师,自能农)4=证明:至少为Kt条,但Vo中每个顶存在完舒丁印外一G中存在V到Va的完备任取W中的K(f=I.2,.|历D个顶点,他们关联的边边至少关联Vo中的k个顶点。前提,所以,G中存在Vu到V的完备匹配。个充公条企二部图a求解过程:(D取一初始匹配M.90国Q)分析M非饱和顶点,调整匹配方桌。t-卫,去6270013604PM第四部分,图论(授谁教师,自肽农)n吴2坂技巴enTeonRardRrIer(1707-1783)*Swissmathematician,Whostudie
3、dattheUniy,ofBaseLtheSwissmathematicianJohannBernoulliobtainingh论master“sdegreeattheageof16,HeworkedasamemberthefacultyoftheAcademyofScienceinSaintPertersRussiaformorethan30years.“欧拉计算毫不费力,就象人呼吱,或者鹰在风中保持平衡一祖1(闪止又汪)这人永X|余亢无与伦比的数学才能的夺大欧拉是节万存传爱泓刑数学条,被他的同代人称为“外动外化孙“。甚至在他生命的最后十年中的完全失明,也没有妨碍他的无与伦比的多产;事实上,
4、失去视力有什么影响的话,那就是使欧拉对他想象中的内部世界的洞察力更加敏锐。摘自贝尔:数学精奖6270013604PM第四部分,图论(掌谁敏师,肉肽罚)Kinigsberg七桥问题*问题的抽象:=-用顶点表示对象-“地块“=-用边表示对象之间的关系-有桥相连24-能否从河岸或小岛出发,通过每一座桥,而且仅仪通过一次回到原地。吾Buler(欧拉)1736年对这个问题,给出了否定的回答将,河岸和小岛作为图的T点,-史庭桥为边、构成一个吻能量图,问题亿丶图论中佼单坤江的闭顽别李技6270013604PM第四部分,图论(提课教师川斗)欧拉通路和欧拉回路/*包含图中每条边的筒单通路称为欧拉通路。刀1*包含图中每条边的简单回路称为欧拉回路。如柜匈G中含欧拉回路,则图G称为欧拉图。*如果图G中有欧拉通路,但汗有欧拉小力宇区人卜丞刀志:6270013604PM第四部分,图论(提谁敦师,自能农)934沥圃H/弋经欧拉图的判定*连通无向匹均为健数。*达通无向个奇度顶*连通有向度等于出荣。珥中*连通有向图D具有欧拉通路当旦仅当D中除花茹个:顶点外,其余顶点的入度均等于出度。这莹沙痛殊的顶点中,一个顶点的入度比出度大1顶点的入度比出度小1。6270013604PM第四部分,图论(提谁敦师,自能农)衔人励画偕5逊巴河选人EE昌r闹G具有欧拉通路当目仅当G有零个战刹|E余D是欧拉图当且仅当D中每个顶-
