有哪些信誉好的足球投注网站- 1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
- 2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
第18讲哈密顿图-Read
第18讲 哈密顿图 1. 周游世界,哈密顿通(回)路,哈密顿图 2. 判定哈密顿图的必要条件 3. 判定哈密顿图的充分条件 4. 边不重的哈密顿回路 5. 货郎问题, 计算复杂性 《集合论与图论》第18讲 1 周游世界 Sir William Rowan Hamilton, 1857, Icosian game: 《集合论与图论》第18讲 2 Willam Rowan Hamilton Willam Rowan Hamilton(1805~1865): 爱尔兰神童(child prodigy) 三一学院(Trinity College) 光学(optics) 《集合论与图论》第18讲 3 Willam Rowan Hamilton Willam Rowan Hamilton(1805~1865): 1827, Astronomer Royal of Ireland. 1837, 复数公理化, a+bi, (a,b) 四元数(quaternion): a+bi+cj +dk, 放弃乘法 交换律! 《集合论与图论》第18讲 4 马的周游路线(knight’s tour) Leohard Euler, 1759, 棋盘上马的周游路 线(knight’s tour on a chessboard) 《集合论与图论》第18讲 5 马的周游路线(knight’s tour) Leohard Euler, 1759, 详细分析 《集合论与图论》第18讲 6 哈密顿图(Hamilton) 哈密顿通路(Hamilton path): 经过图中所 有顶点的初级通路 哈密顿回路(Hamilton circuit/cycle): 经过 图中所有顶点的初级回路 哈密顿图(Hamiltonian): 有哈密顿回路的 图 半哈密顿图(semi- Hamiltonian): 有哈密 顿通路的图 《集合论与图论》第18讲 7 无向哈密顿图的必要条件 定理6: 设G=V,E是无向哈密顿图,则对 V 的任意非空真子集V1有 p(G-V )≤|V | 1 1 证明: 设C是G中任意哈密顿回路, 当V 中 1 顶点在C中都不相邻时, p(C-V )=|V |最大; 1 1 否则, p(C-V )|V |. C是G的生成子图, 所 1 1 以p(G-V )≤P(C-V )≤|V |. # 1 1 1 《集合论与图论》第18讲 8 无向半哈密顿图的必要条件 定理7: 设G=V,E是无向半哈密顿图,则 对V 的任意非空真子集V1有
文档评论（0）