第6章 图与网络分析

第6章 图与网络分析 §6.1 图的基本概念

§6.2 树图和图的最小部分树 §6.3 最短路问题

§6.4 网络的最大流 §6.5 最小费用流

第1页

引 言图论是运筹学的一个经典和重要的分支，它起源于欧拉 (Euler)对七桥问题的抽象和论证。 1936年，匈牙利数学家柯尼希(Kö nig)出版了图论的 第一部专著《有限图与无限图理论》,竖立了图论发展的第 一座里程碑。 此后，图论进入发展与突破的快车道，所研究的问题涉 及经济管理、工业工程、交通运输、计算机科学与信息技术、 通讯与网络技术等诸多领域。近几十年来，由于计算机技术 和科学的飞速发展，大大地促进了图论研究和应用，图论的 理论和方法已经渗透到物理、化学、通讯科学、建筑学、生 物遗传学、心理学、经济学、社会学等学科中。

图论研究点与边的连接关系、一笔画问题、通路、最短 路、最大流量。而诸如“四色问题”,“旅行商问题”等世 界著名的难题都属于图论的研究范畴。第2页

§6.1 图的基本概念运筹学中研究的图是生活中各类图的抽象概括, 它表明一些研究对象和这些对象之间的相互关系。 用点表示研究对象，用边表示这些对象之间的联 系，则G图可定义为点和边的集合，记为

G {V , E }式中V是点的集合，E是边的集合。

第3页

基本概念网络图N:若给图中的点和边赋以具体的含义和权。 顶点(节点):记为v 边:记为e e1=[v1,v1] e2=[v1,v2] 或 e2=[v2,v1] 端点,关联边,相邻：若边e=[vi,vj],称vi和vj是边e的端点; 边e为点vi或vj的关联边；

若点vi、vj与同一条边关联，称点vi和vj 相邻；e1 e2 v2 v1 e5

若边ei和ej具有共同的端点，称边ei和ej相邻；e3 v3 e4

环,多重边,简单图： 若边e的两个端点相重，称该边为环;v4

e6

若两顶点之间至少有两条边，称为具有多重边;

无环、无多重边的图称作简单图。

第4页

次,奇点,偶点，孤立点 与点v相关联的边的数目称为点v的次(度或线度),记作d(v)

次为奇(偶)数的点称作奇(偶)点； 次为0的点称作孤立点； 链,圈,路，回路，连通图 点和边的交错序列μ={v0, e1, v1,…,ek ,vk}, 若其中各边e1, e2,…,ek互不相同, 且任意vt-1和vt (2≤t≤k)均相邻, 称μ为链.若链中所有的顶点也互不相同,这样的链称为路.e1 e2 v2 v1 e5 e6 v5

e3

v3 e4v4

起点和终点重合的链称为圈. 起点和终点重合的路称为回路. 若图中的每一对顶点之间至少存在一条链, 称这 样的图为连通图, 否则称该图是不连通的.

第5页

完全图，偶图

任意两点之间均有边相连的简单图, 称为完全图.

Kn2 | E | Cn

K2

K3

K4

若图的顶点能分成两个互不相交的非空集合V1和 V2,使在同一集合中任意两个顶点均不

相邻称, 这样的 图为偶图(二分图). 若偶图的顶点集合V1和V2之间的每对不同顶点都 有边相连，称 这样的图为完全偶图. Km,n

K3, 2

m n

第6页

子图，部分图

设G=(V,E)是一个图, 并设V V 和E E , 如果对E 中任意的一条边eij [vi , v j ], 都有 vi V , v j V , 则称G [V , E ] 是G的一个子图. 若V V , E E , 则称 G 是G的一个部分图.

注意： 部分图是子图，但子图不一定是部分图.e1 e2 v2 v1 e5 e3 v3 e4

e2v4 v2

v1

v3

e5

e2 v2

v1 e6

v3 e4 v4 e2 v2 v1 e5

e6

子图

部分图

非子图第7页

树图(简称树): 无圈的连通图，记作T(V, E) G的部分树(或支撑树): 若G1是G的部分图又是树图. 树枝: 树图的各条边. 假定图的各边均有权重. 最小部分树(或最小支撑树，minimum spanning tree): 图中树枝总长最小的部分树.

第8页

§6.2.1树图的性质

悬挂点

悬挂边

性质1 任何树图中必存在次为1的点. 证明：用反证法. 假设树图中不存在次为1的点.又连通图中不存在孤立点，故树图中所有顶点的次≥2. 不妨设d(v1)=2, 既v1有两条关联边， 设关联边的其他两个端点为v2 , v3,而d(v2 )≥2, d(v3) ≥2, 又可知与v2 , v3关联的边的其他端点v4 , v5,同样d(v4 )≥2, d(v5) ≥2,可继续一直往下推。 而图的顶点的总数是有限的，故最后 必然回到前面的某一顶点，于是在图中出 现了圈，这与树的定义产生了矛盾.v2 v4

v5v1 v3

第9页

性质2 具有n个顶点的树图的边树恰好为n-1条. 证明：用归纳法.当n=2和n=3时, 上述性质显然成立. 假设当n=k-1时, 上述性质也成立. 当n=k时, 因树中至少有一个悬挂点，将此悬挂点及 关联的悬挂边从树图中拿掉. 根据前述，剩下的图仍为树图，故此时图中有k-1个 点，据假定应有k-2条边. 再把拿掉的悬挂点及悬挂边放回去，说明树图中含 有k个点时，边数为k-1条.

第10页

性质3 任何具有n个顶点、n-1条边的连通图是树图. 证明： 用反证法. 假设有n个顶点、n-1条边的连通图不是树图.此时这个图中含有圈， 则从圈中拿掉任意一条边, 图仍连通. 若仍有圈， 则继续从圈中拿掉任意一条边, 这样继续下去. 一直到图中没有任何圈为止. 由于剩下的图仍连通且无圈，故仍为树. 但此时图中有n个顶点, 而边数却少于n-1条, 与性质2矛盾.

说明：(1) 树是无圈连通图中边数最多的, 在树图中只要任意再加上一条边，必会出现圈.(2) 树图的任意两点之间有一条且仅有一条唯一通路.

第11页

§6.2.2 图的最小部分树定理1 图中任一个点i, 若j 是i 与相邻点中距离最近的, 则边[i, j]一定含在该图的最小部分树内. 证明：用反证法. 设T为已知图的最小部分树, i 假设边[i, j]不在T内, 将这条

边加上, 图中必出现圈. 假定图中i点的原关联边为[i, k], 则[i, k]> [i, j] 在T中加上边[i, j], 再拿走边[i, k], 该图仍为树图, k 但树枝总长减少了，与T是最小部分树矛盾.j

Ti m j

推论： 把图的所有顶点分成V和 V 两个集合,则两集合之间连线的最短边一定包含在该 图的最小部分树内.k

VV第12页

T

§6.2.3 避圈法和破圈法1. 避圈法寻找最小部分树的步骤： (1) 任选一点 v i , 让vi V , 其余点均包含在V 中； (2) 从V与V 的连线中找出最小边，不妨设最小边为[vi, vj], 将边[vi, vj]加粗(表示最小部分树内的边). (3) 令V v j V , V \ v j V (4) 重复2、3两步，一直到图中所有点均包含在V中为止. 2. 破圈法寻找最小部分树的思路： 从网络图N中任取一回路，去掉这个回路中权数最大 的一条边, 得一子网络N1. 在N1中再任意取一回路, 再去掉回路中权数最大的一 条边, 得N2,如此继续下去一直到剩下的子图中不再包含 回路为止.第13页

例：分别用避圈法和破圈法求下图的最小部分树. A A V 1. 避圈法 A3B 2 E 5 6 D B 2 E 3 5 6 D B 2 E

3

1 C 4 4 3 F 2 A 3 B 2 E

1 C 4 4 3 F 2 2

5

6 D

1 C 4 4 3 F 2 A 3

A5 6 D B 2 E 3 5 6 D B 2 E 1 C 4 4 3 F 2

5

6 D

1 C 4 4 3 F 2

1 C 4 4 3 F 2

A3 B 2 E 5 6 D第14页

1 C 4 4 3 F 2

分别用避圈法和破圈法求下图的最小部分树.A 3B 2 E 5 6 D B 2 E

2. 破圈法3

A 5 D B 2 E

A 31 C 4 4 3 F 2 D

1 C 4 4 3 F 2

1 C 4 4 3 F 2

A 3 B 2 E 1 C 2 F 4 D 3

A

B2 E

1 C 2 3 F

4 D

第15页

§6.3 最短路问题最短路问题，一般来说就是从给定的网络图中找出任意 两点之间距离最短的一条路. 求最短路有两种算法： 1. 求从某一点至其余各点之间最短距离的狄克斯屈拉算法； 2. 求网络图上任意两点之间最短距离的矩阵算法.

第16页

6.3.1 Dijkstra 算法 算法的基本思路：假定 v1 v2 v3 vn 1 vn 是v1 vn的最短路， 则 vi vi 1 v j 1 v j 一定是vi v j 的最短路.

(1 i j n)

符号说明：d ij : 两相邻两点i 与j 的距离d ii 0 d ij 点i 与j不相邻. Lsi : 从点s 到点i 的最短距离.

第17页

算法的基本步骤：(1) 从点s出发, 因Lss=0, 将此值标注在s旁的小方框内, 表示s 点已经标号；(2) 从点s出发, 找出与s相邻的点中距离最小的一个, 设为r. 将Lsr=Lss+dsr的值标注在r 旁的小方框内, 表明r点也以标号； (3) 从已标号的点出发, 找出与这些点相邻的所有未标号的 点p. 若有Lsp=min{Lss+dsp ; Lsr+drp}, 则对p点标号, 并将Lsp的值标 注在p点 旁的小方框内； (4) 重复第3步，一直到t点得到标号为止.

第18页

例: 用Dijkstra 算法求下图中从v1到其它点的最短路. 解:3 0

v25 6 1 v3 4 3 2 4

v23

v52

v6

0

5 6 1 1 4

4

v1

v12

v3 3 v4

v5

2

v6

V

v4

L1r=min{d12, d13, d14}= d13=1 v23 0 3

L1p=min{L11+d12, L13+d32, L13+d35, L13+d34 ,L11+d14}= L11+d14=23

v20 5 6 1 1 4 4

5 6 1 1 4

4

v12

v3 32 v 4

v52

v6

v12

v3 32 v4

v52

v6

L1p=min{L12+d25, L12+d25, L13+d35, L14+d46}

L1p=min{L11+d12, L13+d32, L13+d35, L14+d46} = L11+d12=3第19页

= L14+d46=4

v23 0

34 3

v2v60

34

5 6 1 1 4

v12

v3 32 v 4

v52

5 6 1 1 4

v12

v3 32 v 4

v52

v64

L1p=min{L12+d25, L12+d25, L13+d35, L14+d46} = L14+d46=4

L1p=min{L12+d25, L13+d35}= L13+d35=5 v23 0 3 4 5

5 6 1 1 4

v64

v12

v3 32 v 4

v52

第20页

6.3.2 每对顶点间的最短路算法寻求赋权图中各对顶点之间最短路，显然可以调用 Dijkstra 算法。具体方法是：每次以不同的顶点作为起点， 用 Dijkstra 算法求出从该起点到其余顶点的最短路径， 反复执行次这样的操作，就可得到每对顶点之间的最短路。 但这样做需要大量重复计算，效率不高。

R. W. Floyd(弗洛伊德)另辟蹊径，提出了比这更好 的算法，操作方式与 Dijkstra 算法截然不同。

第21页