第二章欧拉图及哈密顿图课件

第二章第二章 第一节第一节 欧拉图欧拉图(1)(1)定义定义1 1 给定无孤立结点的无向图G,经过图G的每边一次且仅一次的迹为一条欧拉路一条欧拉路.经过图G的每边一次且仅一次的回为一条欧拉回路一条欧拉回路.说明:(1)由定义,含有欧拉路(回)的图显然是连通的;(2)欧拉路是迹(边互不重复),但不是严格意义上的路.定理定理1 1 连通图G具有欧拉回路当且仅当其每个顶点的度数为偶数.欧拉路欧拉路(2)证明:必要性必要性:不妨设C是从顶点x1开始的无向图G的一条欧拉回路.对该回路中的任何一个内部点xi而言,每出现一次,其度数必增加2,对x1来讲,回路最后在该点结束,当然其度数也为偶数.充分性充分性:若G是连通无向图,作G的一条最长回C,并假设C不是欧拉回路.这样,在C中必存在xkV(C)及关联xk的边e=xk,x1 C;又deg(x1)为偶数,所以存在e1=x1,x2,e2=x2,x3,en=xn,xk,这样在G中又找到一条回C,若G=CUC,则结论成立,反之,继续寻找,总可以找到符合条件的回.第二章 欧拉图与哈密顿图(2)定理定理2 连通图G具有欧拉路而无欧拉回路,当且仅当G恰有两个奇数度顶点.证证:必要性必要性:设连通图G从顶点a到顶点b有欧拉路C,但不是欧拉回路.在欧拉路C中,除第一边和最后一边外,每经过G中顶点xi(包括a和b),都为顶点xi贡献2度,而C的第一边为a贡献1度,C的最后一条边为b贡献1度.因此,a和b的度数均为奇数,其余结点度数均为偶数.充分性充分性:设连通图设连通图G恰有两个奇数度结点恰有两个奇数度结点,不妨设为不妨设为a和和b,在图在图G中添加一条边中添加一条边e=a,b得得G,则则G的每的每个结点的度数均为偶数个结点的度数均为偶数,因而因而G中存在欧拉回路中存在欧拉回路,故故G中必存在欧拉路中必存在欧拉路.定义2 给定有向图D,经过D中每边一次且仅一次的有向迹称为D的有向欧拉路有向欧拉路.经过D中每边一次且仅一次的有向闭迹(回),称为有有向欧拉回路向欧拉回路.第二章 欧拉图与哈密顿图(3)定理定理3 具有弱连通性的有向图G具有有向欧拉回路,当且仅当当且仅当G的每个结点的入度等于出度.具有弱连通性的有向图G具有有向欧拉路,当且仅当且仅当当在G中,一个结点的入度比出度大1,另一个结点的入度比出度小1,而其余每个结点的入度等于出度.定义定义3 含有欧拉回路的无向连通图与含有向欧拉回路的弱连通有向图,统称为欧拉图欧拉图.求求Euler图的图的Euler回路的回路的Fleury算法算法.(1)任意选取一个顶点v0,置W0=v0;(2)假定迹(若是有向图,则是有迹)Wi=v0e1v1eivi已经选出,则用下列方法从E(G)-e1,e2,ei中取ei+1;(a)ei+1与vi关联(若是有向图,ei+1 以vi为起点)(b)除非没有别的边可选择,ei+1不是 Gi=G-e1,e2,ei的割边.(3)当(2)不能执行时,停止.否则让i+1 i,转(2).定理定理4 若若G是是Euler图图,则则Fleury算法终止时得算法终止时得到的迹是到的迹是Euler回路。回路。定义1 给定无向图G,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿路.若存在一条闭路经过图G的每个结点一次且仅一次,这条闭路称为哈密顿回路.第二节 哈密顿图(1)第二节 哈密顿图(1)定义2 给定有向图D,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿有向路.若存在一条闭路经过图G的每个结点一次且仅一次,这条有向闭路称为哈密顿有向回路.第二节 哈密顿图(1)定义3 具有哈密顿回路的无向图与具有哈密具有哈密顿回路的无向图与具有哈密顿有向回路的有向图顿有向回路的有向图,统称为哈密顿图统称为哈密顿图.例1 对于完全图Kn(n3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n3)是哈密顿图.说明:判断一个给定的图是否为哈密顿图,是图论中尚未解决的难题之一,下面介绍若干必要条件和充分条件.第二节 哈密顿图(2)定理1 设任意n(n3)阶图G,对所有不同非邻接顶点x和y,若deg(x)+deg(y)n,则G是哈密顿图.证明:仅就G是无向图加以证明.假设定理不成立.则存在一个阶为n(n3),满足定理条件且边数最多的非哈密顿图,即G是一个非哈密顿图且对G的任何两个非邻接点x1和x2,图G+边x1,x2是哈密顿图.因为n3,所以G不是完全图.设u和v是G的两个顶点.因此G+边u,v是哈密顿图.且G+边u,v是哈密顿回路一定包含边u,v(不妨设为u=u1,v=un).故在G中存在一条u-v路T=u1u2un 包含G中每个顶点.若u1,uiE(G)(2in),则ui-1,unE(G).否则u1uiui+1 unui-1ui-2u1是G的一个哈密顿回路,故对u2,u3,un-1中每一个邻接到u1的顶点存在一个u1,u3,un-1中与un不邻接的顶点,故deg(un)n-1-deg(u1),所以deg(u)+deg(v)n-1矛盾.定理定理2 设u和v是n阶图G的不同非邻接点,且deg(u)+deg(v)n,则G+边u,v是哈密顿图当且仅当G是哈密顿图.定义定义4 给定n阶图G,若将图G度数之和至少是n的非邻接点用一条边连接起来得图G,对图G重复上述过程,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包,记作C(G).定理定理3 一个图是哈密顿图当且仅当它的闭包是哈密顿图.定理定理4 设G是阶至少为3的图,如果G的闭包是完全图,则G是哈密顿图.定理定理5 如果G是一个n阶(n3)任意图,且对G的每个顶点x,都有deg(x)n/2,则G是哈密顿图.说明:由哈密顿图的定义可知,哈密顿图有向图必是强连通的,哈密顿无向图必无割点.8.哈密顿图(4)定理5 若G是一个哈密顿图,则对于V(G)的每个非空真子集S,其中W(G-S)为G-S的分支数.证明:设C是G的一个哈密顿回路,则对于V(G)的任意一个非空真子集S,均成立 由于C-S为G-S的一个生成子图,因而W(G-S)W(C-S),故 9.哈密顿图哈密顿图(5)说明:定理6只是一个必要条件,如下的彼特森图,尽管有 但它不是哈密顿图.10.哈密顿图哈密顿图(6)例例1.11个学生要共进晚餐个学生要共进晚餐,他们将坐成一个圆桌他们将坐成一个圆桌,计划计划要求每次晚餐上要求每次晚餐上,每个学生有完全不同的邻座每个学生有完全不同的邻座.这样这样能共进晚餐几次能共进晚餐几次.分析分析:如何将该问题转化成图论中的相关问题如何将该问题转化成图论中的相关问题.实际上实际上,可以这样可以这样来构造一个图来构造一个图,即以每个学生看作图的顶点即以每个学生看作图的顶点,以学生的邻座关以学生的邻座关系作为图的系作为图的的边的边,这样学生每次进餐的就坐方式就对应一个这样学生每次进餐的就坐方式就对应一个哈密顿回路哈密顿回路.两次进餐中两次进餐中,每个学生有完全不同的邻座对应着每个学生有完全不同的邻座对应着两个没有公共边的哈密顿回路两个没有公共边的哈密顿回路.因为每个学生都可以与其余因为每个学生都可以与其余学生邻座学生邻座,故问题转化为在图故问题转化为在图K11中找出所有没有公共边的哈中找出所有没有公共边的哈密顿回路的个数密顿回路的个数.11.哈密顿图哈密顿图(7)K11中共有中共有 条边条边,而而K11中每条哈密顿回路的长中每条哈密顿回路的长度为度为11,因此因此K11中最多有中最多有55/11=5条没有公共边的哈条没有公共边的哈密顿回路密顿回路,构造方法为构造方法为:设第一条哈密顿回路为设第一条哈密顿回路为(1,2,3,11,1),将将1固定在圆心固定在圆心,其余固定在圆周上其余固定在圆周上,如如图图(1)所示所示,然后将图的顶点旋转然后将图的顶点旋转i 3600/10(i=1,2,3,4),从而就得到另外从而就得到另外4个哈密顿回路个哈密顿回路.12.12.哈密顿图哈密顿图(8)(8)1 (3,2,4,6)5 7(5,3,2,4)(2,4,6,8)3 9(7,5,3,2)(4,6,8,10)2 11(9,7,5,3)(6,8,10,11)4 10(11,9,7,5)(8,10,11,9)6 8(10,11,9,7)图图1 1应用定理：应用定理：设u和v是n阶图G的不同非邻接点,且deg(u)+deg(v)n,则G+边u,v是哈密顿图例2.有n个人,任意两个人合起来认识其余的n-2个人,证明:当n4时,这n个人能站成一圈,使每一个人的两旁站着自己认识的人.证明:构造简单无向图G=,其中V中的n个结点表示这n个人,G中的边表示他们间的认识关系.对u,vV(G),显然d(u)+d(v)n-2,即其余n-2个结点必与u或v邻接.(1)若u,v相邻,则d(u)+d(v)2+n-2=n;(2)若u与v不相邻,如果d(u)+d(v)=n-2,则V-u,v中恰有n-2个结点(n4,故V-u,v),其中每个结点只能与u,v中的一个结点相邻.不妨设aV-u,v,且a与u相邻,a与v不相邻,此时对于结点a与u来说,都不与v相邻,这与已知矛盾,所以 d(u)+d(v)n-2,即d(u)+d(v)n-1.若d(u)+d(v)=n-1,由于n4,在结点集V-u,v中至少有两个结点a和b,其中a与u和v都相邻,而b只与u和v中的一个相邻,不妨设b与u相邻,此时v与与b和和u都不相邻,显然与已知矛盾,因此d(u)+d(v)n-1,即 d(u)+d(v)n 综上所述,对u,vV(G),都有d(u)+d(v)n.因此G中存在一条哈密顿回路,从而这n个人能站成一圈,使得每一个人的两旁站着自己认识的人.第三节第三节 并行运算图论模型与格雷码并行运算图论模型与格雷码 串行计算机串行计算机:传统的计算机一般称为传统的计算机一般称为串行计算机串行计算机,即执行程序是一次完成一个操作即执行程序是一次完成一个操作.实际上实际上,为解决问为解决问题而写的算法都设计成一次执行一步题而写的算法都设计成一次执行一步,这样的算法这样的算法称为称为串行的串行的.到目前为止到目前为止,几乎所有书本描述的算法几乎所有书本描述的算法都是串行的都是串行的.然而在有些问题上然而在有些问题上,如气象模拟如气象模拟,医学图像及密码医学图像及密码分析等许多高强度计算问题分析等许多高强度计算问题,即使在超级计算机上即使在超级计算机上,也不能通过串行操作在合理时间范围内解决也不能通过串行操作在合理时间范围内解决;而且而且对计算机的运行速度来讲对计算机的运行速度来讲,还存在着物理上的限制还存在着物理上的限制,即总有问题不能用串行操作在合理长度的时间之内解决.另外,随着硬件价格的下降,使得制造并行计算机成为可能.并行计算机并行计算机并行计算机并行计算机就是使用多个处理器实现在同一时间执行多条指令.并行算法就是把问题分成可同时解决的若干子问题,其单个指令流控制着算法的执行,包括把子问题送到不同的处理器,以及把子问题的输入和输出定向到适当的处理器.采用并行处理,一个处理器需要另一个处理器产生的输出.因此.处理器需要互联.用图来描述带有多重处理器的计算机里处理器的互联网络,是一种十分便利的方法,即所谓的并行运算图论模型.在第一章中介绍的n维立方体Qn中,有2n(n0)个处理器,每个处理器有自己的内存,在一个单位时间内,n维立方体中的每个处理器同时处理一条指令,然后与相邻的处理器通信.若一个处理器要与一个不相邻的处理器通信,第一个处理器要发送一些信息,这包括路径信息及接受者的最终目的地.当然这要花费数个时间段.许多计算机已经根据n维立方体Qn的模型制造和运行.下面将证明n维立方体Qn中存在哈密顿回路,为此先介绍格雷码格雷码.格雷码格雷码是以弗兰克.格雷的名字命名的,在20世纪40年代,他为了把传送数字信号过程中的错误的影响降到最低而发现的.下面介绍格雷码的有关定义和构造定理.v定义定义1 n 阶格雷码是序列阶格雷码是序列s1,s2,st,(t=2n),v其中每个其中每个si是是n位二进制串，满足位二进制串，满足v（1）每个）每个n位二进制串都出现在序列中；位二进制串都出现在序列中；v（2）si与与si+1只有一位不同；只有一位不同；v（3）st和和s1只有一位不同。只有一位不同。定理1令G1表示序列，由Gn-1根据以规则来定义Gn:（1）令 表示序列Gn-1的逆序；（2）令 表示在序列G的每个成员前加0所得的序列；（3）令 表示在序列 的每个成员前加1所得的序列；（4）令G为由 后加上 组成的序列。例1从G1开始构造G3。G 1 0 1 1 0 00 01 11 10G2 00 01 11 10 10 11 01 00 000 001 011 010 110 111 101 100G3 000 001 011 010 110 111 101 100推论推论.对于每个正整数对于每个正整数n 2，n维立方体都维立方体都包含一个哈密顿回路。包含一个哈密顿回路。0000000110011000001000111011101001100111111111100100010111011100例例2 证明任一个有限集合的全部子集可以这样排证明任一个有限集合的全部子集可以这样排列顺序使任何相邻的两个子集列顺序使任何相邻的两个子集仅相差一个元素仅相差一个元素.证明证明:设此有限集为设此有限集为A=a1,a2,an,用长为用长为n的二进制的二进制数列对应它的数列对应它的2n个子集个子集:当且仅当子集中含有子集中含有A的第的第i个元素时个元素时,数列的第二个数码为数列的第二个数码为1,否则为否则为0.以这以这2n个数个数列为顶点列为顶点,当且仅当数列仅一个同位数码相异时当且仅当数列仅一个同位数码相异时,该两该两顶点间连一边顶点间连一边,得到一个图得到一个图G.显然图显然图G为为n维立方体维立方体.而而n维立方体为哈密顿图维立方体为哈密顿图.按照一条哈密顿回路的顺序排按照一条哈密顿回路的顺序排列对应子集即可列对应子集即可.第四节第四节 算法的时间复杂性算法的时间复杂性一个算法是一个算法是有限指令的集合.有限性有限性:任何算法都会在有限条指令执行完后结束。任何算法都会在有限条指令执行完后结束。确定性确定性:算法的每一步有精确的定义。输入有零个或算法的每一步有精确的定义。输入有零个或多个输入，且输入取自特定的对象集合。多个输入，且输入取自特定的对象集合。输出输出 :有一个或多个输出与输入有某种特定关系。有一个或多个输出与输入有某种特定关系。唯一性唯一性 :每一步执行后所得到的中间结果是唯一的，每一步执行后所得到的中间结果是唯一的，且仅依赖于输入和先前步骤的结果且仅依赖于输入和先前步骤的结果.通用性通用性:算法适用于一类输入。算法适用于一类输入。问题是要求回答的提问通常有几个参数它们的值问题是要求回答的提问通常有几个参数它们的值是特定的，取自定义域。是特定的，取自定义域。问题的描述问题的描述:是对参数进行描述，指出其解是满足是对参数进行描述，指出其解是满足什么性质的命题。什么性质的命题。实例实例 :给问题的全体参数都指定了确定的值便得给问题的全体参数都指定了确定的值便得到一个问题的实例。到一个问题的实例。A A是问题是问题P P的算法，若算法的算法，若算法A A对问题对问题P P的每个实例都的每个实例都给出正确答案。给出正确答案。问题问题P P算法可解，若存在一个算法解答问题算法可解，若存在一个算法解答问题P P。算法分析算法分析 是指通过分析得到算法所需的时间和空间是指通过分析得到算法所需的时间和空间的估计量。的估计量。算法的复杂度是指执行算法所需的时间和空间的量。算法的复杂度是指执行算法所需的时间和空间的量。定义定义1 令令f和和g为从整数集合或实数集合到实数集合为从整数集合或实数集合到实数集合的函数，如果存在常数的函数，如果存在常数c和和k，使得只要，使得只要x k,就有就有 f(x)c g(x)则称则称f(x)是是O(g(x)记为记为f(x)=O(g(x)读作读作f(x)是是O(g(x)定理定理1:令令f(x)=an xn+an-1 xn-1+a1 x+a0其中其中a0、a1、an-1、an为实数，则为实数，则f(x)=O(xn)定理定理2 设设f1(x)=O(g1(x)、f2(x)=O(g2(x)，则，则f1(x)+f2(x)=O(max(g1(x)、g2(x)）。）。定理定理3 设设f1(x)=O(g1(x)、f2(x)=O(g2(x)，则，则f1(x)*f2(x)=O(g1(x)*g2(x)。例例1 对于正整数对于正整数n，给出，给出n!和和logn!的大的大O估计估计.解解:n!=1*2*3*n nn,故故n!=O(nn),又又logn!lognn=nlogn,所以所以logn!=O(nlogn).例例2 给出f(n)=3n*logn!+(n2+3)*logn的大O估计,其中n是正整数。解:logn!=O(nlogn),故3n*logn!=O(n2logn)所以f(n)=O(n2logn).例例3 给出f(x)=(x+1)log(x2+1)+3x2的大O估计。解:当x1时,x2+12x2;当x2时,Log(x2+1)log(2x2)3logx,故Log(x2+1)=O(logx),所以(x+1)Log(x2+1)=O(xlogx)又x1时,xlogx x2,所以f(x)=O(x2).复杂性复杂性术语术语复杂性复杂性术语术语O（1）O(logn)O(n)O(nlogn)常数复杂性常数复杂性对数复杂性对数复杂性线性复杂性线性复杂性nlogn复杂性复杂性O（nk）O(bn),b 1O(n!)多项式复杂性多项式复杂性指数复杂性指数复杂性阶乘复杂性阶乘复杂性易处理的，能用多项式最坏情况复杂性的算法解决的易处理的，能用多项式最坏情况复杂性的算法解决的问题，否则称为问题，否则称为不易处理的不易处理的.P问题问题:易处理的问题易处理的问题.NP问题：至今没有找到多项式算法，又不能证明它不问题：至今没有找到多项式算法，又不能证明它不存在多项式算法的一类问题存在多项式算法的一类问题.NPC问题：其中任何一个问题能用一个多项式时间最问题：其中任何一个问题能用一个多项式时间最坏情况算法解答的一类问题。坏情况算法解答的一类问题。例例4 冒泡排序冒泡排序 它把一个列表排列成升序；相继地比较它把一个列表排列成升序；相继地比较相邻的元素，若它们顺序不对，则交换它们。试分析冒相邻的元素，若它们顺序不对，则交换它们。试分析冒泡排序泡排序 的最坏时间复杂度。的最坏时间复杂度。O(n2)12343 2 2 2 2 3 3 3 4 4 4 11 1 1 4 5 5 5 522 233 111 344 455 5 2 11 2 3 3 4 4 5 5 1 2 3 4 5 冒泡排序解答冒泡排序解答第五节 最短路路问题1.加权图:边上有数的图称为加权图;该数称为边的权。2.最短路问题:如何求两个结点之间的最短路.3.Dijkstra算法:这是荷兰计算机科学教授Edsger W.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖图灵奖,这是计算机科学中最具声望的奖项.迪克斯曲拉算法是求出一个连通加权简单图中从结点a到结点z的最短路.边i,j的权(i,j)0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.4.Dijkstra算法流程算法流程Procedure Dijkstra(G:所有权为正的加权连通简单图所有权为正的加权连通简单图)G带有顶点带有顶点a=v0,v1,vn=z和权和权w(vi,vj),若若vi,vj不是不是G中的边中的边,则则w(vi,vj)=)For i:=1 to n L(vi):=L(a):=0 S:=初始化标记初始化标记,a的标记为的标记为0,其余结点标记为其余结点标记为,S是空集是空集While z S beginu:=不属于不属于S的的L(u)最小的一个顶点最小的一个顶点 S:=S uFor 所有不属于所有不属于S的顶点的顶点v If L(u)+w(u,v)L(v)then L(v):=L(u)+w(u,v)这样就给这样就给S中添加带最小标记的顶点并且更新不在中添加带最小标记的顶点并且更新不在S中的顶点中的顶点的标记的标记End L(z)=从从a到到z的最短路的长度的最短路的长度.例1.用Dijkstra算法求下图所示的加权图中顶点a与z之间最短路的长度.（见65页）a4b5d2110c8e263zv定理1 Dijkstra算法求出连通简单无向图的中两点之间的最短路的长度。v定理2 Dijkstra算法使用O(n2)次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间的最短路的长度。vDijkstra算法可以推广到求加权有向图的最短路。（p68）v定理定理3 设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有有限长的有向路，那么式（2）有唯一有限解。v定理4-5见p69.Floyd算法 Dijkstra算法只求出一个特定顶点到其他各顶点的最短路.但在许多实际问题中,需求出任意两点之间的最短路,如全国各城市之间最短的航线,选址问题等.Floyd算法可以比较好地解决这一问题.为介绍Floyd算法,先定义矩阵的两种运算.定义1.已知矩阵A=(aij)ml,B=(bij)ln,规定C=AB=(cij)mn,其中cij=min(ai1+b1j,ai2+b2j,ail+blj).定义2.已知矩阵A=(aij)mn,B=(bij)mn,规定D=AB=(dij)mn,其中dij=min(aij,bij).可以利用上面定义的运算求任意两点间的最短距离.已知n阶加权简单图G,设D=(dij)nn是图G的边权矩阵即dij=w(i,j)(若G是有向图,则dij=w),若结点i到结点j无边相连时,则取dij=.然后依次计算出矩阵D2,D3,Dn及S,其中D2=DD=(dij2)nnD3=D2 D=(dij3)nn,Dn=Dn-1 D=(dijn)nnS=DD2D3Dn=(Sij)nn 由定义可知,dijk表示从结点i到结点j经k边的路(在有向图中即为有向路)中的长度最短者.这就是Floyd算法.请同学们分析一下Floyd算法的时间复杂度.例2.利用Floyd算法求下图中任意两点间最短有向路的长度.(p71-73)v121v27v6v41332v61Warshall算法步骤算法步骤算法原理算法原理 求路径矩阵的方法求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R)(即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径nRi j算法原理算法原理查找最短路路径的方法查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：实质上是考虑经过n次结点转换每一次保留最短路的长度。见P74.第六节旅行推销员问题和中国投递员问题（NPC问题）一。旅行推销员问题（TSP）（最邻近算法给出旅行推销员问题的近似解）（最邻近算法给出旅行推销员问题的近似解）步骤如下步骤如下:（1）由任意选择的结点开始，找出于该结点邻近的）由任意选择的结点开始，找出于该结点邻近的点，形成一条有边的初始路。点，形成一条有边的初始路。（2）以）以x表示最新加到这条路上的结点，从不在路上表示最新加到这条路上的结点，从不在路上的所有结点中选一个和的所有结点中选一个和x最靠近的结点，把连接最靠近的结点，把连接x与这与这一结点的边加到这条路上，重复这一步骤直到这条路一结点的边加到这条路上，重复这一步骤直到这条路包含图中所有结点。包含图中所有结点。(3)将连接起点与最后加入的结点之间的边加到这条路将连接起点与最后加入的结点之间的边加到这条路上，就得到一条上，就得到一条Hamilton回路。回路。(即得近似解即得近似解)例例1 用用“最邻近算法最邻近算法”给出下面加权图中有给出下面加权图中有充分小权的哈密顿路充分小权的哈密顿路P76.D1218AFBEC1669 715131835132119说明:“最邻近插入方法”是“最邻近法”的一种改进方法.该方法是在每次迭代中都构成一个闭的旅行路线.求解时,在已经建立旅程以外的顶点中,寻找最临近于旅程中某个顶点的顶点,然后将其插入该旅程中,并使增加的距离尽可能小,当全部顶点收入这个旅程后,就找到了所求的最短哈密顿回路的近似解.例2 用“最邻近插入方法”找出上图中具有充分小权的哈密顿回路.定理定理1 设设P是加权连通图是加权连通图G中一条包含中一条包含G的所有边至的所有边至少一次的闭链，则少一次的闭链，则P最优的充要条件（具有最小长度）最优的充要条件（具有最小长度）是：是：（1）P中无二重以上的边；中无二重以上的边；（2）在）在G的每个圈中的每个圈中C中，重复边集中，重复边集E的长度之和不的长度之和不超过这个圈的长度的一半，超过这个圈的长度的一半，即即W(E)1/2W(C).二二.中国邮路问题中国邮路问题奇偶点作业法奇偶点作业法（1）把）把G中所有奇度顶点配成对，将每对奇度顶点之间的中所有奇度顶点配成对，将每对奇度顶点之间的一条路上的每边改为二重边，得到一个新图一条路上的每边改为二重边，得到一个新图G1，新图，新图G1中中无奇度顶点，即无奇度顶点，即G1为多重欧拉图为多重欧拉图.（2）若）若G1中某对结点间有多于两条边连接，则去掉其中偶中某对结点间有多于两条边连接，则去掉其中偶数条边，留下一条或两条边连接这两个结点，直到每对相数条边，留下一条或两条边连接这两个结点，直到每对相邻结点至多由邻结点至多由2条边连接。得到图条边连接。得到图G2.（3）检查）检查G2的每个圈的每个圈C，若某个圈，若某个圈C上重复边集上重复边集E的权和超的权和超过这个圈的权和的一半，则将过这个圈的权和的一半，则将C按定理按定理1必要性证明中的方必要性证明中的方法进行调整，直到对法进行调整，直到对G2所有的圈其重复边的权和不超过此所有的圈其重复边的权和不超过此圈权和的一半，得到图圈权和的一半，得到图G3.（4）用）用Fleury算法求算法求G的的Euler回路回路.例例3 求下图求下图G的最优环游的最优环游p81.v1v2v3v4v5v6v7v8v9v10v11v122 4 5 5 3 6 4 6 4 65 4 4 7 9 3 8AV1 2 v10 4 v9 5 v8 V2 6 v11 4 v12 6 v75 5 4 4 7 7V3 9 v4 3 v5 8 v6B445 5 4 4 7 7993 8 8 6 4 63 6C446 4 66 65 4 4 4 4 79 3 83 6D5 9444 4 3 32 4 55 3 6 4666642例4.设G是分划为X,Y的二分图,且则G一定不是哈密顿图.(利用分支数反证)例5.设简单图G=则G是哈密顿图.证明：G中的任意两点u,v，其度数分别为d(u),d(v)对于图G-u,v都有 m-d(u)-d(v)(n-2)(n-3)/2又因为 mCn-12+2 d(u)+d(v)(n-1)(n-2)/2+2-(n-2)(n-3)/2 =n-2+2 =n由定理1 可得 G是哈密顿图。