运筹学图与网络分析

2021/3/16
13
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题
充要条件：无向图中无奇点，有向图每个顶点出次等于入次
2021/3/16
14
第二节 树
树是图论中的重要概念，所谓树就是一个无圈的连通图。
v1
v2
v3
v6
v5
v4
v7
v8
v9
(a)
v1
v2
v3
v4
v5
v6
(b)
18
例8.1
19
2、避圈算法 步骤：
（1）任找一个点S，其余各点就是 S 。
（2）在连接S与 S 的所有边中，选择权数最小的边(i, k)； （3）将最小边(i, k)的另一个端点移入S； （4）若 S 则停止，否则返回（2）。
20
例8.1
21
有向树：不考虑方向时是树
根树（外向树）：只有一个顶点入次为0，其余顶点入次为1 ◦ 根：入次为0的顶点 ◦ 叶：出次为0的顶点 ◦ 分支点 ◦ 层次：根到顶点的长度
11
路：有向图：弧的方向与链的方向一致 ◦ 开路:v1v2v4v5 ◦ 回路：第一个点和最后一个点相同。v1v2v4v5v1
12
连通图：若任何两个不同的点之间，至少存在一条链，则 G为连通图。
赋权图：对一个图的每一条边（弧）(vi,vj)，相应地有一 个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。 网络：赋权连通图 ➢无向图：开链即开路，闭链即回路 ➢有向图：弧的方向与链的方向一致。
反映对象之间的关系并不是重要的。
e2
(v1) 赵
e1 e3
e4
(v2)钱 孙(v3) 李(v4)
周(v5)
图8.2
e5 吴(v6) 陈(v7)
4
如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关 系了，这是我们引入一个带箭头的联线，称为弧。
a1
定理2 次为奇数的顶点必为偶数个。
2021/3/16
9
G (V , E), G' (V ', E' )
◦ 若 V ' V , E' E ,则G’是G的子图，G是G’的母图 G' G ◦ 若 V ' V , E' E ,则G’是G的真子图，G' G ◦ 若 V ' V , E' E ,则G’是G的支撑（生成）图。
25
一、狄氏标号法（Dijkstra算法）
16
生成（支撑）树 若 V ' V , E' E ,则G’是G的支撑（生成）树。
(a)
(b)
(c)
17
最小生成树问题就是指在一个赋权的连通的无向图G中找出一 个生成树，并使得这个生成树的所有边的权数之和为最小。
1、破圈算法 步骤： （1）在给定的赋权的连通图上任找一个圈。 （2）在所找的圈中去掉一个权数最大的边（如果有两条或两 条以上的边都是权数最大的边，则任意去掉其中一条）。 （3）如果所余下的图已不包含圈，则计算结束，所余下的图 即为最小树，否则返回第1步。
2021/3/16
6
G=(V,E) •关联边(m)：ei •端（顶）点(n)：vi, vj •点相邻(同一条边)： v1, v3 •边相邻(同一个端点)：e2, e3
环：e1 多重边： e4, e5
7
简单图：无环无多重边 多重图：多重边
完全图：每一对顶点间都有边（弧）相连的简单图
2021/3/16
(v2)钱
a7
a2
a8
(赵v1)
a14 a15 a3
(v4) 李
a4
a9
(v3)孙
a5
a6
a12
a11
(v5) 周
a10
(v6)吴 a13
(v7)陈
图8.3
5
无向图：由点和边构成的图，记作G =（V，E）。 有向图：由点和弧构成的图，记作D =（V，A）。
◦ 无向图是有向图的基础图G(D)
有限图 无限图
v8 v7
图8-4
v1
v2
v8
v3
v4
v9
v5
v7
v6
(c)
图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是 树， (c)因为不连通所以也不是树。
15
树的基本性质 1. 任意两点间有且仅有一条链 2. 不相邻两点间添加一条边，有且仅有一个圈 3. 任意去掉一条边，得不连通图. 4. 存在悬挂点 5. m=n-1
2021/3/16
22
m叉树：每个顶点的出次小于等于m 完全m叉树：每个顶点的出次等于m或0
2021/3/16
23
霍夫曼树：最优二叉树
s
m(T ) min pili i1
2021/3/16
24
第三节 最短路问题
最短路问题： 对一个赋权的有向图D中的指定的两个点Vs(起点)和Vt （终点）找到一条从 Vs 到 Vt 的路，使得这条路上所有 弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。 这条路上所有弧的权数的总和被称为从Vs到Vt的距离。
第八章 图与网络分析
图与网络的基本概念 树 最短路问题 最大流问题 最小费用最大流问题
1
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题
哈密尔顿回路：经过每点且仅一次 货郎担问题、快递送货问题
2021/3/16
2
第一节 图与网络的基本概念
图是由点和边构成，可以反映一些对象之间的关系。
10
链：点边交替序列 ◦ vi0 vik 闭链：v1 v2 v3 v4 v1 ◦ vi0 vik 开链：v1 v2 v3 边不同，简单链：v3 v4 v5v1v6v5 边不同且结点不同，初等链：v1 v2 v3 v4 v5v6 圈：闭链，且至少有3个不同结点，v2 v3 v4 v2 初等圈：初等闭链，v1 v2 v3 v4 v1
例如：在一个人群中，对相互认识这个关系我们可以用图 来表示，图8.1就是一个表示这种关系的图。
(赵v1)
e2
(v3)孙
e1
e3
(v2)钱 (v5) 周
e4 (v4) 李
e5 (v6)吴
(v7)陈
图8.1
3
描述对象之间关系， 研究特定关系之间的内在规律， 图中点的相对位置如何、点与点之间联线的长短曲直，对于
8
次（d）：结点的关联边数目
◦ d(v3)=4，偶点
◦ d(vຫໍສະໝຸດ Baidu)=3，奇点
◦ d(v1)=4 ◦ d(v4)=1，悬挂点 ◦ e6, 悬挂边 ◦ d(v5)=0，孤立点
出次：d+(vi) 入次：d-(vi)
d (vi ) d (vi )
d (vi) = d+(vi) + d-(vi)
定理1 顶点次数总和等于边数的两倍。n d(vi) 2m i 1