圈：起点和终点重合的链
Hale Waihona Puke 连通图：图的每一对顶点之间至少存在一条链
完全图：任两点之间均有边相连的简单图
Cn2 =n(n-1)/2
n个端点的完全图，多少条边？
子图：图G1={V1,E1}，G2={V2,E2}，若V1 V2 ，
E1 E2 ，称G1为G2的子图
部分图：图G1={V1,E1}，G2={V2,E2}，若
分树中
2-3避圈法和破圈法
A 2
5 C B 1 3 4
2 S 4
7 5 D 5 7 T
1 E
2 S 4
A 2
5 C B 1 3 4
7 5 D 5 7 T
1 E
§3最短路问题
3-1Dijkstra算法
基本思路：
V5
V4
V1
V2
V3
步骤：
1. 从s点出发，标号0
2. 找到与s点相邻的所有点中距离最小的一个，设为 r，标号为Lsr=dsr的值 3. 从已标号的点出发，找出与这些点相邻的所有未 标号点p，若有Lsp=min{dsp ，Lsr+drp}，对p标号
V1=V2 ，E1 E2 ，称G1为G2的部分图
部分图
子图
§2树和图的最小部分树 2-1树的概念与性质 例
山东建筑大学 管理学院 土木学院
土管 工业工程 …
…
教务处
…
定义 连通且无圈的图称为树
性质1 任何树中必存在次为1的点
性质2 具有n个顶点的树的边数恰好为(n-1)
性质3 任何具有n个顶点、(n-1)条边的连通
V7 （乙地） 17 v2 15
（甲地）
6 3
5
v4
4 2 v5
6
V1
10
v3
4
v6
(22)
V7 （乙地）
v2
15
（甲地）
(13)
6 3 v4
17 5 6
V1
(18)
4
(0)
2
v5
10
4
v6
(16)
v3
(10)
(14)
P171
6.7(b)
V2 (9) 1 2 5 8 V3 (8) V5(10) 3 4 10 V6 (14) Vt (13)
4. 重复3，直到t点得到标号
V2 (5)
7 2 7
V5 (7) 3 1 6 V6 (6) V7 (10)
(0) 5 V1
2 V3 (2)
V4 6
(7) 4 2
例 电信公司准备在甲、乙两地沿路架设一条光缆
线，问如何架设使其光缆线路最短？下图给出了 甲乙两地间的交通图。权数表示两地间公路的长 度（单位：公里）。
图是树
性质4树是最脆弱的连通图
2-2图的最小部分树 部分树：如果G1是G2的部分图，又是树 树枝：图的各边（权重） 最小部分树：树枝总长最小的部分树
定理1 图中任一点i，若j是与i相邻点中距
离最近的，则边(i,j)必含在该图的最小部
分树中
推论 把图的所有点分成V和W两个集合，则 两个集合之间连线的最短边必包含在最小部
e1 =(v1,v1)
环:两个端点重合的边
多重边：两点之间多于一条边
简单图：无环无多重边的图
链：点边序列u=(v1, e1 , v2, e2 , …, en-1,vn),其
中e1, e2 , …, en互不相同，ei =(vi,vi+1）
u=(v4, e7 , v3, e4 , v2)
u=(v4, e7 , v3, e4 , v2, e6,v4)
(0) 9 V1
8
V4 7
(11) 3 7
§4网络的最大流
4-1网络最大流的有关概念
1、有向图和容量网络 有向图：D(V,A)
A是弧的集合aij=(vi，vj)
容量网络:网络上的每条弧都给出一个最大通行
能力，称为该弧的容量，记为cij=c(vi，vj)
容量网络中的点：
• 发点s
• 收点t
• 中间点
2、流和可行流
流：网络各条弧上的负载量，记为fij=f(vi，vj)
可行流：
• 容量限制0≤fij ≤cij • 中间点平衡∑fai = ∑fja
一定存在可行流 吗？
v(f)=∑fsj = ∑fjt
网络最大流
第六章 图与网络
图的基本概念 树和图的最小部分树 最短路问题 网络最大流
§1图的基本概念 定义 图G={V,E} 其中V是点的集合，E是边的集合
区别： • 几何图形 • 图G
e1 v1 e2 v2 e6 v4 v6 e4 e5 e7 e3 v3 e8 v5
e2=(v1,v2)或e2=(v2, v1)