图论中的概念及重要算法

《图论中的概念及重要算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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）。但是，邻接矩阵表示法的空间