运筹学课件之图与网络分析

第八章图与网络分析第一节基本知识第二节树第三节最短路第四节最大流第五节最小费用流1/244L.Euler在1736年发表了一篇论文，解决了Königsberg，今Калининград跨Преголя河两岸七桥难题。2/2443/244ABCDABCD4/2445/2446/2441857年，Hamilton用下图顶点表示20座名城，要求从任一处出发，每处只可经由一次再回到出发点。七桥问题找一条每边仅经由一次的路。这里要找一条每处仅经由一次的路。他提出了一种解法。如图8-4粗箭线所示。7/244v1

这一时期，还提出了诸如迷宫、博弈、行走路线、四色图之类的游戏，许多有实用意义，形成了图论。

匈牙利数学家O.König

1936年发表第一本图论专著。20世纪中期，电子计算机的发展使图论成为运筹学的重要分支，已广泛应用于管理科学、计算机科学、信息论、控制论、物理、化学、生物学、心理学等各领域。8/2449/244第一节基本知识一、图与网络的基本概念1.图及其分类

自然界和人类社会事物之间的关系，可用图形表示。

例如，用点表示企业，用连线表示企业间业务联系。

又如，用点表示工人与需要完成的工作，点间连线表示各个人胜任的工作。10/24411/244图8-5图8-6图8-7定义1

图是由点集V={vi}及其元素的无序对集E={ek}构成的二元组，记为G=(V,E)，V中元素vi

叫做顶点。E中元素ek叫做边。

当V，E为有限集时，G称有限图，否则，称无限图。本章只讨论有限图。12/244

例1图8-7V={v1，v2，v3，v4，v5}，E={e1，e2，e3，e4，e5，e6}其中

e1=(v1，v1)e2=(v1，v2)e3=(v1，v3)

e4=(v2，v3)e5=(v2，v3)e6=(v3，v4)或e1=(1，1)e2=(1，2)e3=(1，3)13/244

14/244若边两端点相同，则称为环（自回路)。

二点之间的边多于两条时，称为多重边。定义2

不含环和多重边的图称简单图，有多重边者称多重图，以后讨论简单图。

有向图两点之间方向不同的两条边，不是多重边。如图8-8中(a)、(b)均为简单图，(c)、(d)为多重图。15/244

16/244

2.顶点的秩定义5以v为端点的边数叫做点v的秩，记作deg(v)或d(v)。

17/244图8-918/244图8-7秩为奇数的点称奇点；秩为偶数的点称偶点。悬挂点，

d(v4)=1悬挂边d(v1)=4孤立点，d(v5)=0定理1任何图顶点秩数总和等于边数2倍。定理2任何图，奇点必为偶数个。证明

设V1和V2分别为G中奇点与偶点集(V1ＵV2=V)。由定理1知，∑

d(v)+∑

d(v)=∑

d(v)=2mv∈V1

v∈V2v∈V因2m是偶数，而

∑d(v)是若干偶数之和，

v∈V2是偶数，∴

∑

d(v)必为偶数，即|V1|为偶数。v∈V119/244

20/24421/244图8-10图8-11(a)的生成子图(a)的子图4．网络

点或边的数量指标，称为“权”，表示距离、费用、容量等。点或边有“权”的图称为网络(赋权图)。

网络分为无向和有向网络。22/24423/244(a)供应站vs与用户(v1,v2,v3,v4,v5,v6,v7)之间的公路网，边上的权表示各点间距离。(b)从vs到vt的输送管道网络，边的权表示容量，要求从vs到vt可运送的最大流方案。图8-11二、连通图定义8无向图G=(V,E)，若G中某些点与边交替序列可排成(vi0,ei1,vi1,ei2,…,vi,k-1,eik,vik)形式，且eit=(vi,t-1,vit)(t=1,2,…,k)，则称之为连接vi0与vik的一条链，链长为k。

点边序列中，点和边无重复者为初等链。24/24425/244图8-12S={v6,e6,v5,e7,v1,e8,v5,e7,v1,e9,v4,e4,v3}连接v6，v3的链。

S1={v6,e6,v5,e5,v4,e4,v3}为初等链。定义9无向图G中，连结vi0与vik的链，当vi0与vik是同一点时，称为圈。圈中既无重复点也无重复边者为初等圈。

图8-12{v1,e7,v5,e8,v1,e9,v4,e10,v2,e2,v1}为圈。图8-12

26/244

对于有向图可类似于无向图定义链和圈、初等链和圈，此时不考虑边的方向。而当考虑链（圈）上边方向相同时，称为道路(回路)。

图8-13

27/244

图8-13S={v6,e6,v5,e8,v1,e9,v4,e10,v2,e3,v3}链。S1={v6,e6,v5,e7,v1,e9,v4,e4,v3}道路。S2={v1,e2,v2,e11,v4,e5,v5,e8,v1}圈。S3={v1,e2,v2,e10,v4,e5,v5,e7,v1}回路。

28/244对于无向图，道路与链、回路与圈意义相同。定义10图中任意两点间至少有一条链相连，则称之为连通图。任何不连通图都可分为若干个连通子图，每一个称为原图的分图。29/244三、图的矩阵表示

权矩阵、邻接矩阵，关联矩阵、回路矩阵、割集矩阵等。只介绍两种。定义11网络(赋权图)G=(V,E)，(vi,vj)有权wij，构造矩阵A=(aij)，

其中：aij=wij，(vi,vj)∈E

=0

其他A称为网络G的权矩阵。30/244定义12对于G=(V,E)，|V|=n，构造一个矩阵A=(aij)，其中：aij=1，(vi,vj)∈E

=0其他称A为G的邻接矩阵。例3图8-15，当G为无向图时，A为对称矩阵。31/244四、欧拉回路与中国邮路问题

l.欧拉回路与道路定义13连通图G，若有道路，每边仅经过一次，则称之为欧拉道路。若有回路，每边仅经过一次，则称之为欧拉回路。

只有欧拉回路的图称为欧拉图(E图)。哥尼斯堡七桥问题就是找一条欧拉回路。

32/244欧拉道路v2→v4欧拉道路{v2,e1,v1,e5,v4,e3,v3,e2,v2,e6,v5,e4,v4}v3→v4欧拉道路{v3,e3,v4,e2,v2,e1,v1,e4,v4}无欧拉道路v1v4v2v3v5e1e2e3e4e5e6v1v4v2v3e1e2e4e2v1v2e1v3v4e4v5e5v6e6e7v7v8e8回路和初等回路初等回路{v1,e1,v2,e3,v4,e2,v1}{v1,e1,v2,e3,v5,e6,v3,e4,v4,e5,v5,e2,v1}是回路，但v5重复，不是初等回路。v1v2v4e1e4e2e3v3v1v2v4e1e4e2e3v3v5e5e6欧拉回路欧拉回路{v1,e1,v2,e2,v3,e3,v4,e7,

v2,e5,v5,e4,v4,e6,v1}所有顶点均为偶点。v1v4v2v3v5e1e2e4e6e5e7e3Everyvertexofthisgraphhasanevendegree,thereforethisisanEuleriangraph.FollowingtheedgesinalphabeticalordergivesanEuleriancircuit/cycle.v1,v4,是奇点，无欧拉回路。v1v4v2e3e5e2e1v3e4定理3无向连通图G是欧拉图，当且仅当G

中无奇点。证明

必要性

因G是欧拉图，则有回路，经由G中所有边，回路上顶点可能重复出现，但边不重复。对于任一顶点vi，只要在回路出现一次，必关联两条边，即这条回路沿一条边进入这点，再沿另一边离开这点。所以vi虽然可在回路中重复出现，但deg(vi)必为偶数。所以G中没有奇点。37/244充分性

由于G无奇点，从任一点，如v1出发，经关联边e1“进入”v2，因v2是偶点，则必可由v2经关联边e2到v3，如此下去，每边仅经过一次。由于V有限，所以该路必有尽头，必可走回v1，完成了一条回路c1。(1)若c1经过G所有边，则c1就是欧拉回路。(2)从G中去掉c1后得到子图G’，则G’中每个顶点的秩仍为偶数。因G连通，所以c1与G’总有顶点vi相连，在G’中从vi出发，如同c1，完成回路c2。38/244组合c1与c2，若恰是G，则得到欧拉回路。否则重复(2)可得回路c3，依此类推，由于E有限，最终可得到遍历E的回路，即为欧拉回路。39/24440/244v1v2v3v4v5v6v7v8G41/244v1v6v7v8v1v2v3v4v5v5G’c1v2v3v442/244v1v6v7v8v1v2v3v4v5v5G’’c1v6v8c2(c3)v143/244v1v2v3v4v5v6v7v8+c2+c3c1推论1无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。推论2无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。44/244根据定理检查七桥问题，从图8-2中可看到deg(A)=3，deg(B)=3，deg(C)=5，deg(D)=3。有四个奇点，不是欧拉图，该问题无解。

一笔画问题可类似求解。一个图形可否一笔画出，一种是每边仅经过一次到另一点停止。另一种是每边仅经过一次回到原点。

这两种情况可分别用关于欧拉道路和欧拉回路的判定条件解决。45/244ABCD定理3的证明实际上是构造欧拉回路的算法，

从任一v1出发，找一个初等回路c1，并去掉c1，在剩余图中再找初等回路c2，…，一直到图中所有边都成为初等回路，再将其连接起来即得该图的欧拉回路。

无向图的定理3，可直接推广到有向图。定理4连通有向图G是欧拉图，当且仅当它每个顶点的出秩等于入秩。

连通有向图G有欧拉道路，当且仅当图中除两个顶点外，其余每一顶点的出秩等于入秩，且该二顶点中，一个入秩比出秩多1，另一个入秩比出秩少1。46/24447/244连通有向图G是欧拉图欧拉道路v2→v4欧拉道路{v2,e1,v1,e6,v4,e4,v5,e5,v2,e2,v3,e3,v4}v1v4v2v3v5e1e2e4e5e6e3d

+(v2)=2d

-(v2)=1d

+(v4)=1d

-(v2)=2d

+(vi)=d

-(vi)2．中国邮路问题

邮差每天从邮局出发，走遍邮区所有街道再返回，问应如何走总路程才最短?

从图论看：连通图G各边有非负权l(e)，求一条每边至少过一次的回路，且使总权最小。

由定理3知，G若无奇点，则是欧拉图，走欧拉回路就可每边至少过一次且总权最小。49/244G若有奇点，要求连续每边至少走一次，必然有些边不止过一次，相当于G某些边添加重复边，使新图G*无奇点且使总路程最短。

由于路程总长完全取决于新添重复边的长度，所以该问题也可化为如下问题：

在连通图G=(V,E)中，求一个边集E1∈E，将E1中边均改成二重边，得到G*=G+E1，使G*无奇点且L(E1)=∑

l(e)最小。

e∈E1

50/244定理5已知G*=G+E1无奇点，则L(E1)=∑l(e)最小的充分必要条件是：

e∈E1(1)每条边最多重复一次；(2)G中各初等圈内重复边总长不超过圈长一半。51/24452/244v1v2v3v4v5v6v7v85134117279141812610158例1编号初等回路圈长c11-2-4-130c21-2-3-4-131c31-2-3-4-6-8-155c41-2-3-4-6-7-8-175c51-2-3-4-5-6-7-8-199c61-2-4-6-8-154c71-2-4-6-7-8-174c81-2-4-5-6-7-8-198c91-2-6-8-139c101-2-6-7-8-159c111-4-6-8-146c121-4-6-7-8-166c131-4-5-6-8-169c141-4-5-6-7-8-181c151-4-3-6-8-147从v1出发的初等回路53/244v1v2v3v4v5v6v7v85134117279141812610158例154/244v1v2v3v4v5v6v7v85134117279141812610158例1E1={(1,8),(3,4)},L(E1)=∑

l(e)=18+8=26c11={(1,8),(8,6),(6,4),(4,1)},L(c11)=18+4+13+11=46,L(E1)<L(c1)/2c3={(1,8),(8,6),(6,4),(4,3),(3,2),(2,1)},L(c2)=18+4+13+8+7+5=55,L(E1)<L(c1)/2c15={(1,4),(4,3),(3,6),(6,8),(8,1)},L(c15)=11+8+6+4+18=47,L(E1)>L(c15)/2圈长重边？满足(2)？c130无c231有Yesc355有Yesc475有Yesc599有Yesc654有Yesc774有Yesc898有Yesc939有Yesc1059有Yesc1146有Yesc1266有Yesc1369有Yesc1481有Yesc1547有Noc11-2-4-130c21-2-3-4-131c31-2-3-4-6-8-155c41-2-3-4-6-7-8-175c51-2-3-4-5-6-7-8-199c61-2-4-6-8-154c71-2-4-6-7-8-174c151-4-3-6-8-14755/244v1v2v3v4v5v6v7v85134117279141812610158例1c3={(1,8),(8,6),(6,4),(4,3),(3,2),(2,1)},L(c3)=18+4+13+8+7+5=55,L(E1)<L(c3)/2c11={(1,8),(8,6),(6,4),(4,1)},L(c11)=18+4+13+11=46,L(E1)<L(c11)/2圈长有重边？满足（2）？c130有Yesc231有Yesc355有Yesc475无c599无c654有Yesc774无c898无c939有Yesc1059无c1146有Yesc1266无c1369有Yesc1481无c1547有YesL(E1)=∑

l(e)=4+6+11=2156/244v1v2v3v4v5v6v7v8243569v944434例25初等回路圈长c11-2-5-4-124c21-2-5-8-7-4-132c31-2-3-6-5-4-128c41-2-3-6-5-8-7-4-136c51-2-3-6-9-8-7-4-136c61-2-5-6-9-8-7-4-138c72-3-6-5-216c82-3-6-9-8-5-224c95-6-9-8-514c105-8-7-4-516c112-5-4-7-8-9-6-3-23257/244v1v2v3v4v5v6v7v8243569v944434例25E1={(2,3),(3,6),(4,5),(5,8)},L(E1)=∑

l(e)=2+5+4+4=15初等圈c7={(2,3),(3,6),(6,5),(5,2)},L(c7)/2=(5+2+3+6=16)/2>5+2=7c8={(2,3),(3,6),(6,9),(9,8),(8,5),(5,2)},L(c8)/2=(5+2+4+3+4+6=24)/2>5+2+4=11c5={(2,3),(3,6),(6,9),(9,8),(8,5),(5,4),(4,1),(1,2)},L(c5)/2=(5+2+4+3+4+4+9+5=36)/2>5+2+4+4=15c7={(4,5),(5,8),(8,7),(7,4)},L(c7)/2=(4+4+4+4=16)/2=4+4=8等等。c11-2-5-4-124c51-2-3-6-9-8-7-4-136c72-3-6-5-21658/244v1v2v3v4v5v6v7v8243569v944434例25E1={(2,5),(5,4),(6,9),(9,8)},L(E1)=∑

l(e)=6+4+4+3=17初等圈c1={(2,5),(5,4),(4,1),(1,2)},L(c1)/2=(6+4+9+5=24)/2>6+4=10c2={(2,5),(5,8),(8,7),(7,4),(4,1),(1,2)},L(c2)/2=(6+4+4+4+9+5=32)/2>6c8={(3,6),(6,9),(9,8),(8,5),(5,2),(2,3)},L(c8)/2=(2+4+3+4+6+5=24)/2<4+3+6=13c11={(2,5),(5,4),(4,7),(7,8),(8,9),(9,6),(6,3),(3,2)},L(c11)/2=(6+4+4+4+3+4+2+5=32)/2<17c82-3-6-9-8-5-224c112-5-4-7-8-9-6-3-232证明

必要性

假如G*中某边重复n(n>2)次，而G*是欧拉图，那么把该边重复边去掉两(偶数)条，则与此边关联的两顶点的秩都减2(偶数)，仍为偶点，故仍为欧拉图，所以边最多重复一次即可。使图上初等圈上原重复的边（重复一次)不再重复，而原不重复的边重复一次，则圈上每个顶点的秩改变0或2，也不改变欧拉图性质。因此，若G中存在某圈，其重复边长度超过圈长的一半，就可减少重复边长度，这与L(E1)最小矛盾。59/244充分性

只需证明凡满足定理中条件(1)、（2）的重复边集，其总长度均相等即可。

设E1，E2都满足定理中条件(1)、（2），下面证L(E1)=L(E2)。

作E0=(E1ＵE2)-(E1∩E2)，则E0中边在E1或E2中必居且仅居其一。60/24461/244v1v2v3v4v5v6v7v85134117279141812610158E1={(1,8),(3,4)},L(E1)=∑

l(e)=18+8=26c1={(1,8),(8,6),(6,4),(4,1)},L(c1)=18+4+13+11=46,L(E1)<L(c1)/2c2={(1,8),(8,6),(6,4),(4,3),(3,2),(2,1)},L(c2)=18+4+13+8+7+5=55,L(E1)<L(c1)/2c3={(3,4),(4,1),(1,8),(8,6),(6,3)},L(c3)=8+11+18+4+6=47,L(E1)>L(c3)/262/244v1v2v3v4v5v6v7v85134117279141812610158L(E1)=∑

l(e)=4+6+11=21c1={(1,8),(8,6),(6,4),(4,1)},L(c1)=18+4+13+11=46,L(E1)<L(c1)/2c2={(1,8),(8,6),(6,4),(4,3),(3,2),(2,1)},L(c2)=18+4+13+8+7+5=55,L(E1)<L(c1)/263/244v1v3v4v6v84111868v1v3v4v8E1E264/244v1v3v4v6v84111868

G0=(V，E0)

观察由E0中边和与之相关联的点组成的图G0，G0可能不连通，但其每个分图必为欧拉图(因为G的每个顶点v与E1中相关联的重复边的数目与v与E2相关联的边数的奇偶性相同，都取决于v原来秩数的奇偶，重复边数也必为奇或偶，所以G0的点必为偶点)，所以每个分图可分为若干个初等圈。根据定理条件，对每个初等圈上均有E1的重复边长不超过周长的一半和E2的重复边长不超过周长的一半，故只能相等。则在E0中属于E1的边总长等于属于E2的边总长，于是有L(E1)=L(E2)。65/24466/244v1v3v5v7243569v9445434图8-16v2v4v6v8定理给出了中国邮路问题的算法，称为“奇偶点图上作业法”。以图8-16所示网络的中国邮路问题为例说明。例4奇偶点图上作业法第l步：确定初始可行方案

先检查图中有无奇点，若无，则已是欧拉图，找出欧拉回路即可。若有，由前知必为偶数个奇点，故可两两配对。每对点间选一条路，使路上均为二重边。

67/244奇偶点图上作业法管梅谷（1934－）上海市人。1957年毕业于华东师范大学数学系。历任山东师范大学讲师、副教授、教授、校长，中国运筹学会第一、二届常务理事。从事运筹学及其应用的研究，1960年研究最短投递路线问题取得成果，国外称之为中国投递问题。自1957年至1990年在山东师范大学工作，1990年至1995年任复旦大学运筹学系主任。

68/24469/244v1v3v5v7243569v9445434图8-16v2v4v6v8该图有10几个初等圈（回路）。70/244v1v2v3v4v5v6v7v8243569v9445434图8-16v2v4v6v8图8-16中有四个奇点v2，v4，v6，v8，将v2与v4，v6与v8配对。71/244v1v2v3v4v5v6v7v8243569v9445434图8-17v2与v4有多条路连接，任取一条{v2，v3，v6，v9，v8，v7，v4}，对v6与v8取{v6，v3，v2，v1，v4，v7，v8}。得到图8-17的欧拉图。重复边总长为：

2l23+2l36+l69+l98+2l87+2l74+l41+l12=5172/244v1v2v3v4v5v6v7v8243569v9445434第2步：调整方案，使重复边最多为一次。去掉(v2，v3)，(v3，v6)，(v4，v7)，(v7，v8)各两条。图8-1873/244v1v2v3v4v5v6v7v8243569v9445434图8-18重复边总长度下降为：

l

12+l14+l69+l98=2174/244v1v2v3v4v5v6v7v8243569v9445434图8-18第3步：检查图中各初等圈是否满足定理条件(2)。

检查图8-18，发现圈c1={v1,v2,v5,v4,v1}总长24，而重复边长14，大于该圈总长一半，可调整。75/244编号初等回路圈长有重边？重边长满足(2)？c11-2-5-4-124有14Noc21-2-5-8-7-4-132有14Yesc31-2-3-6-5-4-128有14Yesc41-2-3-6-5-8-7-4-136有14Yesc51-2-3-6-9-8-7-4-136有21Noc61-2-5-6-9-8-7-4-138有21Noc72-3-6-5-216c82-3-6-9-8-5-224有7Yesc95-6-9-8-514有7Yesc105-8-7-4-516c112-5-4-7-8-9-6-3-232有7Yes76/244v1v2v3v4v5v6v7v8243569v9445434图8-19以(v2，v5)，(v5，v4)代替(v1，v2)，(v1，v4)，得到图8-19，重复边总长度下降为：

l

25+l45+l69+l98=1777/244v1v2v3v4v5v6v7v8243569v9445434图8-19再检查图8-19，圈{v2，v3，v6，v9，v8，v5，v2}总长24，而重复边长为13，再次调整。得图8-20，重复边总长度为15。78/244编号初等回路圈长有重边？重边长满足(2)？c11-2-5-4-124有10Yesc21-2-5-8-7-4-132有6Yesc31-2-3-6-5-4-128c41-2-3-6-5-8-7-4-136有14Yesc51-2-3-6-9-8-7-4-136有7Yesc61-2-5-6-9-8-7-4-138有13Yesc72-3-6-5-216有6Yesc82-3-6-9-8-5-224有13Noc95-6-9-8-514有7Yesc105-8-7-4-516有4Yesc112-5-4-7-8-9-6-3-232有17No79/244v1v2v3v4v5v6v7v8243569v9445434图8-20图8-20，重复边总长度为15。80/244编号初等回路圈长有重边？重边长满足(2)？c11-2-5-4-124有4Yesc21-2-5-8-7-4-132有4Yesc31-2-3-6-5-4-128有11Yesc41-2-3-6-5-8-7-4-136有11Yesc51-2-3-6-9-8-7-4-136有7Yesc61-2-5-6-9-8-7-4-138-c72-3-6-5-216有7Yesc82-3-6-9-8-5-224有11Yesc95-6-9-8-514有4Yesc105-8-7-4-516有8Yesc112-5-4-7-8-9-6-3-232有11Yes

检查图8-20，条件（1）、（2）均满足，得到最优方案。图中任一欧拉回路即为最优邮递路线。

这种方法虽然比较容易，但要检查每个初等圈，当G的点数或边数较多时，运算量极大。Edmods和Johnson于1973年提出了将其化为最短路及最优匹配问题求解的简便算法。81/24482/244JackR.Edmonds(April5,1934–)isaCanadianmathematicianandcomputerscientist,regardedasoneofthemostimportantcontributorstothefieldofcombinatorialoptimization.Hewastherecipientofthe1985JohnvonNeumannTheoryPrize.HegraduatedfromGeorgeWashingtonUniversityin1958andobtainedaMaster'sdegreefromtheUniversityofMarylandin1959.From1969on,heheldafacultypositionattheDepartmentofCombinatoricsandOptimizationattheUniversityofWaterloo'sFacultyofMathematics.Heretiredin1999.83/244UniversityofWaterloo84/244In1984,hereceivedtheGeorgeDantzigAwardforhisresearchinmathematicalprogramming.In1986,hewasawardedtheLanchesterPrizeforhispaperwithCrowderandPadberg.In1988,hewaselectedtotheNationalAcademyofEngineering.In2000,Dr.JohnsonwontheINFORMSJohnVonNeumannTheoryPrize.From1990to1995,hebeganteachingandconductingresearchatGeorgiaTech.EllisJohnson(1937-)aProfessorEmeritusinStewartSchoolofIndustrial&SystemsEngineering.HereceivedaB.A.inmathematicsatGeorgiaTechandaPh.D.inoperationsresearchattheUniversityofCalifornia.BeforejoiningGeorgiaTechin1995,hewasatIBM'sT.J.WatsonResearchCenterfor26years.85/24486/244v1v3v6v934462587/244v1v2v3v4v5v6v7v8513411727914181261015888/244v1v2v3v4v5v6v7v817111218108v1v3v4v81711121810889/244v1v2v3v4v5v6v7v85134117279141812610158L(E1)=∑

l(e)=4+6+11=2190/244v1v2v3v4v5v6v7v85134117279141812610158L(E1)=∑

l(e)=18+8=2691/244v1v2v3v4v5v6v7v8243569v9445434v2v4v6v81078771092/244v1v2v3v4v5v6v7v8243569v9445434v2v4v6v810787710第二节树一、树的基本性质

树是结构最简单但又十分重要的图，在许多领域都有广泛的应用。例5乒乓球单打比赛相遇情况，可用图8-21表示。93/24494/244图8-21图8-22定义14连通且不含圈的无向图称为树。树中秩为1的点称为树叶，大于1者称为分枝点。

树的性质归纳为下面的定理。定理6图T=(V，E)，|V|=n，|E|=m，下列说法等价。(1)T是一个树。(2)T无圈，且m=n-1。(3)T连通，且m=n-1。(4)T无圈，但每加一新边即得惟一个圈。(5)T连通，但任舍去一边就不连通。(6)T中任意两点有惟一链相连。95/244证明(1)→(2)

既然T是树，由定义知T连通，且无圈。只需证明T的边数m等于顶点数减1。

用归纳法。

当n=2时，由于T是树，两点间有且仅有一条边，满足m=n-1。假设n=k-1时命题成立，即有k-1个顶点时T有k-2条边。当n=k时，因T连通无圈，k个顶点中至少有一个点秩为1。设此点为u，u为悬挂点，设连结u

的悬挂边为(v，u)。从T中去掉(v，u)及u后仍连通，得图T’，T’为树只有k-1个顶点，故有k-2条边，再把(v，u)，u加上去，可知当T有k个顶点时有k-l条边。96/244(2)→(3)

只需证明T是连通图。

反证法。设T不连通，可分为l个连通分图(l≥2)，设第i个分图有ni个顶点，∑ni=n。因第i个分图是树，所以有ni-1条边，l个分图共有边数为∑(ni-1)=n-l<n-1，与已知矛盾，所以，T是连通图。97/244(3)→(4)

若T有圈，设为C。可去掉C一条边，T仍连通。若剩余图中仍有圈，可继续拿去一条边……，如此去掉p条边(p≥1)后得到一个无圈连通图T’，T’显然有n-1-p条边。但T’既然是树，顶点个数又与T同为n个，所以T

’应有n-1条边。矛盾，即T中无圈。

设T中u，v两点间无边直接相连，T连通，所以经由其他点必有一条链连结u，v，且是连结这两点的惟一链(否则T中出现圈)，则T+(u，v)后，出现惟一的圈。98/244(4)→(5)

先证T连通。若T不连通，由定义至少存在u，v之间无路，加上(u,v)也不会形成圈，与已知矛盾。

再证舍去一边便不连通。若舍去一边(u,v)后仍然连通，那么，由于T’=T-(u,v)无圈，是树，但T’加一边(u,v)后是T，仍无圈，与(4)中树每加一新边必出现惟一圈相矛盾。(5)→(6)，(6)→(1)均显然，故定理证毕。99/244定理6中每一命题均可作为树的定义，判断和构造树时极为方便。二、图的生成树定义15若图G的生成子图是棵树，则称该树为G的生成树(支撑树）或简称为图G的树。

图G中属于生成树的边称为树枝，不在生成树中的边称为弦。

图8-23(b)为(a)的生成树，边e1,e2,e3,e7,e8,e9为树枝，e4,e5,e6为弦。100/244101/244图8-23定理7图G=(V，E)有生成树的充分必要条件为G是连通图。(证明略)

定理7的证明告诉了找图生成树的方法，即，在图G中，每选一边，该边与已选边都不成圈，直到选出n-1条边为止。该法可称“避圈法”或“加边法”。

按照边的选法不同，找图中生成树的方法可分为两种。102/244(1)深探法标号法步骤：①在V中任取一点v，标上0。②若某点u已标i，检查以u为端点的各边，另一端点是否均已标号。

若(u,w)之w未标号，则为w

标上i+1，记下边(u,w)。令w代u，重复②。

若这种边另一端点均已标号，就退到标号为i-1的r点，以r代u，重复②。直到全部点均标号为止。

图8-24为标号过程，粗线为生成树。103/244104/244图8-24(2)广探法步骤如下：①从V任取v，给v标上0。②所有标号为i的点记为Vi，检查[Vi、V\Vi]中边端点是否均已标号。对所有未标号之点均标以i+1，记下这些边。③对标号i+1的点重复步骤②，直到所有点标上号为止。如图8-25(a)中粗线边就是用广探法生成的树，也可表示为图8-25(b)。显然，生成树不唯一。求生成树还有破圈法。105/244106/244图8-25三、最小生成树问题定义16连通图G=(V，E)各边有非负权L(e)。生成树所有枝权的总和，称为该生成树的权。权最小的生成树称为最小生成树(最小支撑树)简称最小树。下面介绍最小树两种算法。算法1(Kruskal算法)

此法类似于求生成树的“避圈法”，每步从未选的边中选e，使其与已选边不构成圈，且e是未选中的最小权边，直到选够n-1条边为止。107/244KruskalwasastudentattheUniversityofChicagoandPrincetonUniversity,wherehecompletedhisPh.D.in1954.Incomputerscience,hisbestknownworkisKruskal'salgorithmforcomputingtheminimalspanningtree(MST)ofaweightedgraph.108/244JosephBernardKruskal,Jr.wasborninNewYorkCityonJanuary29,1928anddiedonSeptember19,2010.HewasanAmericanmathematician,statistician,computerscientistandpsychometrician.例7某乡9个自然村间道路及路长如图8-26(a)所示。问如何拉线才用得最少。

图8-26109/244最小生成树问题，用Kruskal算法。先将(a)中边按权由小至大排列：(0,2)=1，(2,3)=1，(3,4)=1，(1,8)=1，(0,1)=2，(0,6)=2，(5,6)=2，(0,3)=3，(6,7)=3，(0,4)=4，(0,5)=4，(0,8)=4，(1,2)=4，(0,7)=5，(7,8)=5，(4,5)=5110/244然后按照边的排列顺序，取定(0,2)=e1，(2,3)=e2，(3,4)=e3，(1,8)=e4，(0,1)=e5，(0,6)=e6，(5,6)=e7由于下一个未选边中权最小的(0,3)与已选边e1，e2构成圈，所以排除。选e8=(6,7)。(b)就是图G的一棵最小树，权是13。111/244v4v1v8e5v3e3e2e1v0v2e4e6v6v5e7v7e8定理8用Kruskal算法得到的子图T*=(e1,e2,…,en-1)是一棵最小树。(证明略)

算法2(破圈法)

基本步骤：(1)从图G中任选一棵树T1。(2)加上一条弦e1，T1+e1中立即生成一个圈。去掉此圈中最小权边，得到新树T2。以T2代T1，重复(2)再检查剩余的弦，直到检查完全部弦为止。112/244仍用例7，先求出图G的一棵生成树如图8-27的(a)，加以弦(1,2)，得圈{1,2,0,1}，去掉最大权边(1,2)；再加上弦(2,3)，得圈{2,3,0,2}，去掉最大权边(0,3)，…，直到全部弦均已试过，图8-27(b)即为所求。

算法2的根据为下述定理。定理9图G的生成树T为最小树，当且仪当对任一弦e来说，e是T+e中与之对应的圈μe中的最大权边。（证明略)113/244114/244v3v4v5v7v8132445v2v1v0v614113224图8-27四、根树及其应用定义17若有向图不考虑边的方向时是棵树，则称之为有向树。定义18有向树T恰有一个结点入秩为0，其余各点入秩均为1，则称T为根树(又称外向树)．

根树入秩为0的点称为根。根树中出秩为0的点称为叶，其他顶点称为分枝点。由根到某一顶点vi的道路长度(设每边长度为1)，称为vi点的层次。115/244定义19根树中，若每个顶点出秩小于或等于m，称这棵树为m叉树。若每个顶点出秩恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。116/244117/244图8-28图8-29v1为根，v2，v3，v4，v8为分枝点，其余各点为叶，顶点v2，v3，v4的层次为l，顶点v11的层次为3等。v1完全三叉树四叉树令二叉树T的s片叶子的权分别为pi，根到各叶子的距离(层次)为li，(i=1，…,s)，二叉树T的总权数

m(T)=∑pili满足总权最小的二叉树称为最优二叉树。霍夫曼(DAHuffman)提出了二叉树的算法，所以又称霍夫曼树。算法步骤为，(1)将s

片叶子按权由小至大排列，可设p1≤p2≤…≤ps。(2)将权最小两片叶子合成一个分支点，权为p1+p2，将新的分支点作为一片叶子。令s←s-1，若s=1停止，否则转(1)。118/244DavidAlbertHuffman(August9,1925–October7,1999)wasapioneerincomputerscience,knownforhisHuffmancoding.Hewasalsooneofthepioneersinthefieldofmathematicalorigami.DavidHuffmandiedattheageof74tenmonthsafterbeingdiagnosedwithcancer.119/244例8s=6，其权分别为4，3，3，2，2，1，求最优二叉树。解

该树构造过程见图8-30。120/244121/244图8-30131225223343364915总权为

1×4+2×4+2×3+3×2+3×2+4×2=38可证该树为最优二叉树，直观意义：叶子的距离依权递减而增加，所以总权最小。第三节

最短路问题

是网络理论讨论最多的问题之一。许多优化问题可用这一模型，如设备更新、管道铺设、线路安排、厂区布局等。

有些最短路问题，动态规划难以处理，而图论方法较有效。122/244

最短路问题：设G=(V，E)为连通图，(vi,vj)有权lij(lij=∞表示vi，vj间无边)，求一条从vs到vt的总权最小的路μ，即：

L(μ)=min∑lij。(vi,vj)∈μ相当于LP问题：

Minf(x)=∑∑

lijxij(vi,vj)∈Es.t.∑xij-

∑xki

=1,i=1

(vi,vj)∈E(vk,vi)∈E=0,1<i<m

xij=0或1=-1,i=m

123/244本节介绍三种算法，分别处理几种情况。一、Dijstra算法

Dijkstra于1959年提出，可用于求解从指定点vs到其余各点的最短路，是目前求无负权网络最短路问题的最好方法。

思路：若序列{vs,v1,v2,…,vn}是从vs到vn的最短路，则序列{

vs,v1,v2,…,vn-1}必为从vs到vn-1的最短路。

124/244125/244EdsgerWybeDijkstra(11May1930–6August2002)wasaDutchcomputerscientist.Hereceivedthe1972TuringAwardforfundamentalcontributionstodevelopingprogramminglanguages,andwastheSchlumbergerCentennialChairofComputerSciencesatTheUniversityofTexasatAustinfrom1984until2000.

标号法基本步骤。

用两种标号：T标号与P标号，T标号是为试探，P为永久性标号，vi的P标号表示从vs到vi的最短路权，以后不再改。

vi的T标号表示从vs到vi的最短路权上界，凡未得到P标号的点都加T标号。

每一步都把某点的T标号改为P标号，当终点vt得到P标号时，计算结束。

有n个顶点的图，最多经n-1步就可求得从始点到终点的最短路。126/244步骤：(1)给vs以P标号，P(vs)=0，其余各点均给T标号，T(vi)=+∞。(2)若vi刚得到P标号，考虑vj：(vi,vj)∈E，且为T标号，如下修改vj的T标号：T(vj)=min[T(vj),P(vi)+lij](3)比较所有T标号点，把最小者改为P标号，即：P(v*i)=min[T(vi)]有多个最小者时，可同时改为P标号。若全部点均为P标号，则停止。否则，用v*i

代vi，转回（2）。127/244例9用Dijkstra算法求图8-31中v1到v8最短路。图8-31128/244129/244P(v1)=0T(v2)=

∞T(v3)=∞T(v4)=∞T(v5)=∞T(v6)=∞T(v7)=∞T(v8)=∞130/244P(v1)=0T(v2)=

4T(v3)=

6T(v4)=∞T(v5)=∞T(v6)=∞T(v7)=∞T(v8)=∞T(v2)=min[T(v2)，P(v1)+l12]=min[+∞，0+4]=4T(v3)=min[T(v3)，P(v1)+l13]=min[+∞，0+6]=6T(v2)=∞T(v3)=∞131/244P(v1)=0T(v2)=

4T(v3)=6T(v4)=∞T(v5)=∞T(v6)=∞T(v7)=∞T(v8)=∞T(v2)=min[T(v2),T(v3),T(v4),…,T(v8)]=4P(v2)=4132/244P(v1)=0T(v3)=6T(v4)=∞T(v5)=∞T(v6)=∞T(v7)=∞T(v8)=∞P(v2)=4T(v4)=min[T(v4)，P(v2)+l24]=min[+∞，4+5]=9T(v5)=min[T(v5)，P(v2)+l25]=min[+∞，4+4]=8T(v4)=9T(v5)=8133/244P(v1)=0T(v3)=

6T(v6)=∞T(v7)=∞T(v8)=∞P(v