1
图与网络分析 Graph Theory and Network Analysis
图与网络分析引言十八世纪的哥尼斯堡城中流过一条河（普雷,格尔河），河上有
7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。
2
图与网络分析 Graph Theory and Network Analysis
图与网络分析引言
“哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 O.K?nig写出了 图论的第一本专著,有限图与无限图的理论,。
在图论的发展过程中还有两位著名科学家值得一提，他们是克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。
3
图与网络分析 Graph Theory and Network Analysis
图与网络分析引言图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了 ——历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，
两人都明白这一问题，但是，两人都无能为力。”幸运的是在
1970’s 终于由美国的 两位数学家借助大型计算机将其证明了。
4
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图论与网络分析理论所研究的问题十分广泛，内容极其丰富。
正如一位数学家所说：“可以说，图论为任何一个 包含了某种二元关系 的系统提供了一种分析和描述的模型。”
下面我们来看一个案例 ——
国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：
5
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念各办事处已订购机票情况表：
成都 重庆 武汉 上海 西安 郑州 沈阳 昆明 广州 北京成都 10 5 15 8 12 10 30
重庆 5 6 15 25
武汉 10
上海 15 8
西安 8 6
郑州 14 8
沈阳 18
昆明 8 10
广州 8 2 6 10
6
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念将此问题通过图的模型描述：
下图中，点 ——各城市，带箭头连线 ——从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字 ——机票数量。
成重武昆上广西 郑沈京
8
郑州办事处已订有的到北京的机票数量。
7
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图及其分类和术语图论中所研究的图并非几何学中的图，也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，也就是说我们研究的是某个系统中的元素 ——点，以及这些元素之间的某种关系 ——连线。
定义,图 ——一个图 G 是一个有序二元组（ V,E），记为 G
=（ V,E）其中（ 1） V 是一个有限非空的集合，其元素称为 G 的点或顶点，而称 V为 G 的点集 V ={v1,v2,···,vn}；（ 2） E 是 V
中元素的无序对 (vi,vj) 所构成的一个集合，其元素称为 G 的边，
一般表示为 e =(vi,vj)，而称 E 是 G 的边集。
8
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图及其分类和术语边（无向边） ——没有方向的连线弧（有向边） ——带有方向的连线无向图 有向图 简单图 多重图完全图 二部图（偶图，双图） 子图真子图 生成子图 点生成子图边生成子图 点的次 奇次点 偶次点链 圈 路 回路赋权图
9
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图及其分类和术语连通图在众多各类图中有一类在实际应用中占有重要地位的图连通图 ——在图中，任意两点间至少存在着一条链。
连通图 不连通图
10
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图与矩阵在图与网络分析的应用中，将面临一个问题 ——如何分析、
计算一个较大型的网络，这当然需借助快速的计算工具 ——计算机。
那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有 ——
邻接矩阵、关联矩阵、权矩阵等。
11
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图与矩阵邻接矩阵 ——对于图 G =（ V,E）,| V |=n,| E | =m，有 n?n 阶方 矩阵 A =（ aij） n?n,其中
aij = k 当且仅当 vi与 vj之间有条边时
0 其它关联矩阵 ——对于图 G =（ V,E）,| V |=n,| E | =m，有 m?n 阶矩阵 M =（ mij） m?n,其中
mij = 2 当且仅当 vi是边 ej 的两个端点
1 当且仅当 vi是边 ej 的一个端点
0 其它
12
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图与矩阵例
v1
v2
v3
v5
v4
v8
v6
v7
e1
e2
e3
e4e6
e5
e7
e9
e12 e10
e11
e8
A=（ aij） n?n=
0 1 0 0 1 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 1 0 0 2
0 0 0 0 0 1 1 0
1 1 1 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 0 1 1 1 0 0
0 0 2 0 1 0 0 0
v1
v2
v3
v4
v5
v6
v7
v8
v1 v2 v3 v4 v5 v6 v7 v8
M=（ mij） =
1 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1
0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 1 0 0 1 1 0 0 0 0
v1
v2
v3
v4
v5
v6
v7
v8
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12
13
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树树是图论中一类重要的图，实际中有很多系统的结构都是树。
树 ——连通且不含圈的图，简记为 T 。
下面的说法是等价的：
T 是一个树。 T 无圈，且 m = n-1。 T 连通，且 m =
n-1。 T无圈，但每加一条新的边即出现唯一一个圈。 T连通，但每舍去一条边就不连通。 T中任意两点，有唯一的一条链相连。 T是边数最少的 连通图。
14
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树图的生成树 —— 若 G图的一个点 生成子图是一个树，则称此树是 G
图的一个 生成树。
树的权 —— 若 Tk是加权图 G的一棵树，则树 T的全部边的权之和称为树 Tk的权，记为?（ Tk ） =（ e）；? e? Tk
最小树 —— T*是加权图 G的一棵 最小 树，即?（ T* ） =min{? (Tk) }
15
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树破圈法，避圈法求 生成树：
图 G
生成树 T
生成树 T
16
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树破圈法，避圈法求最小 生成树：
图 G
1
5
4
2
4
5
3
1
3
4
4
2
1
5
1
2
生成最小树 T
生成最小树 T
1
2
3
1
2
11
2
1
2
3
1
2
11
2
17
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用有向树 ——若一个有向图在不考虑边的方向时是一棵树。
出次 —— 入次 ——
根树 ——有向树 T,恰有一个结点入次为 0,其余各个点入次均为
1。
叉树 ——在根树中，若每个顶点的出次小于或等于 m,称其为 m
叉树。若每个顶点的出次恰好等于 m 或 0,则称其为完全 m 叉树。
4 叉树 完全 3 叉树
18
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用应用中常常讨论的是叶子上带有权的 2 叉树。
2 叉树 T 的总权数：
pi —— 2 叉树 T 的树叶 i 的权，
li —— 树根到树叶 i 的距离（层次） i = 1,2,…,s
m（ T） —— 2 叉树 T 的总权数
m（ T） = ∑ pi li
s
i = 1
满足总 权最小的 2 叉树 T* 称为最优 2 叉树，又称霍夫曼树。
霍夫曼（ D,A,Huffman）给出了一个求最优 2 叉树的算法。
19
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用求最优 2 叉树的霍夫曼算法：
（ 1）将 s 个叶子按权由小至大排序，不妨设为 p1≤ p2 ≤ … ≤ ps 。
（ 2）将二个具有最小权的叶子合并成一个分枝点，其权为 p1 + p2,
将新的分枝点作为一个叶子。令 s? s – 1,若 s = 1，停止，
否则转（ 1）。
最优 2 叉树的直观意义：叶子的距离随着权的递减而增加，
所以总权最小。
20
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用例 s = 6，其权分别为 4,3,3,2,2,1，求最优 2 叉树。
1 2 2 3 3 4
3
1 2
3
5
2 3 3 4
总权为：
1× 4 + 2 × 4 + 2 × 3 + 3 × 2 + 3 × 2
+ 4 × 2 = 38
6
21
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用最优 2 叉树的应用最优检索问题 ——使用计算机进行图书分类。
有五类图书共 100 万册，其中有 A 类 50 万册,B 类 20 万册，
C 类 5 万册,D 类 10 万册,E 类 15 万册。问如何安排分检过程，
可使总运算（比较）次数最少？
解：构造一棵有 5 个叶子的最优 2 叉树，其叶子的权分别为
50,20,5,10,15。总权为：
m（ T*） = 5× 4 + 10 × 4 + 15 × 3 + 20 × 2 + 50 × 1 = 195
22
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用最优 2 叉树的应用
5 10 15 20 50
15
30
50
C D E B A
100
A？
B？ A
N Y
E？ B
N Y
D？ E
N Y
D
N Y
C
23
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路最短路问题是网络分析中应用最广泛的问题之一。尽管前面介绍了用动态规划方法求解，但有时却较困难，此时图论的方法却十分有效。
最短路问题的一般描述：
G = （ V,E）是连通图，图中各边（ vi,vj） 有权 lij（ =?表示 vi,vj
间无边 ）,vs,vt为 图中任意两指定点，求一条路 μ，使其是从 vs
到 vt的所有路中最短（路中各边的权之和最小）的一条路。即
L（ μ ） = min? lij
（ vi,vj）?μ
24
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路
E.W.Dijkstra 算法（标号算法）
算法基本思路分析：（逐步向外搜索）
5 2
1
6
5
8
2
8
9
9
7
2
2
1
2
1
0
∞
∞
∞
∞
∞
∞
∞
∞
2
5
75 11 12
12
107
6
9
10
63
x
y
起点到该点的最短距离起点到该点的最短距离的 上界
25
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路
E.W.Dijkstra 算法（标号算法）的条件是所有边的权 lij ≥ 0,
当网络中带有负权边时，该算法失效。此时，有所谓逐次逼近算法
（修改的标号算法）。
逐次逼近算法 ——求网络中某一指定点 v1 到任意点的最短距离
（最短路）。算法的基本思路是,v1 到 vj 的最短路总是沿着该路从 v1 先到达某一点 vi,然后再沿边（ vi,vj ）达到 vi,则 v1 到
vi 的这条路必然也是 v1 到 vi 的最短路。若令 P1j 表示从 v1 到 vj 的最短路长，则必有如下方程：
P1j = min（ P1i + lij ）
i
26
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路逐次逼近算法采用迭代方法解上述方程。
（ 1） 开始时令 P（ 1） 1j = l1j （ j = 1,2,…,n），即以 v1 到 vj 的直接距离（经过一步）做初始解，若 v1 与 vj 间无边，则记 l1j = +∞。
（ 2） 从第二步起，使用迭代公式
P （ k） 1j = min（ P （ k-1） 1i + lij ） （ k = 2,3,… ）
当进行到第 t 步时，若出现 P （ t） 1j = P （ t-1） 1j,则算法停止，
P （ t） 1j （对一切 j ）即为 v1 到各点的最短路长当进行到第 n 步时，若仍有 P （ n） 1j≠ P （ n-1） 1j,（对一切 j ），
则算法停止，此时可知网络中含有负回路。
27
图与网络分析 Graph Theory and Network Analysis
路与最短路问题最短路问题最短路问题大量存在于经济管理、生产计划、以及我们的许多日常生活之中。
例 人、狼、羊、草渡河游戏。规则略
M（ Man）,W（ Wolf）,G（ Goat）,H（ Hay）。
点 —— vi 表示河岸的状态边 —— ek 表示由状态 vi 经一次渡河到状态 vj
权 —— 边 ek 上的权定为 1。
我们可以得到下面的加权有向图：
28
图与网络分析 Graph Theory and Network Analysis
路与最短路问题最短路问题
v1,u1 =（ M,W,G,H）； v2,u2 =（ M,W,G）；
v3,u3 =（ M,W,H）； v4,u4 =（ M,G,H）；
v5,u5 =（ M,G）。
此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。
v1 v2 v3 v4 v5
u5 u4 u3 u2 u1
29
图与网络分析 Graph Theory and Network Analysis
路与最短路问题最短路问题例 设备更新问题例 选址问题（网络的中心、重心）
某地 7 个村镇之间的现有交通道路如下图，边旁数值为各村镇之间道路的长度，点旁数值为各村镇的小学生人数。现拟在某一村镇建一商店和小学，试问：
（ 1）商店应该建在何村，能使各村都离它较近？
（ 2）小学应该建在何村，能使各村小学生总的行走路程最短？
30
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心
v1
v3
v4
v5
v6
v7v2
7
4
6
4
3 5
7
1 2
3
2
4
2
30
40
45 35
25
20 50
距离人数
31
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心距离矩阵摹乘法求各点至各点的最短距离网络的距离矩阵设一网络 N 中有 n 个点，其中任意两点 vi 与 vj 之间都有一条边 ( vi,vj )，其权数为 wij > - ∞。若 vi 与 vj 不相邻，则虚设一条边
( vi,vj )，并令其权数 wij = ∞。
距离矩阵 W = （ wij ）
32
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心距离矩阵摹乘法
v1
v3
v4
v5
v6
v7v2
7
4
6
4 3 5
7
1 2
3
2
4
2
30
40
45 35
25
20
50
W =
v1 v2 v3 v4 v5 v6
v1 0 3 2 ∞ ∞ 4
v2 ∞ 0 4 ∞ 4 1
v3 ∞ ∞ 0 -1 6 ∞
v4 3 -2 ∞ 0 1 ∞
v5 5 ∞ ∞ ∞ 0 3
v6 ∞ ∞ 3 3 ∞ 0
33
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心距离矩阵摹乘运算记矩阵 Dk = （ d（ k） ij） n× n
当 k = 1 时，令
D1 = （ d（ 1） ij） n× n = （ wij） n× n = W
定义 Dk = Dk-1? Dk-1,（ k =,1,2,…,p） 摹乘运算其中
d（ k） ij = min {d（ k-1） is + d（ k-1） sj },i,j = 1,2,…,n
摹乘运算的含义：
表示从各点走 2k-1 步达到各点的最短距离矩阵。而 D 即给出各点到各点的最短距离。若计算中出现 Dk = Dk-1,也可结束。
s
34
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心设 D = （ dij） n× n 为一网络各点间的最短距离矩阵。
（ 1 ） 网络的中心令,d( vi ) = max? dij?,i = 1,2,…,n
若 d( vk ) = max? d( vi )?
1≤i≤n
1≤j≤n
则称点 vk 为网络的中心。
35
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心
（ 2 ） 网络的重心设 gi 为点 vi 的权重（ i = 1,2,…,n ），
令,h ( vj ) = ∑ gidij,j = 1,2,…,ni=1
n
若 h( vr ) = max? h( vj )?1≤j≤n
则称点 vr 为网络的重心。
36
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心前例 vj
vi
D = ( dij ) d( vi )= max? dij?
1 2 3 4 5 6 7
1 0 3 4 5 7 8 10 10
2 3 0 3 2 4 5 7 7
3 4 3 0 5 5 6 8 8
4 5 2 5 0 2 3 5 5 ( min )
5 7 4 5 2 0 1 3 7
6 8 5 6 3 1 0 2 8
7 10 7 8 5 3 2 0 10
结论,商店应该建在 v4 村（ v4 村是网络的 中心 ）。
37
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心
vj
vi
gidij
1 2 3 4 5 6 7
1 0 120 160 200 280 320 400
2 75 0 75 50 100 125 175
3 180 135 0 225 225 270 360
4 150 60 150 0 60 90 150
5 140 80 100 40 0 20 60
6 280 175 210 105 35 0 70
7 500 350 400 250 150 100 0
h ( vj ) 1325 920 1095 870 850 ( min ) 925 1215
结论,小学应该建在 v5 村（ v5 村是网络的 重心 ）。
38
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题最大流问题是一类应用极为广泛的问题，如运输网络中的人流、
车流、物流，供水网络中的水流，金融系统中的现金流，通信系统中的信息流，等等。 20 世纪 50 年代 Ford – Fulkerson 建立的
,网络流理论,，是网络应用的重要组成部分。
39
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题概念容量网络 —— N=（ V,E,R ），发点 vs，收点 vt 。
1、网络流 ——
2、可行流 ——
3、最大流 ——
4、增广链 ——
5、最小截集 ——
40
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题理论
1、流量 ——截量定理容量网络上任何一个可行流的流量不超过任何一个截集的截量。
2、增广链调整定理在增广链上对可行流进行调整可以得到一个流量更大的可行流。
3、最大流定理可行流是最大流的充分必要条件是不存在关于该可行流的增广链。
41
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法容量网络 N 上最大流的标号（ Ford-Fulkerson）算法：
我们采用此算法来求解前面的旅行总社计划问题案例 ——
发点 vs =成都，收点 vt =北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。
42
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成
0,+∞
标号，但未检查 标号，且已检查
vs,30
0+30
43
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
0,+∞
vs,10
vs,15
vs,12
vs,10
vs,8
vs,15
，
v7,10
v7,8
，
0+10 0+10
44
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
6 6
12
2
84
122
10
6
10
10
0
0
0
0
10
8
0
18
0
100
0,+∞
vs,8
vs,13
v2,4
，
-v2,4
v1,4
，
+4
4-4
+4
v1,4
45
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
6 6
12
2
80
126
10
6
10
10
0
0
0
0
10
8
0
18
4
100
vs,8
vs,9
v2,4
0,+∞
-v4,6
，
v1,6
，
+6
-6
+6
，
46
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
0 6
12
2
80
126
10
6
10
10
6
0
0
0
10
8
0
18
10
100
vs,9
0,+∞
vs,2
v2,4
，
v3,4
，
v5,4
-v5,2
，
，
，
，
47
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
0 6
12
2
80
126
10
6
10
10
6
0
0
0
10
8
0
18
10
100
v ( f* ) =10+6+12+30+12+10+6 = 86
48
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法在 Excel 上建立网络模型及其求解方法
49
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题最小费用大流问题前面讨论的旅行社的计划问题中，旅行社解决了将尽可能多的游客（ 86人）送往了目的地 ——北京，但旅行社计划时没有考虑机票的成本。现在旅行社考虑的问题是既要送出尽可能多的游客（ 86
人），又要使机票的总成本最低，应该如何制定新的计划呢？这就是 最小费用大流 所研究解决的一类流量问题。
最小费用大流问题还广泛应用于诸如 最优匹配，运输问题 等一类问题。
应该注意的是：最小费用大流问题首先要解决网络上的最大流，
目的是寻找使总费用达到最小的那个最大流。
50
图与网络分析 Graph Theory and Network Analysis
第十章结束谢谢！
图与网络分析 Graph Theory and Network Analysis
图与网络分析引言十八世纪的哥尼斯堡城中流过一条河（普雷,格尔河），河上有
7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡 7 桥”难题。
2
图与网络分析 Graph Theory and Network Analysis
图与网络分析引言
“哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到 1936 年匈牙利数学家 O.K?nig写出了 图论的第一本专著,有限图与无限图的理论,。
在图论的发展过程中还有两位著名科学家值得一提，他们是克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。
3
图与网络分析 Graph Theory and Network Analysis
图与网络分析引言图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了 ——历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，
两人都明白这一问题，但是，两人都无能为力。”幸运的是在
1970’s 终于由美国的 两位数学家借助大型计算机将其证明了。
4
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图论与网络分析理论所研究的问题十分广泛，内容极其丰富。
正如一位数学家所说：“可以说，图论为任何一个 包含了某种二元关系 的系统提供了一种分析和描述的模型。”
下面我们来看一个案例 ——
国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：
5
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念各办事处已订购机票情况表：
成都 重庆 武汉 上海 西安 郑州 沈阳 昆明 广州 北京成都 10 5 15 8 12 10 30
重庆 5 6 15 25
武汉 10
上海 15 8
西安 8 6
郑州 14 8
沈阳 18
昆明 8 10
广州 8 2 6 10
6
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念将此问题通过图的模型描述：
下图中，点 ——各城市，带箭头连线 ——从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字 ——机票数量。
成重武昆上广西 郑沈京
8
郑州办事处已订有的到北京的机票数量。
7
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图及其分类和术语图论中所研究的图并非几何学中的图，也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连接，也就是说我们研究的是某个系统中的元素 ——点，以及这些元素之间的某种关系 ——连线。
定义,图 ——一个图 G 是一个有序二元组（ V,E），记为 G
=（ V,E）其中（ 1） V 是一个有限非空的集合，其元素称为 G 的点或顶点，而称 V为 G 的点集 V ={v1,v2,···,vn}；（ 2） E 是 V
中元素的无序对 (vi,vj) 所构成的一个集合，其元素称为 G 的边，
一般表示为 e =(vi,vj)，而称 E 是 G 的边集。
8
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图及其分类和术语边（无向边） ——没有方向的连线弧（有向边） ——带有方向的连线无向图 有向图 简单图 多重图完全图 二部图（偶图，双图） 子图真子图 生成子图 点生成子图边生成子图 点的次 奇次点 偶次点链 圈 路 回路赋权图
9
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图及其分类和术语连通图在众多各类图中有一类在实际应用中占有重要地位的图连通图 ——在图中，任意两点间至少存在着一条链。
连通图 不连通图
10
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图与矩阵在图与网络分析的应用中，将面临一个问题 ——如何分析、
计算一个较大型的网络，这当然需借助快速的计算工具 ——计算机。
那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有 ——
邻接矩阵、关联矩阵、权矩阵等。
11
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图与矩阵邻接矩阵 ——对于图 G =（ V,E）,| V |=n,| E | =m，有 n?n 阶方 矩阵 A =（ aij） n?n,其中
aij = k 当且仅当 vi与 vj之间有条边时
0 其它关联矩阵 ——对于图 G =（ V,E）,| V |=n,| E | =m，有 m?n 阶矩阵 M =（ mij） m?n,其中
mij = 2 当且仅当 vi是边 ej 的两个端点
1 当且仅当 vi是边 ej 的一个端点
0 其它
12
图与网络分析 Graph Theory and Network Analysis
图与网络的基本概念图与矩阵例
v1
v2
v3
v5
v4
v8
v6
v7
e1
e2
e3
e4e6
e5
e7
e9
e12 e10
e11
e8
A=（ aij） n?n=
0 1 0 0 1 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 1 0 0 2
0 0 0 0 0 1 1 0
1 1 1 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 0 1 1 1 0 0
0 0 2 0 1 0 0 0
v1
v2
v3
v4
v5
v6
v7
v8
v1 v2 v3 v4 v5 v6 v7 v8
M=（ mij） =
1 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1
0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 1 0 0 1 1 0 0 0 0
v1
v2
v3
v4
v5
v6
v7
v8
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12
13
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树树是图论中一类重要的图，实际中有很多系统的结构都是树。
树 ——连通且不含圈的图，简记为 T 。
下面的说法是等价的：
T 是一个树。 T 无圈，且 m = n-1。 T 连通，且 m =
n-1。 T无圈，但每加一条新的边即出现唯一一个圈。 T连通，但每舍去一条边就不连通。 T中任意两点，有唯一的一条链相连。 T是边数最少的 连通图。
14
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树图的生成树 —— 若 G图的一个点 生成子图是一个树，则称此树是 G
图的一个 生成树。
树的权 —— 若 Tk是加权图 G的一棵树，则树 T的全部边的权之和称为树 Tk的权，记为?（ Tk ） =（ e）；? e? Tk
最小树 —— T*是加权图 G的一棵 最小 树，即?（ T* ） =min{? (Tk) }
15
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树破圈法，避圈法求 生成树：
图 G
生成树 T
生成树 T
16
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题树（ Tree）和最小树破圈法，避圈法求最小 生成树：
图 G
1
5
4
2
4
5
3
1
3
4
4
2
1
5
1
2
生成最小树 T
生成最小树 T
1
2
3
1
2
11
2
1
2
3
1
2
11
2
17
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用有向树 ——若一个有向图在不考虑边的方向时是一棵树。
出次 —— 入次 ——
根树 ——有向树 T,恰有一个结点入次为 0,其余各个点入次均为
1。
叉树 ——在根树中，若每个顶点的出次小于或等于 m,称其为 m
叉树。若每个顶点的出次恰好等于 m 或 0,则称其为完全 m 叉树。
4 叉树 完全 3 叉树
18
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用应用中常常讨论的是叶子上带有权的 2 叉树。
2 叉树 T 的总权数：
pi —— 2 叉树 T 的树叶 i 的权，
li —— 树根到树叶 i 的距离（层次） i = 1,2,…,s
m（ T） —— 2 叉树 T 的总权数
m（ T） = ∑ pi li
s
i = 1
满足总 权最小的 2 叉树 T* 称为最优 2 叉树，又称霍夫曼树。
霍夫曼（ D,A,Huffman）给出了一个求最优 2 叉树的算法。
19
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用求最优 2 叉树的霍夫曼算法：
（ 1）将 s 个叶子按权由小至大排序，不妨设为 p1≤ p2 ≤ … ≤ ps 。
（ 2）将二个具有最小权的叶子合并成一个分枝点，其权为 p1 + p2,
将新的分枝点作为一个叶子。令 s? s – 1,若 s = 1，停止，
否则转（ 1）。
最优 2 叉树的直观意义：叶子的距离随着权的递减而增加，
所以总权最小。
20
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用例 s = 6，其权分别为 4,3,3,2,2,1，求最优 2 叉树。
1 2 2 3 3 4
3
1 2
3
5
2 3 3 4
总权为：
1× 4 + 2 × 4 + 2 × 3 + 3 × 2 + 3 × 2
+ 4 × 2 = 38
6
21
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用最优 2 叉树的应用最优检索问题 ——使用计算机进行图书分类。
有五类图书共 100 万册，其中有 A 类 50 万册,B 类 20 万册，
C 类 5 万册,D 类 10 万册,E 类 15 万册。问如何安排分检过程，
可使总运算（比较）次数最少？
解：构造一棵有 5 个叶子的最优 2 叉树，其叶子的权分别为
50,20,5,10,15。总权为：
m（ T*） = 5× 4 + 10 × 4 + 15 × 3 + 20 × 2 + 50 × 1 = 195
22
图与网络分析 Graph Theory and Network Analysis
图的树与最小树问题根树及其应用最优 2 叉树的应用
5 10 15 20 50
15
30
50
C D E B A
100
A？
B？ A
N Y
E？ B
N Y
D？ E
N Y
D
N Y
C
23
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路最短路问题是网络分析中应用最广泛的问题之一。尽管前面介绍了用动态规划方法求解，但有时却较困难，此时图论的方法却十分有效。
最短路问题的一般描述：
G = （ V,E）是连通图，图中各边（ vi,vj） 有权 lij（ =?表示 vi,vj
间无边 ）,vs,vt为 图中任意两指定点，求一条路 μ，使其是从 vs
到 vt的所有路中最短（路中各边的权之和最小）的一条路。即
L（ μ ） = min? lij
（ vi,vj）?μ
24
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路
E.W.Dijkstra 算法（标号算法）
算法基本思路分析：（逐步向外搜索）
5 2
1
6
5
8
2
8
9
9
7
2
2
1
2
1
0
∞
∞
∞
∞
∞
∞
∞
∞
2
5
75 11 12
12
107
6
9
10
63
x
y
起点到该点的最短距离起点到该点的最短距离的 上界
25
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路
E.W.Dijkstra 算法（标号算法）的条件是所有边的权 lij ≥ 0,
当网络中带有负权边时，该算法失效。此时，有所谓逐次逼近算法
（修改的标号算法）。
逐次逼近算法 ——求网络中某一指定点 v1 到任意点的最短距离
（最短路）。算法的基本思路是,v1 到 vj 的最短路总是沿着该路从 v1 先到达某一点 vi,然后再沿边（ vi,vj ）达到 vi,则 v1 到
vi 的这条路必然也是 v1 到 vi 的最短路。若令 P1j 表示从 v1 到 vj 的最短路长，则必有如下方程：
P1j = min（ P1i + lij ）
i
26
图与网络分析 Graph Theory and Network Analysis
路与最短路问题路（ Path）和最短路逐次逼近算法采用迭代方法解上述方程。
（ 1） 开始时令 P（ 1） 1j = l1j （ j = 1,2,…,n），即以 v1 到 vj 的直接距离（经过一步）做初始解，若 v1 与 vj 间无边，则记 l1j = +∞。
（ 2） 从第二步起，使用迭代公式
P （ k） 1j = min（ P （ k-1） 1i + lij ） （ k = 2,3,… ）
当进行到第 t 步时，若出现 P （ t） 1j = P （ t-1） 1j,则算法停止，
P （ t） 1j （对一切 j ）即为 v1 到各点的最短路长当进行到第 n 步时，若仍有 P （ n） 1j≠ P （ n-1） 1j,（对一切 j ），
则算法停止，此时可知网络中含有负回路。
27
图与网络分析 Graph Theory and Network Analysis
路与最短路问题最短路问题最短路问题大量存在于经济管理、生产计划、以及我们的许多日常生活之中。
例 人、狼、羊、草渡河游戏。规则略
M（ Man）,W（ Wolf）,G（ Goat）,H（ Hay）。
点 —— vi 表示河岸的状态边 —— ek 表示由状态 vi 经一次渡河到状态 vj
权 —— 边 ek 上的权定为 1。
我们可以得到下面的加权有向图：
28
图与网络分析 Graph Theory and Network Analysis
路与最短路问题最短路问题
v1,u1 =（ M,W,G,H）； v2,u2 =（ M,W,G）；
v3,u3 =（ M,W,H）； v4,u4 =（ M,G,H）；
v5,u5 =（ M,G）。
此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。
v1 v2 v3 v4 v5
u5 u4 u3 u2 u1
29
图与网络分析 Graph Theory and Network Analysis
路与最短路问题最短路问题例 设备更新问题例 选址问题（网络的中心、重心）
某地 7 个村镇之间的现有交通道路如下图，边旁数值为各村镇之间道路的长度，点旁数值为各村镇的小学生人数。现拟在某一村镇建一商店和小学，试问：
（ 1）商店应该建在何村，能使各村都离它较近？
（ 2）小学应该建在何村，能使各村小学生总的行走路程最短？
30
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心
v1
v3
v4
v5
v6
v7v2
7
4
6
4
3 5
7
1 2
3
2
4
2
30
40
45 35
25
20 50
距离人数
31
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心距离矩阵摹乘法求各点至各点的最短距离网络的距离矩阵设一网络 N 中有 n 个点，其中任意两点 vi 与 vj 之间都有一条边 ( vi,vj )，其权数为 wij > - ∞。若 vi 与 vj 不相邻，则虚设一条边
( vi,vj )，并令其权数 wij = ∞。
距离矩阵 W = （ wij ）
32
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心距离矩阵摹乘法
v1
v3
v4
v5
v6
v7v2
7
4
6
4 3 5
7
1 2
3
2
4
2
30
40
45 35
25
20
50
W =
v1 v2 v3 v4 v5 v6
v1 0 3 2 ∞ ∞ 4
v2 ∞ 0 4 ∞ 4 1
v3 ∞ ∞ 0 -1 6 ∞
v4 3 -2 ∞ 0 1 ∞
v5 5 ∞ ∞ ∞ 0 3
v6 ∞ ∞ 3 3 ∞ 0
33
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心距离矩阵摹乘运算记矩阵 Dk = （ d（ k） ij） n× n
当 k = 1 时，令
D1 = （ d（ 1） ij） n× n = （ wij） n× n = W
定义 Dk = Dk-1? Dk-1,（ k =,1,2,…,p） 摹乘运算其中
d（ k） ij = min {d（ k-1） is + d（ k-1） sj },i,j = 1,2,…,n
摹乘运算的含义：
表示从各点走 2k-1 步达到各点的最短距离矩阵。而 D 即给出各点到各点的最短距离。若计算中出现 Dk = Dk-1,也可结束。
s
34
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心设 D = （ dij） n× n 为一网络各点间的最短距离矩阵。
（ 1 ） 网络的中心令,d( vi ) = max? dij?,i = 1,2,…,n
若 d( vk ) = max? d( vi )?
1≤i≤n
1≤j≤n
则称点 vk 为网络的中心。
35
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心
（ 2 ） 网络的重心设 gi 为点 vi 的权重（ i = 1,2,…,n ），
令,h ( vj ) = ∑ gidij,j = 1,2,…,ni=1
n
若 h( vr ) = max? h( vj )?1≤j≤n
则称点 vr 为网络的重心。
36
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心前例 vj
vi
D = ( dij ) d( vi )= max? dij?
1 2 3 4 5 6 7
1 0 3 4 5 7 8 10 10
2 3 0 3 2 4 5 7 7
3 4 3 0 5 5 6 8 8
4 5 2 5 0 2 3 5 5 ( min )
5 7 4 5 2 0 1 3 7
6 8 5 6 3 1 0 2 8
7 10 7 8 5 3 2 0 10
结论,商店应该建在 v4 村（ v4 村是网络的 中心 ）。
37
图与网络分析 Graph Theory and Network Analysis
路与最短路问题网络的中心、重心
vj
vi
gidij
1 2 3 4 5 6 7
1 0 120 160 200 280 320 400
2 75 0 75 50 100 125 175
3 180 135 0 225 225 270 360
4 150 60 150 0 60 90 150
5 140 80 100 40 0 20 60
6 280 175 210 105 35 0 70
7 500 350 400 250 150 100 0
h ( vj ) 1325 920 1095 870 850 ( min ) 925 1215
结论,小学应该建在 v5 村（ v5 村是网络的 重心 ）。
38
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题最大流问题是一类应用极为广泛的问题，如运输网络中的人流、
车流、物流，供水网络中的水流，金融系统中的现金流，通信系统中的信息流，等等。 20 世纪 50 年代 Ford – Fulkerson 建立的
,网络流理论,，是网络应用的重要组成部分。
39
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题概念容量网络 —— N=（ V,E,R ），发点 vs，收点 vt 。
1、网络流 ——
2、可行流 ——
3、最大流 ——
4、增广链 ——
5、最小截集 ——
40
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题理论
1、流量 ——截量定理容量网络上任何一个可行流的流量不超过任何一个截集的截量。
2、增广链调整定理在增广链上对可行流进行调整可以得到一个流量更大的可行流。
3、最大流定理可行流是最大流的充分必要条件是不存在关于该可行流的增广链。
41
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法容量网络 N 上最大流的标号（ Ford-Fulkerson）算法：
我们采用此算法来求解前面的旅行总社计划问题案例 ——
发点 vs =成都，收点 vt =北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。
42
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成
0,+∞
标号，但未检查 标号，且已检查
vs,30
0+30
43
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
0,+∞
vs,10
vs,15
vs,12
vs,10
vs,8
vs,15
，
v7,10
v7,8
，
0+10 0+10
44
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
6 6
12
2
84
122
10
6
10
10
0
0
0
0
10
8
0
18
0
100
0,+∞
vs,8
vs,13
v2,4
，
-v2,4
v1,4
，
+4
4-4
+4
v1,4
45
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
6 6
12
2
80
126
10
6
10
10
0
0
0
0
10
8
0
18
4
100
vs,8
vs,9
v2,4
0,+∞
-v4,6
，
v1,6
，
+6
-6
+6
，
46
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
0 6
12
2
80
126
10
6
10
10
6
0
0
0
10
8
0
18
10
100
vs,9
0,+∞
vs,2
v2,4
，
v3,4
，
v5,4
-v5,2
，
，
，
，
47
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法重武昆上广西 郑沈京成 30
10
0 6
12
2
80
126
10
6
10
10
6
0
0
0
10
8
0
18
10
100
v ( f* ) =10+6+12+30+12+10+6 = 86
48
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题算法在 Excel 上建立网络模型及其求解方法
49
图与网络分析 Graph Theory and Network Analysis
网络流（ Flow）与最大流问题最小费用大流问题前面讨论的旅行社的计划问题中，旅行社解决了将尽可能多的游客（ 86人）送往了目的地 ——北京，但旅行社计划时没有考虑机票的成本。现在旅行社考虑的问题是既要送出尽可能多的游客（ 86
人），又要使机票的总成本最低，应该如何制定新的计划呢？这就是 最小费用大流 所研究解决的一类流量问题。
最小费用大流问题还广泛应用于诸如 最优匹配，运输问题 等一类问题。
应该注意的是：最小费用大流问题首先要解决网络上的最大流，
目的是寻找使总费用达到最小的那个最大流。
50
图与网络分析 Graph Theory and Network Analysis
第十章结束谢谢！
