文档介绍：第7章图
图的定义和术语
1、图、顶点、边
图G是由集合V(G)和E(G)组成,记为G=(V,E),其中V(G)是顶点的非空有限集合,E(G)是边的有限集合,边是点的无序对或有序对。
2、有向图、弧、无向图
2
4
5
1
3
6
G1
若图中的边是顶点的有序对,则称此图为有向图。
有向边又称为弧,通常用尖括号表示一条有向边,<v,w>表示从顶点v到w顶点的一条弧,v称为边的始点(或弧尾),w称为边的终点(或弧头)。
例
2
4
5
1
3
6
G1
图G1中: V(G1)={1,2,3,4,5,6}
E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}
例
1
5
7
3
2
4
G2
6
图G2中: V(G2)={1,2,3,4,5,6,7}
无向图若图中的边是顶点的无序对,则称此图为无向图。通常用园括号表示无向边。(v,w)或(w,v),并且(v,w)=(w,v)
图的定义和术语
E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
3、有向完全图、无向完全图
4、相邻顶点、相关联弧或边
无向完全图:n个顶点的无向图最大边数是n(n-1)/2,具有n(n-1)/2条边的无向图称为无向完全图。
2
1
3
有向完全图
2
1
3
无向完全图
图的定义和术语
若<V1,V2> E或(V1,V2) E ,则V1,V2是相邻顶点,弧<V1,V2>或边(V1,V2)是与顶点V1和V2相关联弧或边。
有向完全图:具有n(n-1)条弧的有向图称为有向完全图。
5、度
例1
2
4
5
1
3
6
G1
顶点2入度:1 出度:3
顶点4入度:1 出度:0
例2
1
5
7
3
2
4
G2
6
顶点5的度:3
顶点2的度:4
图的定义和术语
一个顶点V的度是与该顶点相关联的边的数目,记为TD(V)。
对于有向图,则把以顶点V为弧尾的数目称为点V的出度,记为OD(V),把以顶点V为头的弧的数目称为顶点V的入度,记为ID(V)。顶点V的度为:
TD(V)=ID(V)+OD(V)
6、子图
设有两个图 G=(V, E) 和 G‘=(V’, E‘)。若 V’ V 且 E‘E, 则称图G’是图G 的子图。
图的定义和术语
7、路径
若一条路径上除了vi 和vj 可以相同外, 其余顶点均不相同,则称此路径为一条简单路径。
图的定义和术语
在无向图 G=(V, E) 中, 若存在一个顶点序列 vp1, vp2, …, vpm,使得(vi, vp1)、(vp1, vp2)、...、(vpm, vj)均属于E,则称顶点vi到vj存在一条路径。路径长度定义为路径上边或弧的数目。
起点和终点相同的路径称为简单回路或简单环。
例2
1
5
7
3
2
4
G2
6
例1
2
4
5
1
3
6
G1
路径:1,2,3,5,6,3
路径:1,2,5,7,6,5,2,3
图的定义和术语
路径长度:5
简单路径:1,2,3,5
回路:1,2,3,5,6,3,1
简单回路:3,5,6,3
路径长度:7
简单路径:1,2,5,7,6
回路:1,2,5,7,6,5,2,1
简单回路:1,2,3,1
8、图的连通在无向图G中,若两个顶点vi和vj之间有路径存在,则称vi 和vj 是连通的。若G中任意两个顶点都是连通的,则称G为连通图。
连通图
例
2
4
5
1
3
6
强连通图
3
5
6
例
例
2
4
5
1
3
6
非连通图,连通分量
9、强连通图与强连通分量在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。
图的定义和术语
非连通图的极大连通子图叫做连通分量。
10、带权图或网
1
2
3
5
6
8
7
4
10
7
9
6
6
7
12
3
15
16
A
B
D
C
E
60
30
45
35
80
40
75
若给图中每一条边附加一个实数作为权,则该图称为带权图或网。
图的定义和术语
这些权可以表示从一个顶点到另一个顶点的距离或花费的代价。
一、图的数组(邻接矩阵)存储表示
图的存储结构
二、图的邻接表存储表示
三、有向图的十