文档介绍：由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。
A
B E
C D
例如:
G1 = (V1, VR1)
其中
V1={A, B, C, D, E}
VR1={<A,B>, <A,E>,
<B,C>, <C,D>, <D,B>,
<D,A>, <E,C> }
第1页/共99页
若<v, w>VR 必有<w, v>VR,
则称 (v,w) 为顶点v 和顶点 w 之间存在一条边。
B C
A D
F E
由顶点集和边集构成的图称作无向图。
例如: G2=(V2,VR2)
V2={A, B, C, D, E, F}
VR2={(A,B), (A,E),
(B,E), (C,D), (D,F),
(B,F), (C,F) }
第2页/共99页
名词和术语
网、子图
完全图、稀疏图、稠密图
邻接点、度、入度、出度
路径、路径长度、简单路径、简单回路
连通图、连通分量、
强连通图、强连通分量
生成树、生成森林
第3页/共99页
A
B
E
C
F
A
E
A
B
B
C
设图G=(V,{VR}) 和图 G=(V,{VR}),
且 VV, VRVR,
则称 G 为 G 的子图。
15
9
7
21
11
3
2
弧或边带权的图分别称作有向网或无向网。
第4页/共99页
假设图中有 n 个顶点，e 条边，则
含有 e=n(n-1)/2 条边的无向图称作完全图；
含有 e=n(n-1) 条弧的有向图称作 有向完全图；
若边或弧的个数 e<nlogn，则称作稀疏图，否则称作稠密图。
第5页/共99页
假若顶点v 和顶点w 之间存在一条边，
则称顶点v 和w 互为邻接点，
A
C
D
F
E
例如:
ID(B) = 3
ID(A) = 2
边(v,w) 和顶点v 和w 相关联。
和顶点v 关联的边的数目定义为顶点v的度。
B
第6页/共99页
顶点的出度: 以顶点v
为弧尾的弧的数目；
A
B
E
C
F
对有向图来说，
顶点的入度: 以顶点v为弧头的弧的数目。
顶点的度(TD)=
出度(OD)+入度(ID)
例如:
ID(B) = 2
OD(B) = 1
TD(B) = 3
第7页/共99页
设图G=(V,{VR})中的一个顶点序列
{ u=vi,0,vi,1, …, vi,m=w}中，(vi,j-1,vi,j)VR 1≤j≤m,
则称从顶点u 到顶点w 之间存在一条路径。
路径上边的数目称作路径长度。
A
B
E
C
F
如:长度为3的路径{A,B,C,F}
简单路径:序列中顶点不重复出现的路径。
简单回路:序列中第一个顶点和最后一个顶点相同的路径。
第8页/共99页
若图G中任意两个顶点之间都有路径相通，则称此图为连通图；
若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。
B
A
C
D
F
E
B
A
C
D
F
E
第9页/共99页
若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。
A
B
E
C
F
A
B
E
C
F
对有向图，
否则，其各个强连通子图称作它的强连通分量。
第10页/共99页