第5章 图与网络分析

图与网络分析

第5章 图与网络分析( Graph Theory and Network Analysis )

图的基本概念与模型树 最短路问题

网络的最大流最小费用流 应用举例

图与网络分析

第一节 图的基本概念与模型近代图论的历史可追溯到18世纪的七桥问题—穿过 Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不 可能存在这样的路线。

Kö nigsberg桥对应的图

图与网络分析

一、图基本概念例1、有甲、乙、丙、丁、戊五个球队， 它们之间比赛的情况也可以用图表示出来。V5 e5 e4 e6 e7 e2 e3 V3 V4

V1e1 V2

图与网络分析

例2 某单位储存八种化学药品，其中某些 药品是不能存放在同一个库房里的。为了反映 这个情况可以用点V1,V2,……V8分别代表这八 种药品，若药品Vi和药品Vj是不能存放在同 一个库房的，则在Vi和Vj之间连一条线。V2 V1 · V8 V3 V4 V5

V6 V7

图与网络分析

一般地，当用图论研究一个实际问题时， 常以顶点(Vertex)表示要研究的对象，以 它们之间的连线，表示某种关系，这种连线 称为边(Edge),目的是为了解决某个极值 问题。图中的点用v表示，边用e表示。对每 条边可用它所连接的点表示， 记作：e1=[v1,v1]; e2=[v1,v2]; 图的表示方法：

G {V , E }

图与网络分析

运筹学中研究的图具有下列特征:强调点与点之间的关联关系，不讲究图的比例大 小与形状； 每条边上赋有一个权；

建立网络模型，求最大值或最小值。

图与网络分析

下图可以提出很多极值问题2 1 6 3 3 1 3 1 2 3 7 7 6 4 8

6

4

6

5

67

图与网络分析

二、关于图的另外一些名称和术语：端点,关联边,相邻e1

若有边e可表示为e=[vi,vj],称vi和vj 是边e的端点，反之称边e为点vi或vj 的关联边。若点vi、vj与同一条边关 联，称点vi和vj相邻；若边ei和ej具 有公共的端点，称边ei和ej相邻。v2

e2

v1 e4 e5

e3 v3

e6

e7

e8

v4

v5

图与网络分析

环, 多重边, 简单图 如果边e的两个端点相重，称该边为 环。如右图中边e1为环。如果两个点 之间多于一条，称为多重边，如右图v2 e2

e1 v1

e4e5

e3 v3

中的e4和e5,对无环、无多重边的图称作简单图。

e6

e7

e8

v4

v5

图与网络分析

次，奇点，偶点，孤立点 与某一个点vi相关联的边的数目称为 点vi的次(也叫做度),记作d(vi)。 右图中d(v1)=4,d(v3)=5,d(v5)=1。次 为奇数的点称作奇点，次为偶数的v2

e1

e2

v1 e4 e5

e3 v3

e6

e7

e8

点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。v4 v5

图的次: 一个图的次等于各点的次之和。

图与网络分析

定理1 任何图中，顶点次数之和等于所有边数的2倍。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边 均被计算了两次，所以顶点次数的总和等于边数的2倍。

定理2 任何图中，次为奇数的顶点

必为偶数个。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：v V1

d ( v ) d ( v ) d ( v ) 2mv V2 v Vv V1

2m为偶数，且偶点的次之和 d (v ) 也为偶数，所以 d (v ) 必为偶 v V2 数，即奇数点的个数必为偶数。

图与网络分析

链，圈，连通图 图中某些点和边的交替序列，若其 中各边互不相同，且对任意vi,t-1和 vit均相邻称为链。用μ表示：e2 v2

e1 v1 e4 e5 e6 e3 v3 e8

{v 0 , e1 , v1 , , e k , v k }

起点与终点重合的链称作圈。如 果每一对顶点之间至少存在一条 链，称这样的图为连通图，否则 称图不连通。

e7

v4

v5

图与网络分析

子图，部分图(支撑子图) 图G1={V1、E1}和图G2={V2,E2}如果有V1 V2 和E1 E 2 称G1是G2的一个子图。 若有 V1=V2,E1 E 2 ,则称G1是G2的一v2 e2

e1 v1 e4 e5 e6 e3 v3 e7 e8 e3 v3

个部分图(支撑子图)。e4 v2 e5 e6 e8 v3

v1 e2 e4

v2 e6

v4

(G图)

v5

e7

e8

v4

v5

(a)

v4

(b)

v5

图与网络分析

网络(赋权图)赋权图):权可以代表距离、费用、通过能力(容量)等等。 无向网络:端点无序的赋权图称为.

有向网络:端点有序的赋权图称为。② 9 ① 20 ③ 10 19 7

15④

146

⑤

⑥ 25

图与网络分析

图的矩阵描述： 邻接矩阵、关联矩阵、权矩阵等。 1. 邻接矩阵 对于图G=(V,E),| V |=n, | E |=m,有n n阶方矩阵 A=(aij) n n,其中v 1 当 且 仅 档 i 与v j之 间 有 关 联 边 时 a ij 0 其 它

图与网络分析

图的基本概念与模型例6.2 下图所表示的图可以构造邻接矩阵A如下v13 v6 3 6 3 4 7 v2

2v3 5

v1 v2 v3 v4 v5 v6 v1 0 v 2 1 v3 0 v 4 1 v5 1 v6 1 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0

4 2v5 v4

A6 6

图与网络分析

2. 权矩阵

对于赋权图G=(V,E), 其中边 (vi , v j )有权 w i j , 构造矩阵B=(bij) n n 其中： wi j bi j 0 (v i , v j ) E (v i , v j ) E

图与网络分析

例6.4 下图所表示的图可以构造权矩阵B如下:v1 3 v6 3 4 2 v5 6

47

v2 2

3 5 v4

v3

v1 0 v 2 4 v 3 0 B v 4 6 v 5 4 v 6 3 v1

4 0 6 4 3 0 2 7 0 0 2 0 5 0 3 7 5 0 2 0 0 0 2 0 3 0 3 0 3 0 v2 v3 v4 v5 v6

图与网络分析

顶点数p

边数q

环

重 合

简单图

矩阵表示 A 邻接矩阵 B 关联矩阵

端点

G=(V,E)

边e=[u,v] 多重边平行边

含

子图0

点的次1 奇数 偶数

多重图

子 生 图 成 子 图

点边关系 孤 悬 立 挂 点 点 奇 点 偶 点 各种链的概念

图与网络分析

欧拉图与中国邮路问题欧拉图

哥尼斯堡七桥问题哥尼斯堡(现名加里宁格勒)是欧洲一个城市， Pregei河把该城分成两部分，河中有两个小岛，十八世纪 时，河两边及小岛之间共有七座桥，当时人们提出这样 的问题：有没有办法从某处(如A)出发，经过各桥一次 且

仅一次最后回到原地呢？

图与网络分析

哥尼斯堡七桥问题

a

C

d

b

本文来源：https://www.bwwdw.com/article/zj34.html