文档介绍：第三讲图
1
本章出题特点
在历年统考里,大多以客观题不劳形式出现,具体如下:
年份
客观
主观
2009
1(2分)
1(10分)
2010
2(4分)
2011
1(2分)
1(8分)
2012
4(8分)
2
知识点归纳
图
应用
遍历方式
存储结构
关键路径
最小生成树
广度优先
深度优先
邻接表
最短路径
拓扑排序
邻接矩阵
基本概念
了解
掌握
掌握
掌握、应用
基本概念
3
一、图的概念和相关术语
图的定义
图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。
顶点集合为空的图称为空图。
E(G)为空时,图中只有顶点而没有边。
4
图的基本术语
1. 端点和邻接点
在一个无向图中,若存在一条边(vi,vj),则称vi和vj为此边的两个端点,并称它们互为邻接点。
在一个有向图中,若存在一条边<vi,vj>,则称此边是顶点vi的一条出边,同时也是顶点vj的一条入边;称vi和vj分别为此边的起始端点(简称为起点)和终止端点(简称终点);称vi和vj互为邻接点。
1
3
0
2
4
(a)
1
3
0
2
4
(b)
5
2. 路径和路径长度
在一个图G=(V,E)中,从顶点vi到顶点vj的一条路径是一个顶点序列(vi,vi1,vi2,…,vim,vj),若此图G是无向图,则边(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)属于E(G);若此图是有向图,则<vi,vi1>,<vi1,vi2>,…,<vim-1,vim>,<vim,vj>属于E(G)。
路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外,其余顶点均不相同,则称此路径为简单路径。例如,有图中,(v0,v2,v1)就是一条简单路径,其长度为2。
2
1
0
3
6
3. 连通、连通图和连通分量
在无向图G中,若从顶点vi到顶点vj有路径,则称vi和vj是连通的。
若图G中任意两个顶点都连通,则称G为连通图,否则称为非连通图。
无向图G中的极大连通子图称为G的连通分量。显然,任何连通图的连通分量只有一个,即本身,而非连通图有多个连通分量。
1
0
2
3
1
0
2
(b)
(a)
3
“极大”的含义:指的是对子图再增加图G中的其它顶点,子图就不再连通。
7
4. 顶点的度、入度和出度
在无向图中,顶点所具有的边的数目称为该顶点的度。
在有向图中,以顶点vi为终点的入边的数目,称为该顶点的入度。以顶点vi为始点的出边的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
若一个图中有n个顶点和e条边,每个顶点的度为di(1≤i≤n),则有:
1
3
0
2
4
(a)
1
3
0
2
4
(b)
8
5. 完全图
若无向图中的每两个顶点之间都存在着一条边,有向图中的每两个顶点之间都存在着方向相反的两条边,则称此图为完全图。
显然,完全无向图包含有n(n-1)/2条边,完全有向图包含有n(n-1)条边。
例如,图(a)所示的图是一个具有4个顶点的完全无向图,共有6条边。图(b)所示的图是一个具有4个顶点的完全有向图,共有12条边。
(b)
1
0
2
3
1
0
2
3
(a)
9
6. 子图
设有两个图G=(V,E)和G’=(V’,E’),若V’是V的子集,即V’V,且E’是E的子集,即E’E,则称G’是G的子图。例如图(b)是图(a)的子图,而图(c)不是图(b)的子图。
(a)
1
3
0
2
4
1
3
0
2
4
(b)
1
3
0
2
4
(c)
10