离散汉密尔顿图.ppt

1 周游世界 SirWilliamRowanHamilton 1857 Icosiangame 是否存在一条回路 使它含有图中的所有顶点一次且仅一次 2 马的周游路线 knight stour 棋盘上马的周游路线 knight stouronachessboard 3 汉密尔顿图 1 周游世界 汉密尔顿通 回 路 汉密尔顿图2 判定汉密尔顿图的必要条件3 判定汉密尔顿图的充分条件4 旅行商问题 4 WillamRowanHamilton WillamRowanHamilton 1805 1865 爱尔兰神童 childprodigy 三一学院 TrinityCollege 光学 optics 1827 AstronomerRoyalofIreland 1837 复数公理化 a bi a b 四元数 quaternion a bi cj dk 放弃乘法交换律 5 马的周游路线 knight stour LeohardEuler 1759 详细分析 6 汉密尔顿图 Hamilton 汉密尔顿通路 Hamiltonpath 经过图中所有顶点的初级通路汉密尔顿回路 Hamiltoncircuit cycle 经过图中所有顶点的初级回路汉密尔顿图 Hamiltonian 有汉密尔顿回路的图半汉密尔顿图 semi Hamiltonian 有汉密尔顿通路但没有汉密尔顿回路的图 7 汉密尔顿图 Hamilton 的思考 n阶简单图是汉密尔顿图 要求m n 要有尽可能多的边 K3 3 K5 8 无向汉密尔顿图的必要条件 定理15 6 设G 是无向汉密尔顿图 则对V的任意非空真子集V1有p G V1 V1 证明 设C是G中任意汉密尔顿回路 当V1中顶点在C中都不相邻时 p C V1 V1 最大 否则 p C V1 V1 C是G的生成子图 所以p G V1 P C V1 V1 9 无向半汉密尔顿图的必要条件 推论 设G 是无向半汉密尔顿图 则对V的任意非空真子集V1有p G V1 V1 1证明 设P是G中任意汉密尔顿通路 当V1中顶点都在P内部且都不相邻时 p P V1 V1 1最大 否则 p P V1 V1 P是G的生成子图 所以p G V1 p P V1 V1 1 10 推论 证明二 推论 设G 是无向半汉密尔顿图 则对V的任意非空真子集V1有p G V1 V1 1证明二 设P是G中任意汉密尔顿通路 两个端点是u与v 令G1 G u v 由定理3有p G V1 p G1 V1 1 V1 1 11 举例1 b a f e 二部图 a f 和 b c d e d c 12 举例2 b a c d e f g h i j k 二部图 a c g h i 和 b d e f j k 半汉密尔顿图 13 举例3 b c d e f g h i j 二部图 a c g h e 和 b d f i j 汉密尔顿图 a 14 二部图与汉密尔顿图 设二部图G V1 V2 V1 2 V2 2若G是汉密尔顿图 则 V1 V2 若G是半汉密尔顿图 则 V1 V2 1 若 V2 V1 2 若G不是半汉密尔顿图 也不是汉密尔顿图 15 反例 非充分条件 上述条件只是必要条件 而不是充分条件反例 Petersen图Petersen图满足 V1 p G V1 V1 Petersen图不是汉密尔顿图 穷举Petersen图是半汉密尔顿图 16 无向半汉密尔顿图的充分条件 定理15 7 设G是n 2 阶无向简单图 若对G中任意不相邻顶点u与v有d u d v n 1则G是半汉密尔顿图 证明 1 G连通 2 由极大路径得圈 3 由圈得更长路径路径 极大路径 圈 更长路径 更长极大路径 更长圈 更长路径 汉密尔顿通路 构造法 17 极大路径 是一条路径 如果 的始点和终点都不与 外的顶点相邻 则称 是一条极大路径 极大 不能再向外延伸 18 定理15 7 证明 1 3 证明 1 G连通 u v u v E w u w E w v E 3 由圈得更长路径 由连通性 19 定理15 7 证明 2 证明 2 由极大路径得圈 设极大路径 v0v1 vk k n 2 2a 若 v0 vk E 则得圈C v0v1 vkv0 2b 若 v0 vk E 则 i 1 i k 1 vi vk E v0 vi 1 E 否则 d v0 d vk d v0 k d v0 k n 2 矛盾 于是得圈C v0 vivkvk 1 vi 1v0 v0 vk vi vi 1 v0 vk 20 无向汉密尔顿图的充分条件 推论1 设G是n 3 阶无向简单图 若对G中任意不相邻顶点u与v有d u d v n则G是汉密尔顿图 证明 由定理15 7知G连通且有汉密尔顿通路 v0v1 vn 1 若 v0 vn E 则得汉密尔顿回路C v0v1 vnv0 2 若 v0 vk E 则与定理15 7证明 2b 类似 也存在汉密尔顿回路 v0 vn vi vi 1 v0 vn 21 无向汉密尔顿图的充分条件 推论2 设G是n 3 阶无向简单图 若对G中任意顶点u有d u n 2则G是汉密尔顿图 推论3 Kn n 2 为汉密尔顿图 22 图的闭包C G 定义 给定简单图G V n 将图G中度数之和至少为n的非邻接顶点连接起来得到图G 对G 重复上述步骤 直到不再有这样的顶点对为止 所得到的图称为G的闭包 记作C G 23 定理5 定理5 无向n阶简单图G是汉密尔顿图 C G 是汉密尔顿图 24 引理 引理 设u v是无向n阶简单图G中两个不相邻顶点 且d u d v n 则G是汉密尔顿图 G u v 是汉密尔顿图 证明 显然 设C是G u v 中的汉密尔顿回路 1 C不经过 u v C是G中汉密尔顿回路 2 C经过 u v C u v 是G中汉密尔顿通路 与定理15 7证明 2b 类似 G中有汉密尔顿回路 25 应用举例 例 七天内安排七门课的考试 使得同一位教师所担任的两门课程不在相邻的两天考试 若无教师担任多于四门课程 则可以合理安排 每个顶点对应一门考试课程 两个顶点之间有边当且仅当对应两课程由不同教师担任 每个顶点的度数至少是3 任两个顶点度数之和至少为6 因此一定存在一条汉密尔顿通路 26 有向汉密尔顿图的充分条件 n n 1 阶竞赛图中都有汉密尔顿通路 证明 归纳法 vk 1 vk 1 vk 1 27 旅行商问题 TSP 旅行商问题 TravlingSalesmanProblem 给定n个城市之间的所有距离 求推销员走遍所有城市的最短路线又名货郎担问题 巡回售货员问题 TSPTSP 给定带权完全图G 求最短汉密尔顿回路 28 TSP的复杂性 蛮力法 bruteforce 穷举所有的可能进行验证或比较 复杂性为2n以上 TSP n 条H通路 n 1 2条H回路目前还不知道TSP是否有多项式时间算法 大多数学者认为没有 证明 P NP问题 计算机科学的核心问题 奖金 1 000 000 29 总结 周游世界 汉密尔顿通 回 路 汉密尔顿图判定汉密尔顿图的必要条件判定汉密尔顿图的充分条件旅行商问题 30 作业1 1 画一个无向图 使它是 1 既是欧拉图 又是汉密尔顿图 2 是欧拉图 而不是汉密尔顿图 3 是汉密尔顿图 而不是欧拉图 4 既不是欧拉图