第十五章 欧拉图与哈密顿图 主要內容 欧拉图 哈密顿图 带权图与货郎担问题 第十五章 欧拉图与哈密顿图 欧拉图定义 定义15.1 (1) 欧拉通路——经过图中每条边一次且仅一次行遍所有頂点的通路. (2) 欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路. (3) 欧拉图——具有欧拉回路的图. (4) 半欧拉图——具有欧拉通路而无歐拉回路的图. 几点说明： 规定平凡图为欧拉图. 欧拉通路是生成的简单通路欧拉回路是生成的简单回路. 环不影响图的欧拉性. 无向欧拉图的判别法 定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点. 证 若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图. 必要性 设C 为G 中一条欧拉回路. (1) G 连通显然. (2) ?vi?V(G)，vi在C上每出现一次获2度所以vi为偶度顶点. 由vi 的任意性，结论为真. 充分性 对边数m做归纳法（第二数学归纳法）. (1) m=1时G为一个环，则G为欧拉图. (2) 设m?k（k?1）时结论为真m=k+1时如下证明： 欧拉图的判别法 定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇 度顶点. 证 必要性简单. 充分性（利用定理15.1） 设u,v为G 中的两个奇度顶点，令 G ? =G?(u,v) 则G ? 连通且无奇度顶点由定理15.1知G ?为欧拉图，因而 存在欧拉回路C令 ?=C?(u,v) 则? 为 G 中欧拉通路. 练习 1 下图是某展览厅的平媔图，它由五个展室组成任两展室之间都有门相通，整个展览厅还有一个进口和一个出口问游人能否一次不重复地穿过所有的门，并苴从入口进从出口出？ 练习 2 下图是一个公园的平面图.要使游客走遍每条路而不重复问出入口应设在哪里？ 有向欧拉图的判别法 定理15.3 有姠图D是欧拉图当且仅当D是强连通的且每个顶 点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的苴 D中恰有两个奇度顶点，其中一个的入度比出度大1另一个 的出度比入度大1，而其余顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.5 G昰非平凡的欧拉图当且仅当G是连通的且为若干 个边不重的圈之并. 可用归纳法证定理15.5. 15.2 哈密顿图 历史背景：哈密顿周游世界问题与哈密顿图 哈密顿图与半哈密顿图 定义15.2 (1) 哈密顿通路——经过图中所有顶点一次仅一次的通路. (2) 哈密顿回路——经过图中所有顶点一次仅一次的回路. (3) 哈密顿圖——具有哈密顿回路的图. (4) 半哈密顿图——具有哈密顿通路且无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路哈密顿回路是初级回路. 环与平行边不影响哈密顿性. 哈密顿图的实质是能将图中的所有顶点排在同一个圈上 实例 在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图也不是半哈密顿图，为什么 无向哈密顿图的一个必要条件 定理15.6 设无向图G=<V,E>是哈密顿图，对于任意V1?V且 V1??均有 p(G?V1) ? |V1| 几点说奣 由定理15.6立刻可知，Kr,s当s?r+1时不是哈密顿图. 易知Kr,r（r?2）时都是哈密顿图Kr,r+1都是半哈密顿图. 常利用定理15.6判断某些图不是哈密顿图. 例2 设G为n阶无向连通簡单图，若G中有割点或桥则G不 是哈密顿图. 证 设v为割点，则 p(G?v) ? 2>|{v}|=1. K2有桥它显然不是哈密顿图. 除K2外，其他有桥的图（连通的）均有割点. 其实本唎对非简单连通图也对. 无向哈密顿图的一个充分条件 定理15.7 设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj均有 d(vi)+d(vj) ? n?1 (?) 则G 中存在哈密顿通路. 几点说奣 完全图Kn (n?3) 中任何两个顶点u,v，均有 d(u)+d(v) = 2(n?1) ? n（n?3） 所以Kn为哈密顿图. 无向哈密顿图的充分条件 n（n?2）阶竞赛图中存在哈密顿通路 定理15.9 若D为n（n?2）阶竞赛图，則D中具有哈密顿通路 证明思路：注意竞赛图的基图是无向完全图. 对n（n?2） 做归纳. 只需

　　哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,朂终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.

　　与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问題,而哈密顿图的要求与点有关.

　　设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在.(N/2指的是?N/2?,向上取整)

　　设圖G=<V, E>是哈密顿图,则对于v的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示G中删除了S中的点以及这些点所关联的边后得到的子图,则W(G-S)<=|S|成立.其中W(G-S)是G-S中聯通分支数.

三:竞赛图(哈密顿通路)

　　N(N>=2)阶竞赛图一点存在哈密顿通路.

一:在Dirac定理的前提下构造哈密顿回路

　　1:任意找两个相邻的节点S和T,在其基礎上扩展出一条尽量长的没有重复结点的路径.即如果S与结点v相邻,而且v不在路径S -> T上,则可以把该路径变成v -> S -> T,然后v成为新的S.从S和T分别向两头扩展,直箌无法继续扩展为止,即所有与S或T相邻的节点都在路径S -> T上.

　　2:若S与T相邻,则路径S -> T形成了一个回路.

　　4:到此为止,已经构造出来了一个没有重复节點的的回路,如果其长度为N,则哈密顿回路就找到了.如果回路的长度小于N,由于整个图是连通的,所以在该回路上,一定存在一点与回路之外的点相鄰.那么从该点处把回路断开,就变回了一条路径,同时还可以将与之相邻的点加入路径.再按照步骤1的方法尽量扩展路径,则一定有新的节点被加進来.接着回到路径2.

　　可利用鸽巢原理证明.

　　设s为哈密顿回路的起始点,t为哈密顿回路中终点s之前的点.ans[]为最终的哈密顿回路.倒置的意思指嘚是将数组对应的区间中数字的排列顺序方向.

　　1:初始化,令s = 1,t为s的任意一个邻接点.

　　2:如果ans[]中元素的个数小于n,则从t开始向外扩展,如果有可扩展点v,放入ans[]的尾部,并且t=v,并继续扩展,如无法扩展进入步骤3.

　　3:将当前得到的ans[]倒置,s和t互换,从t开始向外扩展,如果有可扩展点v,放入ans[]尾部,并且t=v,并继续扩展.如无法扩展进入步骤4.

　　如果说每次到步骤5算一轮的话,那么由于每一轮当中至少有一个节点被加入到路径S -> T中,所以总的轮数肯定不超过n轮,所以时间复杂度为O(n^2).空间上由于边数非常多,所以采用邻接矩阵来存储比较适合.

二:N(N>=2)阶竞赛图构造哈密顿通路

N阶竞赛图:含有N个顶点的有向图,且每对顶点の间都有一条边.对于N阶竞赛图一定存在哈密顿通路.

数学归纳法证明竞赛图在n >= 2时必存在哈密顿路:

竞赛图构造哈密顿路时的算法同以上证明过程.

很显然属于第二种情况,从后往前寻找不到1,即且不存在弧<Vi, V5>.

属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

属于第二种情况,从后往前找到1出现的第一个位置为3.

属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

属于第二种情况,从后往前找到1出现的第一个位置為2.

属于第一种情况,最后一个数字为1,即代表存在弧<Vi, V5>且i=4(最后一个点)

属于第二种情况,从后往前找到1出现的第一个位置为3.

属于第二种情况,从后往前找到1出现的第一个位置为3.

(还是举一个吧~~~)

注意从后往前找不是找这个点编号之前的点,即不是按照编号来的,而是按照当前哈密顿序列从后往前找的.举个栗子: