文档介绍：学习要点:
理解图的定义和与图相关的有向图、无向图、赋权图、连通图等术语。
理解图是一个表示复杂非线性关系的数据结构。
掌握图的邻接矩阵表示及其实现方法。
掌握图的邻接表表示及其实现方法。
了解图的紧缩邻接表表示方法。
掌握图的广度优先搜索方法。
掌握图的深度优先搜索方法。
掌握单源最短路径问题的Dijkstra算法。
掌握所有顶点对之间最短路径问题的Floyd算法。
掌握构造最小支撑树的Prim算法。
掌握构造最小支撑树的Kruskal算法。
理解图的最大匹配问题的增广路径算法。
第十二章图
11/11/2017
1
福州大学数学与计算机科学学院
第十二章图
图的定义和术语
图(Graph)——图G是由两个集合V(G)和E(G)组成记为G=(V,E)
其中:V(G)是顶点的非空有限集
E(G)是边的有限集合,边是顶点的无序对或有序对
有向图——有向图G是由两个集合V(G)和E(G)组成
其中:V(G)是顶点的非空有限集
E(G)是有向边的有限集合,弧是顶点的有序对,记为<v,w>,v,w是顶点,v为有向边的起点,w为有向边的终点
无向图——无向图G是由两个集合V(G)和E(G)组成
其中:V(G)是顶点的非空有限集
E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v)
本书约定:不考虑顶点到其自身的边;不允许一条边在图中重复出现!
11/11/2017
2
福州大学数学与计算机科学学院
例
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}
E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
11/11/2017
3
福州大学数学与计算机科学学院
完全图——设|V|=n,|E|=e。对有向图G,若e=n(n-1),则称G为完全的有向图;对无向图G,若e=n(n-1)/2,则称G为完全的无向图。
邻接、关联——若(u,v)是一条无向边,则称顶点u和v互为邻接点,或称u和v相邻接;并称边(u,v)关联于顶点u和v,或称边(u,v)与顶点u和v相关联。若(u,v)是一条有向边,则称v是u的邻接顶点;并称边(u,v)关联于顶点u和v,或称边(u,v)与顶点u和v相关联。
顶点的度
无向图中,顶点v的度为关联于该顶点相连的边数,记为D(v)
有向图中,顶点v的度分成入度与出度
入度:以顶点v为终点的边的数目,记为ID(v)
出度:以顶点v为起点的边的数目,记为OD(v)
D(v)=ID(v)+OD(v)
无论是有向图还是无向图,顶点数n,边数e和度数
之间有如下关系:
11/11/2017
4
福州大学数学与计算机科学学院
子图——如果图G(V,E)和图G’(V’,E’),满足:
V’V E’E 则称G’为G的子图
有向图G1的若干子图
无向图G2的若干子图
11/11/2017
5
福州大学数学与计算机科学学院
路径:
在无向图G中,若存在一个顶点序列u(1),u(2),…,u(m),使得(u(i),u(i+1))∈E(G),i=1,2,…,m-1,则称该顶点序列为顶点u(1)和u(m)之间的一条路径。其中u(1)称为该路径的起点,u(m)称为该路径的终点。
若图G是有向图,则路径也是有向的,其中每条边(u(i),u(i+1)),i=1,2,…,m-1均为有向边。
路径的长度:路径所包含的边数m-1称之。
简单路——若一条路径上除了起点和终点可能相同外,其余顶点均不相同,则称此路径为一条简单路径。
回路——起点和终点相同的简单路径称为简单回路或简单环或圈。
有根图——在一个有向图中,若有一个顶点v,从该顶点有路径可以到达图中其它所有顶点,则称此有向图为有根图。v称为该有根图的根。
11/11/2017
6
福州大学数学与计算机科学学院
连通——无向图G中,若从顶点V到顶点W有一条路径,则说V和W是连通的
连通图——无向图中任意两个顶点都是连通的叫连通图
连通分支——无向图的极大连通子图叫连通分支
下图有两个连通分支:
11/11/2017
7
福州大学数学与计算机科学学院
强连通图——有向图中,如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径,则称G是强连通图
强连通分支——有向图的极大强连通子图叫强连通分支