《图论》5-8章-习题课.ppt

该【《图论》5-8章-习题课 】是由【zhilebei】上传分享，文档一共【32】页，该文档可以免费在线阅读，需要了解更多关于【《图论》5-8章-习题课 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。*同构于G时,称G为自对偶图。证明:G=(V,E)为自对偶图时,有m=2n?2。这里n=|V|,m=|E|。《图论》4-8章****题课第一页,编辑于星期六:八点分。*同构于G时,称G为自对偶图。证明:G=(V,E)为自对偶图时,有m=2n?2。这里n=|V|,m=|E|。提示:欧拉公式:n?m+d=2 对偶性:d=n* 同构性:n*=n 联立解得。《图论》4-8章****题课第二页,编辑于星期六:八点分。:Perterson图不是平面图。《图论》4-8章****题课第三页,编辑于星期六:八点分。:Perterson图不是平面图。《图论》4-8章****题课证一:反证。设其为平面图,则n?m+d=2。每个面至少有5条边,则2m?5d,或d?2/5m。故n?m+2/5m?2,即m?5/3(n?2)。将n=10,m=15代入得15?5/3?8,矛盾。第四页,编辑于星期六:八点分。《图论》4-:Perterson图不是平面图。证二:反证。设其为平面图。由图示,每个面至少有5条边,即l=5,代入:得: 3m?5(n?2) 将n=10,m=15代入得45?40,矛盾。第五页,编辑于星期六:八点分。,证明G中存在节点v,deg(v)?4。《图论》4-8章****题课第六页,编辑于星期六:八点分。,证明G中存在节点v,deg(v)?4。证明:不妨设G是连通的。若G是一棵树,结论显然成立。设G中有回路。反证:若G中所有结点的度均大于等于5,则2m?5n。联立m?3n?6得m?30,矛盾。《图论》4-8章****题课第七页,编辑于星期六:八点分。=7,边数m=15。证明G是连通的。《图论》4-8章****题课第八页,编辑于星期六:八点分。=7,边数m=15。证明G是连通的。证明:反证。设G不连通,有k个连通分支G1,G2,…,Gk,Gi对应结点数和边数分别为ni和mi。不存在1阶的连通分支,否则G只能由平凡图加上K6才能构成m=15,而K6是不可平面的。也不存在2阶的连通分支K2,否则G最多由K2加上K5也只能构成m=10<15。因此任意连通分支的阶必大于等于3。由mi?3ni?6,对全部连通分支求和得m?3n?6k。将n=7,m=15代入得k?1。《图论》4-8章****题课第九页,编辑于星期六:八点分。,且使得任意两个区域都相邻,问x最大是多少?《图论》4-8章****题课第十页,编辑于星期六:八点分。