汉密尔顿图课件

1、1，旅行路线，1，2，3，4，5，6，7，8，2，骑士旅行路线，骑士旅行路线，环游世界，通过哈密尔顿(后)路，汉密尔顿图表2。汉密尔顿图表判断的必要条件3。哈密尔顿图表判断的充分条件4。旅游公司问题，5，will am rowsan Hamilton，will am rowsan Hamilton(1805165):爱尔兰神童，Trinity College(Trinity College)1837，多个巩俐，a bi，(a，b)四元数： a bi CJ dk，放弃乘法交换法！6，文章旅行路径，Leo hard Euler，1759，详细分析，7，汉密尔顿图，汉密尔顿路径(汉密尔顿路径):通过

2、图中所有顶点的初级路径汉密尔顿循环、k3、K5、n否则，p(C-V1)|V1|。c是g的生成子图形，因此p (g-V1) p (c-V1) | v1 |。#、11、无方向哈密顿图的必要条件是：是G=无方向半哈密顿图，v的所有郑智薰-真子集v1具有p(G)p是g的生成子图形，因此p (g-V1) p (p-v1) | v1 | 1。#，12，推理(证明2)，是G=全向半哈密顿图，v的所有郑智薰null子集v1具有p(G-V1)|V1#，13，反例：不充分条件，定理3不是： Petersen图Petersen图满足3360 V1，只是必要条件。P(G-V1)|V1| Petersen图不是汉密尔顿

3、图：14，2篇和汉密尔顿图表-示例1，b，a，f，e，2篇和汉密尔顿图表-示例2，G为准哈密顿图时，|V1|=|V2|-1或| v1 |=| v2 | | | V2 | | V1 | 2时，G不是哈密顿图，G为哈密顿图，18，无向哈密顿图的充分条件，定理44: (1) G被(2)大路径循环(3)被较长的路径循环(最大路径-圆-较长的路径-较长的路径-较长的路径-汉密尔顿路径(配置方法)，19，最大最大值：不能再向外扩展，20，清理4(证明(1)(3)为3360 (1)(2a)对于e (v0，vk)E，圆c=C=v0v1vkv0。(2b)对于e (v0，vk)E，设置i(1ik-1(vi，vk)

4、E(v0，VI 1)E；否则，设置D(v0) d(vk)d圆c=v0v iv kvk-1vi 1vi 1v 0。#，v0，vk，VI，vi1，从定理4连接到g，哈密尔顿路径=v0v1vn。(1)如果e (v 0，VN)，则哈密顿回路C=v0v1vnv0。(2)如果e (v 0，vk)，则汉密尔顿循环(#，v 0，VN，)如果g中任意顶点u的d(u)n/2存在，则g是哈密顿图。推论3:Kn(n2)给出了哈密顿图，24，图的闭包C(G)，定义：简单图G=，|V|=n，连接图G的度数总和和至少n的不相邻顶点以生成图G，直到不再存在这样的顶点对，25，定理5，定理5:无向n次简单图G是哈密顿图C(G)

5、，26，次，次，次：是u，v是非向n次简单图G不相邻的两个顶点，d(u) d()证明：()显然是c等于G(u，(v)的哈密顿回路。(1) C不通过(u，v): C是g的哈密顿回路。(2) C通过(u，v): C-(u，v)是g的哈密顿过程，类似于定理4证明(2b)，g有哈密顿回路。#，27，使用案例：在7天内考试安排7次课程，避免在相邻的2天内考试同一位老师负责的2次课程，如果没有4次以上课程的老师，则可以合理安排。每个顶点对应于测试过程，只有在两个顶点之间有边，并且这两个过程徐璐由另一位教师负责的情况下，每个顶点的度数至少为3，两个顶点的度数至少为6，因此必须有汉密尔顿过程。28，哈密顿图的

6、充分条件，n(n1)阶竞赛也有哈密尔顿球道。证明：归纳法、vk1、vk1、29、旅行商问题(TSP)、旅行商问题(Travling Salesman Problem):是n个城市之间的所有距离，对销售员来说是到所有城市旅行的最短路径，又称单h通路，(n-1)！/2个h循环当前不知道TSP是否具有多项式时间算法。大多数学者认为没有。证明？P=？妮可问题：计算机科学的核心问题，奖金1，000，000近似算法，31，摘要，环游世界，汉密尔顿之路，汉密尔顿之图判断的必要条件汉密尔顿之图判断的充分条件这是(1)欧拉和哈密尔顿；(2)不是汉密尔顿地图，而是欧拉多。(。(3)非长久的哈密尔顿图；(4)欧拉也不是哈密尔顿。(。33，作业2:2，现在知道a，b，c，d，e，f，G7人，以下事实：a会说英语；b能说英语和汉语。c