欧拉图及哈密顿图.ppt

下载文档

0
0
约8.04千字
约 39页
2025-02-09 发布于广东
举报
版权申诉
保障服务

欧拉图及哈密顿图.ppt

1、本文档共39页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

奇偶点作业法（1）把G中所有奇度顶点配成对，将每对奇度顶点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中无奇度顶点，即G1为多重欧拉图.（2）若G1中某对结点间有多于两条边连接，则去掉其中偶数条边，留下一条或两条边连接这两个结点，直到每对相邻结点至多由2条边连接。得到图G2.第30页,共39页，星期六，2024年，5月（3）检查G2的每个圈C，若某个圈C上重复边集E的权和超过这个圈的权和的一半，则将C按定理1必要性证明中的方法进行调整，直到对G2所有的圈其重复边的权和不超过此圈权和的一半，得到图G3.（4）用Fleury算法求G的Euler回路.第31页,共39页，星期六，2024年，5月例3求下图G的最优环游.v1v2v3v4v5v6v7v8v9v10v11v1224553646465447938A第32页,共39页，星期六，2024年，5月V12v104v95v8V26v114v126v7554477V39v43v58v6B第33页,共39页，星期六，2024年，5月44554477998864636C第34页,共39页，星期六，2024年，5月446466654444793836D第35页,共39页，星期六，2024年，5月594443345536466664第36页,共39页，星期六，2024年，5月2第37页,共39页，星期六，2024年，5月例4.设G是分划为X,Y的二分图,且则G一定不是哈密顿图.(利用分支数反证)例5.设简单图G=V,E则G是哈密顿图.第38页,共39页，星期六，2024年，5月证明：G中的任意两点u,v，其度数分别为d(u),d(v)

对于图G-{u,v}都有

m-d(u)-d(v)=(n-2)(n-3)/2

又因为m=Cn-12+2

d(u)+d(v)=(n-1)(n-2)/2+2-(n-2)(n-3