F
e3
e5
e7
e10
e13
C
e8
E
由有限个代表事物的点和表示事物间联系线构成，这些 点称为顶点。
为了反映7家企业的业务来往联系，用7个点表示7家企业， 若某两家企业之间存在业务来往，则两点间联线。
数学表达：顶点用V={v1,v2,…,vn}表示；顶点间的连线
称为边，用E={e1,e2, …}表示，则图的表示方法为：
m in z a ij xij
i, j
xij 7
i, j
x12 x13 x24 x34 3 L
19
数据、模型与决策
四、寻找最小生成树的方法
▪ （1）避圈法：开始选一条最小权的边， 以后总从与已选边不构成圈的那些未选 边中，选一条权最小的（相同最小权的 边，任选一条）。
▪ （2）破圈法：任取一圈，从圈中去掉 一条权最大的边（相同权的边，任去一 条），在余下图中，重复此步骤，直到 得到一个不含圈的图，即得最小树。
五、连通图和简单图
▪ 连通图：在图中，任意两点之间都有一条链相连， 叫做连通图。否则是非连通图。非连通图可以由 几个连通图构成。
▪ 环：某边的两个顶点相同； ▪ 多重边：两个顶点之间多于一条边。 ▪ 简单图：没有环和多重边的图是简单图。
A
e11
S
e4
e9
B e6
D e12
F
e3
e7
e10
e13
C
E
9
G={V,E}
3
数据、模型与决策
➢ 无向图：对象之间具有对称性，（甲对乙，乙对甲）。
➢ 有向图：不具有对称性的事物。
➢ A认识B，B一定认识A?A到B的距离，一定等于B到A的距 离？
➢ 为了反映球队之间比赛胜负关系，则球队之间单纯用一 条联线就难以表达。
➢ 对策：带箭头的线，有向线－－－有向图。
v1
5
数据、模型与决策
二、子图与生成子图
➢子图：图G1中的点是图G2中点的一部 分，图G1中的边是图G2中的一部分。
➢生成图：图G1的点与图G2相同，边是
其中的一部分。
v5
v5
v5
v1
v4 v1
v4 v1
v2
v3 v2
v3 v2
v3 6
数据、模型与决策
三、网络图
▪ 各边赋予一定的物理量，例如距离，则叫 做网络图。
▪ 初等链：顶点和边相互交替出现的点不重复序列。
▪ 路：在有向图中，链中每条边的方向和链的走向一致的 链。
▪ 圈：起点和终点相同的链叫做圈。
▪ 回路：起点和终点相同的路叫做回路。
v1
v4
v1
e6
e1
v5 e4
e5
S
T
v2
e2
v3 e3 v4
v2
v3
v5
★任意举出一条链，初等链，路，圈和回路8。
数据、模型与决策
v4
v5
v1
v6
v2
v3
15
数据、模型与决策
三、最小生成树
生成树不唯一
v4 v1 6
1 水塔 5
v2
连接边长度最短？
5
v5
4
架设电话线
7
3
v6
4
2
v 铺设水管 3
16
数据、模型与决策
▪ 设有一个连通图，每一边都有一个非负权， w(e)=wij.
▪ 树的权：树中所有边的权之和。 ▪ 最小生成树：图中，权最小的生成树。
五个城市连通电话线问题
11
数据、模型与决策
五个城市连通电话线问题
▪ 树的基本性质
➢ 任意两点之间有且只有一条链； ➢ 图是树的充要条件：任意两个顶点之间只有一
条链； ➢ 若树有p个顶点，则共有q=p-1条边； ➢ 图是树的充要条件：连通图，边数=顶点数－
1。
12
数据、模型与决策
生成树的概念
➢生成图：图G1的点与图G2相同，边是其中 的一部分。
▪ 所赋予的物理量叫做权。
▪ 权可以是：距离、时间、成本、容量等。
e11表示上海
A
e11
到北京的铁路 长度。
e1
e4
或，旅客从上 海到北京的车
S
e2
票费用
e3
e5
e9
B e6
e7
e10
D e12 e13
F
C
e8
E
7
数据、模型与决策
四、链、路、圈、回路
▪ 链：点和边的交错序列（vi1,ei1,vi2,…,eik-1,vik）,若有 eit=[vit,vit+1]。
v4
T S
v2
v3
v5
4
数据、模型与决策
➢ 边：两点间不带箭头联线称为边，若两点为 vi,vj,则边记为：[vi,vj]；
➢ 弧：两点间带箭头联线称弧,若有vi指向vj的弧， 则弧记为：（vi,vj） 。
➢ 无向图定义：由点和边组成，表示G={V,E}； ➢ 有向图定义：由点和弧组成，表示D={V,A}。
6
v1
v1 v2 v3 v4 v5 v6 5
T v1 0 5 6
20
数据、模型与决策
分别用破圈法和避圈法 求图中的最小生成树
9 9
3
2
6
3
2
6
7
3
7
3
4
1
3
4
1
3
4 4
21
数据、模型与决策
(3) 矩阵求解算法
▪ 步骤1：构造一个矩阵，
wij , i, j有边相连
aij ，无边相连
v4
5
0，i j 6
v1
1
7
5
2 v2
v5
4
3
v6
4
22
v3
数据、模型与决策
v4
5
v5
v1 6
1 7
水塔 5
2
v2
4
3
v6
4
v3
17
数据、模型与决策
▪ 将图中求最小生成树的问题归结为整数规 划问题，列出数学模型。
a12
1
2
a13
a24
a34 3
4
a45
5
a36
a47
a58
a67
6
7
8
a78
18
数据、模型与决策
xij 1,[i, j]在 生 成 树 内 , 否 则 为 0
数据、模型与决策
第二节 树及最小生成树算法
▪ 什么是树？ ▪ 构造生成树的方法 ▪ 最小生成树 ▪ 寻找最小生成树的方法
10
数据、模型与决策
一、树的基本概念
▪ 树：不含圈的连通图
什么是连通图：任意两 点之间都有一条链相连。
什么是圈：起点和终点 相同的链叫做圈。
已知有五个城市，要在它们之间架设电话 线，要求任何两个城市都可以互相通话 （允许通过其它城市），并且电话线的根 数最少。
专题五 图论与网络计划模型
✓最小生成树模型
✓最短路模型 ✓最大流模型 ✓最小费用流模型 ✓网络计划与优化模型
1
数据、模型与决策
第一节 图与网络基础概念
①图 ② 子图和生成子图 ③ 网络图 ④ 链、路、圈和回路 ⑤ 连通图 ⑥ 简单图
2
数据、模型与决策
一、图
A
ቤተ መጻሕፍቲ ባይዱ
e11
e1
e4
S
e2
e9
B e6
D e12
➢如果G1是树，则称为生成树。
五个城市连通电话线问题
13
数据、模型与决策
二、构造生成树的方法
▪ 法1：破圈法：无圈的连通图，图中无圈。
v4
v5
从图中取圈，
从圈中去掉一 v1
边，重复直到
1
无圈。
2
4
v6
3
v2
起点和终点相同的链叫做圈。
v3
14
数据、模型与决策
避圈法：从图中某一点开始生长边，
选取与入树边不构成圈的边。