6运筹学课件 图论

运 筹 学 课 件

运 筹 帷 幄 之 中 Network Analysis

决 胜

图与网络分析

千 里 之 外

第一节 图的基本概 念与模型

无向图的基本概念定义： 是一个图 定义：称G=(N,E)是一个图，如果有 是一个 是非空有限集； (1)N是非空有限集； ) 是非空有限集 (2)E是N中元素对所组成的集合。 ) 是 中元素对所组成的集合。 中元素对所组成的集合 的元素为顶点 的元素为边 且，称N的元素为顶点，E的元素为边。 的元素为顶点， 的元素为 记号： 记号：图G=(N,E) 图G的顶点集 的顶点集简记为

G简记为

N(G)或N 或

的点集合： 图G的点集合： 例如：图(1)中的 的点集合 例如： ) N=(1,2,3,4,5)是一个无向图 ( , , , , ) 的点的集合 的边集合： 为右图 图G的边集合：E={eij}且eij={ni,nj}为右图 的边集合 且 为右 无序二元组 eij的端点：有eij={ni,nj},则称 i和nj为 的端点： 则称n eij的端点，且称eij 连接点 ni和nj 的端点，且称 环：两个端点重合为一点的边 (例如右 图中的e 图中的 11) 孤立点： 孤立点：不与任何边关联的点 (例如右 图中的n 图中的 5)

1

2

4

5

3

关联： 关联：一条边的端点称为这条边的关联 邻接： 与同一条边关联的端点称为是邻接的， 邻接 ： 与同一条边关联的端点称为是邻接的 ， 同时 如果两条边有一个公共端点， 则称这两条边是邻 如果两条边有一个公共端点 ， 接的 有限图： 有限图：点和边都是有限集合的图 空图： 空图：没有任何边的图 平凡图： 平凡图：只有一个点的图 简单图： 简单图：既没有环也没有两条边连接同一对点的图

完全图： 完全图：每一对点之间均有一条边相连的图

偶图(二分图 能分解为N 合于N 偶图 二分图): 若N(G)能分解为 1与N2合于 1∪N2=N(G), 二分图 能分解为 N1∩N2=Φ,且Ni自身的顶点互不相邻(i=1,2)则称 是偶 ∩ Φ 且 自身的顶点互不相邻( )则称G是偶 或二分图);记为G=(N1,N2,E) );记为 图(或二分图);记为 完全偶图: 完全偶图 单偶图； 单偶图； 不在同一顶点子集的任二顶点都相邻的简

子 图图 G=(N,E)的子图 G ′ = ( N ′, E ′ ) : N ′ N 和 E ′ E , 的 ’ 对 E 中任意的一条边 e ij = { n i , n j } ,都有 n i ∈ N ′ 和nj ∈ N′

的支撑(生成) 的子图， 图 G 的支撑(生成)子图 G ′ : G ′ 是 G 的子图， 且 N′ = N

通道、迹的概念 通道、定义：(通道、闭通道、开通道) 定义： 通道、闭通道、开通道) 图的顶点与边的交错序列 v0 e1v1e2 L v k 1ek v k 称为v 0 v k 通道若 ei = (v i 1 , v i ) i = 1,2,L k , 并称其长为 k , 起点是 v 0终点是 v k

起点与终点重合的通道称为闭通道。 起点与终点

重合的通道称为闭通道。 闭通道 起点与终点不重合的通道称为开通道。 起点与终点不重合的通道称为开通道。 开通道 定义： 定义：(迹、闭迹、开迹、路、圈) 闭迹、开迹、 没有重复边的通道称为迹 没有重复边的通道称为迹。 闭迹。 起点与终点重合的迹称为闭迹 起点与终点重合的迹称为闭迹。 起点与终点不重合的迹称为开迹。 起点与终点不重合的迹称为开迹。 开迹

连通性点i和j点是连通的：G中存在一条(i,j) 点是连通的： 中存在一条( 路 是连通的： G是连通的：G中任意两点都是连通的

有向图有向图G:一个有序二员组 有向图 ：一个有序二员组(N,A),记为 ， G=(N,A) G的弧集合：A={aij}且aij={ni,nj}为有序二元 的弧集合： 的弧集合 且 为有序二元 连向nj, 称 组 ，若aij={ni,nj},则称 从ni连向 ， ni称 ，则称aij从 连向 的尾， 为 的头 的头， 称为 的先辈， 称为nj的先辈 为aij的尾， nj为 aij的头，ni称为 的先辈， 的尾 nj称为 ni的后继 称为 的后继 有向图G的基本图 对于G的每条弧用一条边 的基本图： 有向图 的基本图：对于 的每条弧用一条边 代替后得到的无向图

度(次 )无向图G 无向图 V1 有向图D 有向图 V2 V1 V3 V3 V4 各顶点度数为： 各顶点度数为： d(V1)=4 d(V2)=2 各顶点度数为： 各顶点度数为： d(V1)=d+(V1)+ d-(V1)=3+0=3 d(V2)= d+(V2)+ d-(V2)=1+1=2 V5 V2 V4

d(V3)=1 d(V4)=2 d(V5)=? ?

网络有向) 的每条边( (有向)网络G:对(有向)图G的每条边(弧) 有向) 都赋予一个实数，并称为边( 的权， 都赋予一个实数，并称为边(弧)的权，则连同 它边( 上的权称为(有向)网络。 它边(弧)上的权称为(有向)网络。

第二节 树图与图的最小 部分(支撑) 部分(支撑)树

定义： 定义：(树、生成树、最小生成树) 生成树、最小生成树) 无圈连通图称为树 图的生成子图若是树， 无圈连通图称为树；图的生成子图若是树，则称为该 图的生成树 树枝总和最小的生成树叫最小生成树 生成树； 图的生成树；树枝总和最小的生成树叫最小生成树 定理1:设T是(n,m)非平凡图，则下列命题等价： 定理 ： 是 非平凡图，则下列命题等价： 非平凡图 1)T是树 是树； (1)T是树； 无圈， (2)T无圈，m=n-1; ) 无圈 ； 连通， (3)T连通，m=n-1; ) 连通 ； 无圈， (4)T无圈，任加一边有唯一圈； ) 无圈 任加一边有唯一圈； 连通， (5)T连通，任去一边不再连通； ) 连通 任去一边不再连通； 的任二顶点恰有一条路连通； (6)T的任二顶点恰有一条路连通； ) 的任二顶点恰有一条路连通

注：由以上定理知：1。树是边数最少的连通图； 由以上定

理知： 。树是边数最少的连通图； 2。连通图的极大无圈生成子图是生成树； 。连通图的极大无圈生成子图是生成树； 3。连通图的极小连通生成子图是生成树。 。连通图的极小连通生成子图是生成树。

应 用例：已知任两城市间修建直通高速公路的费用，如 已知任两城市间修建直通高速公路的费用， 何修建连通n个城市的高速公路网使总修建费用最少 个城市的高速公路网使总修建费用最少？ 何修建连通 个城市的高速公路网使总修建费用最少？

解：1。模拟图：以n个城市为顶点，以任意两城市 个城市为顶点， 。模拟图： 个城市为顶点 以任意两城市u,v 间修建高速公路的费用为边e=(u,v)的权，记为 的权， 间修建高速公路的费用为边 的权 记为w(u,v) 或w(e),得赋权完全图 ，得赋权完全图G=(N,E) 。 2。问题等价于：求G的最小生成树，即边的权之 。问题等价于： 的最小生成树， 的最小生成树 和最小的生成树； 和最小的生成树； 3。求解： 思路：用避圈法，可选择权相对最小 。求解： 思路：用避圈法， 的边作为“加边” 如此便得到最小生成树。 的边作为“加边”,如此便得到最小生成树。

Kruskal算法(避圈法) Kruskal算法(避圈法) 算法开始把边按权的大小由小到大排列起来， 第 1 步 开始把边按权的大小由小到大排列起来，即

a1 , a 2 ,..., a m置 S = φ ,i = 0, j = 1。 则停。 即为所求；否则， 第 2 步 若 | S |= i = n 1 ,则停。这时 G[ S ] = T 即为所求；否则， 转向第 3 步。 不构成回路， 第 3 步 若 G[ S U {a j }] 不构成回路，则置 e i +1 = a j , S = S U {e i + 1 } , i = i + 1 , 否则， j = j + 1 ,转向第 2 步；否则，置 j = j + 1 ,转向第 2 步。

例：用kruskal法(避圈法)求下图的最小生成树。 法 避圈法)求下图的最小生成树。

4 e4 e9 8 6 e6 1e1 v5 e2 v6 v 2 o 8e10 o e87 o 2 e3 e5 7 9 e11 3 5 e7

v o1

ov4

o v

3

破圈法：任取一个圈，从圈中去掉一条权最大的边， 破圈法：任取一个圈，从圈中去掉一条权最大的边，在 余下的图中重复此步骤。 余下的图中重复此步骤。

第三节 最短路问题

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