哈密尔顿图ppt课件.ppt

哈密尔顿图哈密尔顿图离散数学离散数学──图论南京大学南京大学计算机科学与技算机科学与技术系系内容提要内容提要l哈密尔顿通路哈密尔顿通路l哈密尔顿回路哈密尔顿回路l哈密尔顿图的必要条件哈密尔顿图的必要条件l哈密尔顿图的充分条件哈密尔顿图的充分条件l哈密尔顿图的运用哈密尔顿图的运用l竞赛图与有向哈密尔顿通路竞赛图与有向哈密尔顿通路l沿着正十二面体的棱沿着正十二面体的棱寻觅寻觅一条游一条游览览道路道路, 经过经过每个每个顶顶点恰好一次又回到出点恰好一次又回到出发发点点. (Hamilton 1857) 周游世界的游周游世界的游戏戏lG中中Hamilton通路通路l包含包含G中一切中一切顶顶点点l通路上各通路上各顶顶点不反复点不反复lG中中Hamilton回路回路l包含包含G中一切中一切顶顶点点l除了起点与除了起点与终终点一点一样样之外，通路上各之外，通路上各顶顶点不反复点不反复lHamilton回路与回路与 Hamilton通路通路lHamilton通路通路问题问题可可转转化化为为Hamilton回路回路问题问题lG*K1Hamilton通路通路/回路回路Hamilton回路的根本特性回路的根本特性lHamilton回路回路:无反复地遍无反复地遍历图历图中中诸诸点点, l Euler回路回路:无反复地遍无反复地遍历图历图中中诸边诸边.l假假设图设图G中有一中有一顶顶点的度点的度为为1, 那么无那么无Hamilton回路回路.l设图设图G中有一中有一顶顶点的度大于点的度大于2, 假假设设有有Hamilton回路回路, 那么只用其中的两条那么只用其中的两条边边.l假假设图设图中有中有n个个顶顶点点, 那么那么Hamilton回路恰有回路恰有n条条边边.l注：注：Hamilton回路回路问题问题主要主要针对简单图针对简单图。

Hamilton回路的存在性回路的存在性问题问题Kn(n 3)有有Hamilton回路回路 acbedacbedacbedK3K4一个根本的必要条件一个根本的必要条件l假假设图设图G=(V, E)是是Hamilton图图，那么，那么对对V的任一非空的任一非空子集子集S，都有，都有lP(G-S)  |S|l其中，其中， P(G-S)表示表示图图G-S的的连连通分支数通分支数. l理由：理由：设设C是是G中的中的Hamilton回路回路, P(G-S)  P(C-S)  |S|l 向一个向一个图图中中顶顶点之点之间间加加边边不会添加不会添加连连通分支必要条件的运用必要条件的运用举例举例将将图图中点中点a, b, c的集合的集合记为记为S, G-S有有4个个连连通分支通分支,而而|S|=3. G不是不是Hamilton图图. abc以下以下图给图给出的是出的是 C2,7的的详细图详细图 (h=2,n=7) KhKhKn-2h举例举例必要条件的局限性必要条件的局限性l必要条件只能断定一个图不是哈密尔顿图必要条件只能断定一个图不是哈密尔顿图lPetersen图满足上述必要条件，但不是哈密图满足上述必要条件，但不是哈密尔顿图。

尔顿图哈密尔顿图的充分条件哈密尔顿图的充分条件lDirac定理〔狄拉克定理〔狄拉克, 1952〕〕l 设设G是无向是无向简单图简单图，，|G|=n 3 ，， 假假设设  (G)  n/2，那么，那么G有哈密有哈密尔尔顿顿回回图图.lOre定理〔奥定理〔奥尔尔, 1960〕〕l 设设G是无向是无向简单图简单图，，|G|=n 3 ，假，假设设G中恣意不相中恣意不相邻邻的的顶顶点点对对u,v均均满满足：足： d(u)+d(v) n ，那么，那么G有哈密有哈密尔尔顿顿回回图图l设G是是无无向向简单图, |G|=n2, 假假设G中中恣恣意意不不相相邻的的顶点点对u,v均均满足：足：d(u)+d(v)n-1，那么，那么G是是连通通图l假假设G不不连通通，，那那么么至至少少含含2个个连通通分分支支，，设为G1, G2取取xVG1, yVG2, 那那么么：：d(x)+d(y)(n1-1)+(n2-1)n-2 (其中其中ni是是Gi的的顶点个数点个数)，矛盾 充分条件的讨论充分条件的讨论l“  (G)  n/2〞不能减弱〞不能减弱为为：：   (G) l举举例，例，n=5，，  (G)=2 . G不是不是Hamilton图图.l存在哈密尔顿通路的充分条件〔存在哈密尔顿通路的充分条件〔Ore定理的推论〕定理的推论〕l 设设G是是无无向向简简单单图图，，|G|=n 2 ，，假假设设G中中恣恣意意不不相相邻邻的的顶顶点对点对u,v均满足：均满足： d(u)+d(v) n-1 ，那么，那么G有哈密尔顿通路。

有哈密尔顿通路Ore定理的定理的证证明明lOre定理定理〔 〔1960〕 〕l 设设G是无向是无向简单图简单图，，|G|=n3，假，假设设l 对对G中恣意不相中恣意不相邻邻的的顶顶点点u和和v, d(u)+d(v)n 〔 〔*〕 〕 l 那么那么G有哈密有哈密尔尔顿顿回回图图l证证明明.反反证证法法, 假假设设存在存在满满足足〔 〔*〕 〕的的图图G，但是，但是G没有没有Hamilton回路回路. l 无妨假无妨假设设G是是边边极大的非极大的非Hamilton图图，且，且满满足足〔 〔*〕 〕假假设设G不是不是边边极大的非极大的非Hamilton图图，那么可以不断地，那么可以不断地向向G添加假添加假设设干条干条边边,把把G变变成成边边极大的非极大的非Hamilton图图G’，，G’依然依然满满足足〔 〔*〕 〕，由于，由于对对vV(G), dG(v)dG’(v)设设u, v是是G中不相中不相邻邻的两点，于是的两点，于是G+uv是是Hamilton图图，且其中，且其中每条每条Hamilton回路都要回路都要经过边经过边uv. 因此，因此，G中有起点中有起点为为u，，终终点点为为v的的Hamilton通路通路: Ore定理的定理的证证明明u=v1vi-1viv=vn不存在两个相不存在两个相邻的的顶点点 vi-1和和vi,使得使得vi-1与与v相相邻且且vi 与与u相相邻. 假假设不然不然, (v1,v2, … vi-1, vn, …, vi, v1)是是G的的Hamilton回路回路. 设在在G中中u与与vi1, vi2, …, vik相相邻, 那么那么v与与vi1-1, vi2-1, …vik-1都不都不相相邻, 因此因此d(u)+d(v) k+[(n-1)-k]

回路中l哈密哈密尔顿回路中不能含回路中不能含l 真子回路真子回路l利用利用对称性称性l利用二部利用二部图特性特性l…断定哈密尔顿图的例子断定哈密尔顿图的例子l以下图中只需右图是哈密尔顿图以下图中只需右图是哈密尔顿图棋盘上的哈密尔顿回路问题棋盘上的哈密尔顿回路问题l在在4 4或或5 5的减少了的国际象棋棋盘上，马的减少了的国际象棋棋盘上，马(Knight)不能够从某一格开场，跳过每个格子一次，不能够从某一格开场，跳过每个格子一次，并前往起点并前往起点灰〔灰〔13个〕个〕 VS 白〔白〔12个〕个〕 哈密哈密尔尔顿图问题顿图问题l根本问题根本问题l断定哈密尔顿回路的存在性断定哈密尔顿回路的存在性l找出哈密尔顿回路找出哈密尔顿回路/通路通路l〔在最坏情况下〕时间复杂性为多项式的算法？〔在最坏情况下〕时间复杂性为多项式的算法？运用〔格雷码〕运用〔格雷码〕l给给定一个立方体定一个立方体图图，求出哈密，求出哈密尔尔顿顿回路回路Q3100101000001110111010011安排考试日程〔哈密尔顿通路〕安排考试日程〔哈密尔顿通路〕l问题: 在在6天里安排天里安排6门课 – A,B,C,D,E,F -的考的考试，每天，每天考考1门。

假假设每人每人选修修课的情况有如下的的情况有如下的4类：：DCA，，BCF，，EB，，AB如何安排日程，使得没有人必需延如何安排日程，使得没有人必需延续两天有考两天有考试？？ABCDEFABCDEF竞赛图竞赛图底图为底图为K4的竞赛图：的竞赛图：ABC以上每个图可以看作以上每个图可以看作4个选手参与的循环赛的一种结果个选手参与的循环赛的一种结果竞赛图与有向哈密尔顿通路竞赛图与有向哈密尔顿通路 l底图是完全图的有向图称为竞赛图底图是完全图的有向图称为竞赛图l利用归纳法可以证明竞赛图含有向哈密尔顿通路利用归纳法可以证明竞赛图含有向哈密尔顿通路 作业作业l教材教材[9.5] (p.497)l40, 41, 42l45, 46, 49, 63l补补充充l思索在思索在7天安排天安排7门课门课程的考程的考试试，使得同一位教，使得同一位教师师所任的两所任的两门课门课程考程考试试不排在接不排在接连连的两天中，的两天中，试证试证明假明假设设没有教没有教师师担任多于担任多于4门课门课程，那么符合上述程，那么符合上述要求的考要求的考试试安排安排总总是能是能够够的的.循环赛该如何排名次循环赛该如何排名次AFEDCB按照在一条有向按照在一条有向Hamilton通路通路(一定存在一定存在)上的上的顺序排名：序排名：C A B D E F问题：：Hamilton通路路不是独一通路路不是独一的，例如：也可以得到另一排名的，例如：也可以得到另一排名A B D E F CC 从第一名从第一名变成了最后一名成了最后一名按照得按照得胜的的竞赛场次次(得分得分)排名：排名：A(胜4) B,C(胜3) D, E(胜2) F(胜1)循环赛该如何排名次循环赛该如何排名次AFEDCB问题：很：很难说B,C并列第二名能否公平，并列第二名能否公平，毕竟竟C战胜的的对手比手比B战胜的的对手的手的总得分更高得分更高(9比比5)。

循环赛该如何排名次循环赛该如何排名次AFEDCB建立建立对应对应与每个与每个对对手得分的向量手得分的向量s1 = (a1, b2, c3, d4, e5, f6)然后逐次求第然后逐次求第k级级的得分向量的得分向量sk, 每个每个选选手的第手的第k级级得分是其得分是其战胜战胜的的对对手在手在第第k-1级级得分的得分的总总和对应于左图所示的竞赛结果，得分向量：对应于左图所示的竞赛结果，得分向量：s1=(4,3,3,2,2,1) s2=(8,5,9,3,4,3) s3=(15,10,16,7,12,9) s4=(38,28,32,21,25,16)s5=(90,62,87,41,48,32) ......当当问题竞赛图是是强连通且至少有通且至少有4个个选手手时，，这个序列一定收个序列一定收敛于一个固定的于一个固定的陈列，列，这可以作可以作为排名：排名：A C B E D F。