第三章 图与遍历算法.pdf

文档介绍：第三章图与遍历算法

§1 图的基本概念和术语

无向图(undirected graph)








哥尼斯堡七桥






Euler 图

无向图,简称图,是一个用线(边)连接在一起的节点(顶点)的集合。严
格地说,图是一个三元组 G=( V, E, I ), 其中,V 是顶点的集合,E 是边的集
合,而 I 是关联关系,它指明了 E 中的每条边与 V 中的每个顶点之间的关联关
系:每条边必定连接两个而且只有两个顶点,它们称为该边的端点。连接顶点 v
的边的条数称为 v 的度,记做 d(v). 图 G=( V, E, I )中顶点的度与边数有如下
关系
∑ d(v) = 2 | E | ()
v∈V
由公式(1)可知,图中奇度顶点的个数一定是偶数。
没有重边的图称为简单图,n 阶完全图是指具有 n 个顶点而且每两个顶点之
间都有边连接的简单图,这样的图的边数为 n(n-1)/ 1-4 阶的完全图:
K2
K4
K1 K3

另一类特殊的图是偶图(也叫二分图),它的顶点集分成两部分 V1,V2,同
一部分的顶点之间不相连(没有边连接)。

V1



V2
一个偶图

设图 G 的顶点集是 V={v1, v2, …,vn},边集是 E={e1, e2, …,em},则顶点
与顶点之间的邻接关系、顶点与边之间的邻接关系可以列表如下:

v1 v2 … vn
v1 a11 a12 … a1n 邻接矩阵
v2 a21 a22 … a2n A=(aij)n×n
。。。…。
。。。…。
。。。…。
vn an1 an2 … ann

1 if vi and v j are adjacent
其中 aij = 
0 otherwise

e1 e2 … em
v1 c11 c12 … c1m 关联矩阵
v2 c21 c22 … c2m M=(cij)n×m
。。。…。
。。。…。
。。。…。
2 … cnm
1 if vi is one of the end points of e j
其中cij = 
0 otherwise

1 4
图 3-1-1
e4
一个具有 7
e1 e3
5 5 个顶点的图
e 5 e 6
2
3
e2
e 7
6 7

图 3-1 的邻接矩阵为 A ,关联矩阵是 M :
0 1 1 0 0 0 01 0 1 0 0 0 0
1 0 0 0 0 0 01 1 0 0 0 0 0
1 0 0 0 0 0 00 1 1 0 0 0 0

A = 0 0 0 0 1 0 0 M = 0 0 0 1 0 0 0
0 0 0 1 0 1 10 0 0 1 1 1 0
0 0 0 0 1 0 10 0 0 0 1 0 1

0 0 0 0 1 1 00 0 0 0 0 1 1

图的另一个重要概念是路径,途径、迹、路。
途径:顶点与边交叉出现的序列
v0 e1 v1 e 2 v2 ··· el vl ()
其中 ei 的端点是 vi-1 和vi 。迹是指边不重复的途径,而顶点不重复的途径称为
路。路是要求最严的。

V1 V2
e1
一条途径:
v1e1v2e10v4e5v3e9v1e1v2e2v8
e9 V3 e5 V4 e10
e 2 一条迹:
e8 e6
e 4 v e v e v e v e v e v
V 1 1 2 10 4 5 3 9 1 4 7
5 V6
e 7 一条路:
e12 e11
v1e1v2e10v4e5v3e8v5e12v7
V7 e3 V8

图 3-1-2 立方体 H
起点和终点重合的途径称为闭途径,起点和终点重合的迹称为闭迹,顶点不
重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以 u 为起点、v 为终点
的途径,则说顶点 u 可达顶点 v。如果图 G 中任何两个顶点之间都是可达的,则
说图 G 是连通。如果图 G 不是连通的,则其必能分成几个连通分支。图 3-2 是连
通的,而图 3-1 不是连通的,它有两个连通分支。
不含圈的连通图称为树,