第二讲 图论基础

第二讲：图论模型7月30日图论基础专题（老内容）一图的基本概念二三最短路问题及其算法四最小生成树问题图的矩阵表示新内容欧拉图与哈密顿图匹配问题网络流图的染色

数学建模-图论42023年2月5日

一、图的基本概念若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F

).

设G=(V,E)是一个图,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,则称v0v1…

vk是G的一条通路.

如果通路中没有相同的顶点,则称此通路为路径,简称路.始点和终点相同的路称为圈或回路.

一、图的基本概念数学建模-图论顶点u与v称为连通的，如果存在u到v通路，任二顶点都连通的图称为连通图，否则，称为非连通图。极大连通子图称为连通分图。

连通而无圈的图称为树,常用T表示树.树中最长路的边数称为树的高，度数为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的底图是树，则称G是有向树，也简称树。

一、图的基本概念数学建模-图论邻接矩阵（结点与结点的关系）关联矩阵（结点与边的关系）路径矩阵（任意两结点之间是否有路径）可达性矩阵直达矩阵等等……二、图的矩阵表示数学建模-图论1有向图的邻接矩阵

A=(aij)n×n

（n为结点数）

例1：写出右图的邻接矩阵：解：二、图的矩阵表示数学建模-图论2有向图的权矩阵A=(aij)n×n

（n为结点数）

例2：写出右图的权矩阵：解：二、图的矩阵表示数学建模-图论3有向图的关联矩阵A=(aij)n×m

（n为结点数m为边数）

有向图：无向图：

二、图的矩阵表示数学建模-图论例3：分别写出右边两图的关联矩阵解：分别为：

二、图的矩阵表示

数学建模-图论

二、图的矩阵表示（应用实例及解法分析）数学建模-图论商人过河问题：假如有三个商人各带一名随从要过河，只有一条船，每次最多只能坐两个人。为安全起见，商人数不能少于随从数，否则随从会杀人越货。船过一次河需要5分钟，问最短几分钟能使他们都过去？用邻接矩阵来解决：设(m,n,l)表示左岸商人m人，随从n人；设(m,n,r)表示右岸有商人m人，随从n人。从左岸到右岸去，所有可能的状态为：v1=(3,3,l),v2=(3,2,l),v3=(3,1,l),v4=(3,0,l),v5=(2,2,l),v6=(1,1,l),v7=(0,3,l),v8=(0,2,l),v9=(0,1,l),v10=(3,3,r),v11=(3,2,r),v12=(3,1,r),v13=(3,0,r),v14=(2,2,r),v15=(1,1,r),v16=(0,3,r),v17=(0,2,r),v18=(0,1,r).

二、图的矩阵表示（应用实例及解法分析）数学建模-图论V10v11v12v13v14v15v16v17v18v1

v2v3v4v5v6v7v8v9渡河可以理解为上面状态的转移，例如状态v1渡河一次可以转化为其他状态v15v17v18，其他状态也易列出。以V={v1,

v2,...v18}为顶点集，当两种状态可以互相转化时，就在相应的来那个顶点间连一边，从而建立一个二分图G=<V,E>，如右图所示。G=<V,E>的邻接矩阵为：

二、图的矩阵表示（应用实例及解法分析）数学建模-图论V10v11v12v13v14v15v16v17v18v1

v2v3v4v5v6v7v8v9其中，矩阵B为：记a(k)ij为Ak中的（i,j）元，目标是使a(k)1,10不等于0的最小的自然数k.

利用matlab容易计算出k=11，且a(11)1,10=4,即小船至少11次才能把所有人全部运到右岸，说明共有4种不同的过河方案。继续计算可得出a(19)1,10=45060，如果允许小船过河19次的话，共有45060中不同的方案。若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图,记为G=(V,E,F

).

设G=(V,E)是一个图,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,则称v0v1…

vk是G的一条通路.如果通路中没有相同的顶点,则称此通路为路径,简称路.对于赋权图，路的长度（即路的权）通常指路上所有边的权之和。最短路问题：求赋权图上指定点之间的权最小的路。

三、最短路问题及其算法数学建模-图论重要性质：若v0v1…

vm是G中从v0到vm的最短路,则对1≤k≤m,v0v1…

vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路。数学建模-图论

三、最短路问题及其算法

设有给定连接若干城市的公路网，寻求从指定城市到各城市的最短路线。

2、应用实例：最短路问题

问题的数学模型:

三、最短路问题及其算法172023年2月5日数学建模-图论182023年2月5日

三、最短路问题及其算法数学建模-图论254647109137106648192023年2月5日

三、最短路问题及其算法数学建模-图论202023年2月5日

三、最短路问题及其算法数学建模-图论212023年2月5日

三、最短路问题及其算法数学建模-图论222023年2月5日

三、最短路问题及其算法数学建模-图论254647109137106648232023年2月5日

三、最短路问题及其算法数学建模-图论242023年2月5日

三、最短路问题及其算法数学建模-图论252023年2月5日

三、最短路问题及其算法数学建模-图论262023年2月5日

三、最短路问题及其算法数学建模-图论254647109137106648272023年2月5日

三、最短路问题及其算法数学建模-图论282023年2月5日

三、最短路问题及其算法数学建模-图论292023年2月5日

三、最短路问题及其算法数学建模-图论254647109137106648302023年2月5日

三、最短路问题及其算法数学建模-图论312023年2月5日数学建模-图论

三、最短路问题及其算法322023年2月5日数学建模-图论求v1到v6的最短路问题.

三、最短路问题及其算法332023年2月5日数学建模-图论从上图中容易得到v1到v6只有两条路：v1v3v6和v1v4v6.

而这两条路都是v1到v6的最短路.

三、最短路问题及其算法顶点u与v称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图，否则，称为不连通图。极大连通子图称为连通分图。

连通而无圈的图称为树,常用T表示树.树中最长路的边数称为树的高的度为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。设G是有向图，如果G的底图是树，则称G是有向树，也简称树。

四、最小生成树问题及其算法数学建模-图论若任意一个连通的图G=<V,E>的生成子图T=<V’,E’>(V’=V,E’为E的子集)为树,这棵树T称为图G的生成树.设T是图G的一棵生成树,用F(T)表示树T中所有边的权数之和,F(T)称为树T的权.一个连通图G的生成树一般不止一棵,图G的所有生成树中权数最小的生成树称为图G的最小生成树.数学建模-图论

四、最小生成树问题及其算法怎样找出最小生成树？？？G

T1T2T3T4T5T6T7T8T1至T8是图G的生成树数学建模-图论

四、最小生成树问题及其算法Kruskal算法思想：在不形成圈得条件下，优先挑选权小的边形成生成树。76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7数学建模-图论

四、最小生成树问题及其算法注：算法构造的最小生成树的边集为E1；标号l

具有性质：当且仅当u、v之间有一条仅由E1

中的边形成的路时，l(u)=l(v)，因此在步骤(2)发现l(u)=l(v)时，(u,v)不能放入E1，否则会形成一个圈。

数学建模-图论

四、最小生成树问题及其算法392023年2月5日

四、最小生成树问题及其算法数学建模-图论402023年2月5日

四、最小生成树问题及其算法数学建模-图论412023年2月5日

四、最小生成树问题及其算法数学建模-图论运行结果如下：T=135163266674c=26上述例题的matlab程序如下：b=[11223334556;26364677677;24458378376];Krusf(b,1);76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7422023年2月5日

四、最小生成树问题及其算法数学建模-图论

432023年2月5日

四、最小生成树问题及其算法数学建模-图论442023年2月5日

四、最小生成树问题及其算法数学建模-图论452023年2月5日

四、最小生成树问题及其算法数学建模-图论

运行结果如下：T=116663263574c=24336876788334245v1v2v3v4v5v6v7欧拉图与哈密顿图欧拉图定义15.1通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。说明 欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路。举例欧拉图半欧拉图无欧拉通路欧拉图无欧拉通路无欧拉通路无向欧拉图的判定定理定理15.1无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。证明 若G是平凡图，结论显然成立。下面设G为非平凡图，设G是m条边的n阶无向图，并设G的顶点集V＝{v1,v2,…,vn}。必要性。因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，vi,vj∈V，vi,vj都在C上，因而vi,vj连通，所以G为连通图。 又vi∈V，vi在C上每出现一次获得2度， 若出现k次就获得2k度，即d(vi)＝2k， 所以G中无奇度顶点。定理15.1的证明充分性。由于G为非平凡的连通图可知，G中边数m≥1。对m作归纳法。(1)m＝1时，由G的连通性及无奇度顶点可知，

G只能是一个环，因而G为欧拉图。(2)设m≤k(k≥1)时结论成立，要证明m＝k+1时，结论也成立。 由G的连通性及无奇度顶点可知，δ(G)≥2。 无论G是否为简单图，都可以用扩大路径法证明G中必含圈。定理15.1的证明设C为G中一个圈，删除C上的全部边，得G的生成子图G，设G有s个连通分支G1,G2,…,Gs，每个连通分支至多有k条边，且无奇度顶点，并且设Gi与C的公共顶点为v*ji，i＝1,2,…,s，由归纳假设可知，G1,G2,…,Gs都是欧拉图，因而都存在欧拉回路Ci，i＝1,2,…,s。最后将C还原（即将删除的边重新加上），并从C上的某顶点vr开始行遍，每遇到v*ji，就行遍Gi中的欧拉回路Ci，i＝1,2,…,s，最后回到vr，得回路vr…v*j1…v*j1…v*j2…v*j2…v*js…v*js…vr，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路（演示这条欧拉回路），故G为欧拉图。定理15.2无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。证明

必要性。设G是m条边的n阶无向图，因为G为半欧拉图， 因而G中存在欧拉通路(但不存在欧拉回路)， 设Г＝vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路，vi0≠vim。

v∈V(G)，若v不在Г的端点出现，显然d(v)为偶数， 若v在端点出现过，则d(v)为奇数， 因为Г只有两个端点且不同，因而G中只有两个奇数顶点。 另外，G的连通性是显然的。半欧拉图的判定定理定理15.2无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。证明

充分性。设G的两个奇度顶点分别为u0和v0， 对G加新边（u0,v0），得G＝G∪(u0,v0)， 则G是连通且无奇度顶点的图， 由定理15.1可知，G为欧拉图， 因而存在欧拉回路C，而C＝C-(u0,v0)为G中一条欧拉通路， 所以G为半欧拉图。半欧拉图的判定定理有向欧拉图的判定定理定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。(举例)定理15.5

G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。例15.1例15.1设G是非平凡的且非环的欧拉图，证明： (1)λ(G)≥2。 (2)对于G中任意两个不同顶点u,v，都存在简单回路C含u和v。证明(1)由定理15.5可知，e∈E(G)，存在圈C，e在C中， 因而p(G-e)＝p(G)，故e不是桥。 由e的任意性λ(G)≥2，即G是2边-连通图。(2)u,v∈V(G)，u≠v，由G的连通性可知，u,v之间必存在路径Г1，设G＝G-E(Г1)，则在G中u与v还必连通， 否则，u与v必处于G的不同的连通分支中， 这说明在Г1上存在G中的桥，这与(1)矛盾。 于是在G中存在u到v的路径Г2，显然Г1与Г2边不重， 这说明u,v处于Г1∪Г2形成的简单回路上。求欧拉图中欧拉回路的算法Fleury算法，能不走桥就不走桥

(1)任取v0∈V(G)，令P0＝v0。(2)设Pi＝v0e1v1e2…eivi已经行遍，按下面方法来从

E(G)-{e1,e2,…,ei}中选取ei+1： (a)ei+1与vi相关联； (b)除非无别的边可供行遍，否则ei+1不应该为

Gi＝G-{e1,e2,…,ei}中的桥。(3)当(2)不能再进行时，算法停止。说明 可以证明，当算法停止时所得简单回路

Pm＝v0e1v1e2…emvm(vm＝v0) 为G中一条欧拉回路。Fleury算法示例例15.2下图是给定的欧拉图G。某人用Fleury算法求G中的欧拉回路时，走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后(观看他的错误走法)，无法行遍了，试分析在哪步他犯了错误?解答此人行遍v8时犯了能不走桥就不走桥的错误，因而他没行遍出欧拉回路。 当他走到v8时，G-{e2,e3,e14,e10,e1,e8}为下图所示。此时e9为该图中的桥，而e7,e11均不是桥，他不应该走e9，而应该走e7或e11，他没有走，所以犯了错误。注意，此人在行遍中，在v3遇到过桥e3，v1处遇到过桥e8，但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。哈密顿图定义15.2经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。说明 哈密顿通路是图中生成的初级通路， 哈密顿回路是生成的初级回路。 判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路(圈)上，但这不是一件易事。 与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。例题(1)(2)是哈密顿图。(3)是半哈密顿图。(4)既不是哈密顿图，也不是半哈密顿图。定理15.6定理15.6设无向图G＝<V,E>是哈密顿图，对于任意V1V，且V1≠，均有

p(G-V1)≤|V1| 其中，p(G-V1)为G-V1的连通分支数。证明

设C为G中任意一条哈密顿回路， 易知，当V1中顶点在C上均不相邻时，

p(C-V1)达到最大值|V1|， 而当V1中顶点在C上有彼此相邻的情况时， 均有p(C-V1)＜|V1|，所以有p(C-V1)≤|V1|。 而C是G的生成子图，所以，有p(G-V1)≤p(C-V1)≤|V1|。说明 本定理的条件是哈密顿图的必要条件，但不是充分条件。 可以验证彼得松图满足定理中的条件，但不是哈密顿图。 若一个图不满足定理中的条件，它一定不是哈密顿图。推论推论设无向图G＝<V,E>是半哈密顿图，对于任意的V1V且V1≠，均有p(G-V1)≤|V1|+1证明 设P是G中起于u终于v的哈密顿通路， 令G＝G∪(u,v)(在G的顶点u,v之间加新边)， 易知G为哈密顿图， 由定理15.6可知，p(G-V1)≤|V1|。 因此，p(G-V1)＝p(G-V1-(u,v)) ≤p(G-V1)+1 ≤|V1|+1例15.3例15.3在下图中给出的三个图都是二部图。它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？易知互补顶点子集

V1＝{a,f}

V2＝{b,c,d,e}设此二部图为G1，则G1＝<V1,V2,E>。p(G1-V1)＝4>|V1|＝2，由定理15.6及其推论可知，G1不是哈密顿图，也不是半哈密顿图。例15.3设图为G2，则G2＝<V1,V2,E>，其中V1＝{a,g,h,i,c}，V2＝{b,e,f,j,k,d}，易知，p(G2-V1)＝|V2|＝6>|V1|＝5，由定理15.6可知，G2不是哈密顿图，但G2是半哈密顿图。baegjckhfid为G2中一条哈密顿通路。设图为G3。G3＝<V1,V2,E>，其中V1＝{a,c,g,h,e}，V2＝{b,d,i,j,f}，G3中存在哈密顿回路。如abcdgihjefa，所以G3是哈密顿图。例15.3的说明哈密顿通路是经过图中所有顶点的一条初级通路。哈密顿回路是经过图中所有顶点的初级回路。对于二部图还能得出下面结论： 一般情况下，设二部图G＝<V1,V2,E>，|V1|≤|V2|，且|V1|≥2，|V2|≥2，由定理15.6及其推论可以得出下面结论： (1)若G是哈密顿图，则|V1|＝|V2|。 (2)若G是半哈密顿图，则|V2|＝|V1|+1。 (3)若|V2|≥|V1|+2，则G不是哈密顿图，也不是半哈密顿图。例15.4设G是n阶无向连通图。证明：若G中有割点或桥，则G不是哈密顿图。证明可用定理15.6证明。定理15.7定理15.7设G是n阶无向简单图，若对于G中任意不相邻的顶点vi,vj，均有

d(vi)+d(vj)≥n-1 (15.1) 则G中存在哈密顿通路。证明

首先证明G是连通图。 否则G至少有两个连通分支， 设G1,G2是阶数为n1,n2的两个连通分支， 设v1∈V(G1)，v2∈V(G2)，因为G是简单图，所以

dG(v1)+dG(v2)＝dG1(v1)+dG2(v2)≤n1-1+n2-1≤n-2

这与(15.1)矛盾，所以G必为连通图。定理15.7下面证G中存在哈密顿通路。设Г＝v1v2…vl为G中用“扩大路径法”得到的“极大路径”，即Г的始点v1与终点vl不与Г外的顶点相邻。显然有l≤n。(1)若l＝n，则Г为G中哈密顿通路。(2)若l＜n，这说明Г不是哈密顿通路， 即G中还存在着Г外的顶点。 但可以证明G中存在经过Г上所有顶点的圈。 (a) 若v1与vl相邻，即(v1,vl)∈E(G)， 则Г∪(v1,vl)为满足要求的圈。定理15.7(b)若v1与vl不相邻，设v1与Г上的vi1＝v2,vi2,…,vik相邻(k≥2) (否则d(v1)+d(vl)≤1+l-2=l-1<n-1，这与(15.1)矛盾) 此时，vl至少与vi2,…,vik相邻的顶点vi2-1,…,vik-1之一相邻 (否则d(v1)+d(vl)≤k+l-2-(k-1)＝l-1<n-1)

设vl与vir-1相邻（2≤r≤k），见下图所示。于是，回路

C＝v1v2…vir-1vlvlr-1…vi…virv1过Г上的所有顶点。定理15.7(c)下面证明存在比Г更长的路径。 因为l<n，所以C外还有顶点，由G的连通性可知， 存在vl+1∈V(G)-V(C)与C上某顶点vt相邻，见下图所示。删除边(vt-1,vt)得路径Г＝vt-1…v1vir…vlvir-1…vtvl+1比Г长度大1，对Г上的顶点重新排序，使其成为Г＝v1v2…vlvl+1，对Г重复(a)～(c)，在有限步内一定得到G的哈密顿通路。定理15.7的推论推论设G为n(n≥3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)≥n (15.2) 则G中存在哈密顿回路，从而G为哈密顿图。证明由定理15.7可知，G中存在哈密顿通路， 设Г＝v1v2…vn为G中一条哈密顿通路， 若v1与vn相邻，设边e＝(v1,vn)，则Г∪{e}为G中哈密顿回路。 若v1与vn不相邻，应用(15.2)，同定理15.7证明中的(2)类似，可证明存在过Г上各顶点的圈， 此圈即为G中的哈密顿回路。定理15.8定理15.8设u,v为n阶无向图G中两个不相邻的顶点，且d(u)+d(v)≥n，则G为哈密顿图当且仅当G∪(u,v)为哈密顿图((u,v)是加的新边)。证明 (略)。例15.5例15.5在某次国际会议的预备会议中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。解答

设8个人分别为v1,v2,…,v8，作无向简单图G＝<V,E>， 其中V＝{v1,v2,…,v8}，vi,vj∈V，且i≠j， 若vi与vj有共同语言，就在vi,vj之间连无向边(vi,vj)， 由此组成边集合E，则G为8阶无向简单图， vi∈V，d(vi)为与vi有共同语言的人数。 由已知条件可知，vi,vj∈V且i≠j，均有d(vi)+d(vj)≥8。 由定理15.7的推论可知，G中存在哈密顿回路， 设C＝vi1vi2…vi8为G中一条哈密顿回路， 按这条回路的顺序安排座次即可。哈密顿图是能将图中所有顶点都能安排在某个初级回路上的图。定理15.9定理15.9若D为n(n≥2)阶竞赛图，则D中具有哈密顿通路。证明

对n作归纳法。

n＝2时，D的基图为K2，结论成立。 设n＝k时结论成立。现在设n＝k+1。 设V(D)＝{v1,v2,…,vk,vk+1}。 令D1＝D-vk+1，易知D1为k阶竞赛图， 由归纳假设可知，D1存在哈密顿通路， 设Г1＝v1v2…vk为其中一条。定理15.9下面证明vk+1可扩到Г1中去。若存在vr(1≤r≤k)，有<vi,vk+1>∈E(D)，i＝1,2,…,r-1，而<vk+1,vr>∈E(D)，见左图所示，则Г＝v1v2…vr-1vk+1vr…vk为D中哈密顿通路。否则i∈{1,2,…,k}，均有<vi,vk+1>∈E(D)，见右图所示，则Г＝Г∪<vi,vk+1>为D中哈密顿通路。例15.6下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？(1)存在哈密顿回路，所以(1)为哈密顿图。(2)取V1＝{a,b,c,d,e}，从图中删除V1得7个连通分支，由定理15.6和推论可知，不是哈密顿图，也不是半哈密顿图。(3)取V1＝{b,e,h}，从图中删除V1得4个连通分支，由定理15.6可知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。15.3带权图与货郎担问题定义15.3给定图G＝<V,E>(G为无向图或有向图)，设W：E→R(R为实数集)，对G中任意的边e＝(vi,vj)(G为有向图时，e＝<vi,vj>)，设W(e)＝wij，称实数wij为边e上的权，并将wij标注在边e上，称G为带权图，此时常将带权图G记作<V,E,W>。设GG，

称W(e)为G的权，并记作W(G)，即W(G)＝带权图应用的领域是相当广泛的，许多图论算法都是针对带权图的。货郎担问题设有n个城市，城市之间均有道路，道路的长度均大于或等于0，可能是∞（对应关联的城市之间无交通线）。一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市，问他如何走才能使他走的路线最短？ 这就是著名的旅行商问题或货郎担问题。这个问题可化归为如下的图论问题。 设G＝<V,E,W>，为一个n阶完全带权图Kn，各边的权非负，且有的边的权可能为∞。求G中一条最短的哈密顿回路，这就是货郎担问题的数学模型。此问题中不同哈密顿回路的含义： 将图中生成圈看成一个哈密顿回路，即不考虑始点(终点)的区别以及顺时针行遍与逆时针行遍的区别。例15.7例15.7下图为4阶完全带权图K4。求出它的不同的哈密顿回路，并指出最短的哈密顿回路。解答

由于货郎担问题中不同哈密顿回路的含义可知，求哈密顿回路从任何顶点出发都可以。下面先求出从a点出发，考虑顺时针与逆时针顺序的不同的哈密顿回路。

C1＝abcda

C2＝abdca C3＝acbda

C4＝acdba

C5＝adbca

C6＝adcba带权图的说明n阶完全带权图中共存在(n-1)!/2种不同的哈密顿回路，经过比较，可找出最短哈密顿回路。n＝4时，有3种不同哈密顿回路。

n＝5时，有12种，

n＝6时，有60种，

n＝7时，有360种，…，

n＝10时，有5×9!=1814400种，…。由此可见货郎担问题的计算量是相当大的。对于货郎担问题，人们一方面还在寻找好的算法，另一方面也在寻找各种近似算法。中国邮递员问题一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1960年首次提出的，因此在国际上称之为中国邮递员问题。用图论的述语，在一个连通的赋权图G(V,E)中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小。也就是说要从包含G的每条边的回路中找一条权数最小的回路。基本要求深刻理解欧拉图与半欧拉图的定义及判别定理。会用Fleury算法求出欧拉图中的欧拉回路。深刻理解哈密顿图及半哈密顿图的定义。会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图。会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图。严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地，也不能将充分条件当成必要条件。归纳法证明示意图例15.4例15.4设G是n阶无向连通图。证明：若G中有割点或桥，则G不是哈密顿图。证明 (1)证明若G中有割点，则G不是哈密顿图。

设v为连通图G中一个割点，则V＝{v}为G中的点割集，而

p(G-V)≥2＞1＝|V| 由定理15.6可知G不是哈密顿图。 (2)证明若G中有桥，则G不是哈密顿图。 设G中有桥，e＝(u,v)为其中的一个桥。 若u,v都是悬挂边，则G为K2，K2不是哈密顿图。 若u,v中至少有一个，比如u，d(u)≥2，由于e与u关联，e为桥，所以G-u至少产生两个连通分支，于是u为G中割点。 由(1)的讨论可知，G不是哈密顿图。匹配§1最大匹配－1具体问题描述：有n个女士和n个男士参加舞会，每位女士与其中若干位男士相识，每位男士与其中若干位女士相识，问如何安排，使得尽量多配对的男女舞伴相识。f1f2m1f3f4f5m2m3m4m5§1匹配§1最大匹配－1下图就是一种分配方法：f1f2m1f3f4f5m2m3m4m5(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)

匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生配对？类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？§1最大匹配－定义定义：若图G=(V,E)的顶点可以分成X，Y两个子集，每个子集里的顶点互不相邻，这样的图称为二分图。f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义1定义：若M是图G=(V,E)的边子集，且M中的任意两条边在G中不相邻，则称M为G中的一个匹配，M中的每条边的两个端点称为是M-饱和的的。f1f2m1f3f4f5m2m3m4m5M={(f1,m2),(f2,m1),(f3,m4),(f4,m5)}§1最大匹配－定义2定义：若图G中每个顶点均被M许配时，称M为G中的一个完美匹配。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－定义3定义：图G中边数最多的匹配M，称为G中的一个最大匹配。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义4定义：若匹配M的某边和顶点v关联，称v是M-饱和的，否则就是M-不饱和的。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5饱和的不饱和的§1最大匹配－定义5定义：若M是图G的一个匹配，若从G中一个顶点到另一个顶点存在一条道路，此路径由属于M和不属于M的边交替出现组成的，则称此路径为M-交错路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}P=f1m3f4m5f2m1f5m4§1最大匹配－定义6定义：若交错路的两个端点为关于M的不饱和顶点时，称此交互道为可增广道路。M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一条可增广道路。f1f2m1f3f4f5m2m3m4m5f1f2m1f3f4f5m2m3m4m5§1最大匹配－定义8f1f2m1f3f4f5m2m3m4m5M={(f2,m5),(f3,m2),(f4,m3),(f5,m4)}P=m1f2m5f4m3f1是一条可增广道路。f1f2m1f3f4f5m2m3m4m5M={(f1,m3),(f2,m1),(f3,m2),(f4,m5),(f5,m4)}§1最大匹配－Berge定理定理7.1(Berge1957)：M为最大匹配的充要条件是：图G中不存在可增广道路。M={(f1,m3),(f2,m1),(f3,m2),(f5,m5)}f1f2m1f3f4f5m2m3m4m5[引理]

设P是匹配Ｍ-可增广道路，则PM是一个比M更大的匹配，且|PM｜＝|M|+1.[定理1](Berge)设G=(V,E)，M为G中匹配，则M为G的最大匹配当且仅当G中不存在M可增广道。[证明]

必要性：如有M-可增广道路，则有更大匹配。矛盾！充分性：如果有最大匹配M’,|M’|>|M|.考虑MM’，在可增广路中，第一条边与最后一条边都不是中的边，因而可增广路中属于的边数比不在中边数少一条。M实线边，M’虚线边MM’其中每个结点的最多与Ｍ边和一个M’边关联，每条道路是M边和M’边交互道路。其中回路包含相同数目的M边和M’边。由|M’|>|M|,必存在M’边开始，M‘边终止的M交互道路，即M-可增广道路，矛盾！§2Hall定理

设有m个人，n项工作，每个人会做其中的若干项工作，能不能适当安排，使得每个人都有工作做？w1w2m1w3w4w5m2m3m4§2Hall定理

当m>n时，肯定是不可能的，即使是m≤n也不一定。但如果每个人能做的工作越多，越容易实现。w1w2m1w3w4w5m2m3m4§2Hall定理－1Hall定理(1935)：二分图G存在一匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X任一子集A，及与A邻接的点集为N(A)，恒有：|N(A)|≥|A|。w1w2m1w3w4w5m2m3m4YX§3人员分派问题1965年，匈牙利著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。工作分配问题：现有n个人，n份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？§3匈牙利算法

匈牙利(Hungarian)算法：（1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，V1={x0}，V2=空集；（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2；（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】§3匈牙利算法例用匈牙利算法求下图的最大匹配：例x1x2y1x3x4x5y2y3y4y5§3匈牙利算法例解（1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}§3匈牙利算法例解1（3）在X中找一个非饱和点x0，V1={x0}，V2=空集（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2},V2=空集N(V1)={y2,

y3}§3匈牙利算法例解2（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1=V1∪{x5}={x2,x5}；V2=V2∪

{y3}

={y3}V1={x2},V2=空集§3匈牙利算法例解3（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}N(V1)={y2,y3,y4,y5}§3匈牙利算法例解4（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5}；V2={y3}；V1=V1∪{x3}={x2,x5,x3}；V2=V2∪

{y5}

={y3,y5}§3匈牙利算法例解5（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2；解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,

x3}；V2={y3,y5}；N(V1)={y2,y3,y4,y5}§3匈牙利算法例解6（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}V1={x2,x5,x3}；V2={y3,y5}；x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}ŧ3匈牙利算法例解7（2）若X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，V1={x0}，V2={}（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}N(V1)={y3}§3匈牙利算法例解8（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5V1={x4}；V2=空集M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1=V1∪{x2}={x4,x2}；V2=V2∪{y3}

={y3}§3匈牙利算法例解9（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}N(V1)={y2,y3}§3匈牙利算法例解10（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,}；V2={y3}V1=V1∪{x3}={x4,x2,x3}；V2=V2∪{y2}

={y3,y2}§3匈牙利算法例解11（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}N(V1)={y2,y3,y5}§3匈牙利算法例解12（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3}；V2={y3,y2}V1=V1∪{x5}={x4,x2,x3,x5}；V2=V2∪{y5}

={y3,y2,y5}§3匈牙利算法例解13（4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,x5}；V2={y3,y2,y5}N(V1)={y2,y3,y5,y4}§3匈牙利算法例解14（5）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】解x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}V1={x4,x2,x3,

x5}；V2={y3,y2,y5}x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=ME(P)={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}ŧ3匈牙利算法例解15（2）若X已经饱和，结束；否则转（3）；解x1x2y1x3x4x5y2y3y4y5

这时，M={(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}就是所求的最大匹配。§4最佳匹配

公司里有n名工作人员，他们每个人都能承担n项工作的其中若干项，因为每个人的特长不同，所以对每项工作创造的价值也有所不同。问如何安排，使得他们总的创造价值最大？§4最佳匹配x对每项工作创造的价值的如右边的矩阵所表示：x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5§5最佳匹配算法及例Kuhn和Munkras设计了求最佳匹配的有效算法，他们把求最佳匹配的问题转化成可用匈牙利算法求另一个图的完美匹配的问题。§5最佳匹配算法1

为此，他们对加权的二分图每个顶点v给一个顶标l(v)，当xi∈X，yj∈Y，l(xi)+l(yj)≥cij时，称这样的顶标为可行顶点a标号（feasiblevertexlabelling）。§5最佳匹配算法2初始的时候，令l(xi)=maxci*；l(yi)=0；x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1)=0l(y2)=0l(y3)=0l(y4)=0最佳匹配定理设二分图Kn,n=G是具有正常顶标l的加权图，取G的边子集El={eij|eij∈E(G),l(i)+l(j)=cij}。令Gl是以El为边集的生成子图，如果有Gl完美匹配M，则M即为G的最佳匹配。x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5§5最佳匹配算法3KM算法：（1）选定初始正常标顶l，构作图Gl，在Gl中用匈牙利算法求一个最大匹配；（2）若X饱和则结束，此时所得匹配就是最佳匹配，否则在X中任选一个非饱和点x0，令V1={x0}，V2={}；（3）若NGl(V1)=V2，则取α=min(l(xi)+l(yj)-cij)，其中xi∈V1，yj∈NG(V1)-V2，使得

l(v)-αv∈V1

l(v)=l(v)+αv∈V2

l(v)其他

重新构作图Gl，在NGl(V1)-V2任取一点y，转向（4）；否则在NGl(V1)-V2任取一点y，转向（4）§5最佳匹配算法4（4）若y已饱和，M中必有(y,z)；作【V1=V1∪{z}，V2=V2∪

{y}；转（3）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】§5最佳匹配算法例求下图的最佳匹配例x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5§5最佳匹配算法例解1（1）选定初始正常标顶l，构作图Gl，在Gl中用匈牙利算法求一个最大匹配；解x1x2y1x3x4x5y2y3y4y53554122022244100110012133

C=x1x2x3x4x5y1y2y3y4y5l(x1)=5l(x2)=2l(x3)=4l(x4)=1l(x5)=3l(y5)=0l(y1