欢迎来到天天文库
浏览记录
ID:14088867
大小:2.49 MB
页数:17页
时间:2018-07-26
《图论中的概念及重要算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、Jsoi2004-2005第一轮函授A班第2讲讲义图论中的概念及重要算法常州一中林厚从ch1、图论中的基本概念一、图的概念简单讲,一个图是由一些点和这些点之间的连线组成的。严格意义讲,图是一种数据结构,定义为:graph=(V,E),V是点(称为“顶点”)的非空有限集合,E是线(称为“边”)的集合,边一般用(vx,vy)表示,其中vx,vy属于V。图(A)共有4个顶点、5条边,表示为:V={v1,v2,v3,v4},E={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4)}二、无向图和有向图如果边是没有方向的,称此图为“无
2、向图”,如图(A)和图(C),用一对圆括号表示无向边,如图(A)中的边(v1,v2),显然(vx,vy)和(vy,vx)是两条等价的边,所以在上面E的集合中没有再出现边(v2,v1)。如果边是有方向(带箭头)的,则称此图为“有向图”,如图(B),用一对尖括号表示有向边,如图(B)中的边。把边中Vx称为起点,Vy称为终点。显然此时边与边是不同的两条边。有向图中的边又称为弧,起点称为弧头,终点称为弧尾。图(B)表示为:V={v1,v2,v3},E={,,,<
3、v3,v2>}如果两个顶点U、V之间有一条边相连,则称U、V这两个顶点是关联的。三、带权图一个图中的两顶点间不仅是关联的,而且在边上还标明了数量关系,如图(C),这种数量关系可能是距离、费用、时间、电阻等等,这些数值称为相应边的权。边上带有权的图称为带权图,也称为网(络)。四、阶图中顶点的个数称为图的阶。图(A)、图(B)、图(C)的阶分别为4、3、5。五、度图中与某个顶点相关联的边的数目,称为该顶点的度。度为奇数的顶点称为奇点,度为偶数的顶点称为偶点。图(A)中顶点v1,v2是奇点,v3,v4是偶点。在有向图中,把以顶点V为终点的边的数目称为顶点V
4、的入度,把以顶点U为起点的边的数目称为顶点U的出度,出度为0的顶点称为终端顶点。如图(B)中顶点v117Jsoi2004-2005第一轮函授A班第2讲讲义的入度是0、出度是2,v2的入度是2、出度是1,v3的入度是2、出度是1,没有终端顶点。定理1:无向图中所有顶点的度之和等于边数的2倍,有向图中的所有顶点的入度之和等于所有顶点的出度之和。定理2:任意一个无向图一定有偶数个(或0个)奇点。一、完全图若无向图中的任意两个顶点之间都存在着一条边,有向图中的任意两个顶点之间都存在着方向相反的两条边,则称此图为完全图。n阶完全有向图含有n*(n-1)条边,n
5、阶完全无向图含有n*(n-1)/2条边,当一个图接近完全图时,称为稠密图;相反,当一个图的边很少时,称为稀疏图。二、子图设有两个图G=(V,E)和G’=(V’,E’),若V’是V的子集,E’是E的子集,则称G’为G的子图。三、路(径)在一个G=(V,E)的图中,从顶点v到顶点v’的一条路径是一个顶点序列vi0,vi1,vi2,……,vim,其中vi0=v,vim=v’,若此图是无向图,则(vij-1,vij)∈E,1≤j≤m;若此图是有向图,则∈E,1≤j≤m。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单
6、路径,顶点v和顶点v’相同的路径称为回路(或环)。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路(或简单环)。九、连通图在无向图G中,如果从顶点U到顶点V有路径,则称U和V是连通的。如果对于图G中的任意两个顶点U和V都是连通的,则称图G是连通图,否则称为非连通图。在有向图G中,如果对于任意两个顶点U和V,从U到V和从V到U都存在路径,则称图G是强连通图。Ch2、图的存储结构一、邻接矩阵表示法邻接矩阵是表示顶点之间相邻关系的矩阵,设G={V,E}是一个度为n的图(顶点序号分别用1,2,……,n表示),则G的邻接矩阵是一个n阶方
7、阵,G[i,j]的值定义如下:1或权值当vi与vj之间有边或弧时,取值为1或权值G[i,j]=0或∝当vi与vj之间无边或弧时,取值为0或∝(无穷大)上面3个图对应的邻接矩阵分别如下:0111011∞58∞3G(A)=1011G(B)=001G(C)=5∞2∞6110001082∞1041100∞∞10∞1136411∞采用邻接矩阵表示图,直观方便,很容易查找图中任两个顶点i和j之间有无边(或弧),以及边上的权值,只要看A[i17Jsoi2004-2005第一轮函授A班第2讲讲义,j]的值即可,因为可以根据i,j的值随机查找存取,所以时间复杂性为O(
8、1)。也很容易计算一个顶点的度(或入度、出度)和邻接点,其时间复杂性均为O(n)。但是,邻接矩阵表示法的空间
此文档下载收益归作者所有