图的基本知识

单击此处编辑母版标题样式,单击此处编辑母版副标题样式,图的基本知识,一、图的概念,二、图的表示法,三、图的相关概念,四、图的基本定理,五、图的计算机存储表示,柯尼斯堡七桥问题，能否从,A,地发出，各座桥恰好通过一次，最后回到出发地,A,。,1736,年，数学家欧拉首先解决了这个问题，由此开创了图论研究。这事实上是欧拉图的“一笔画问题” 。,答案是否定的,，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条出路，与每一个顶点相邻的线（关联边）必须是偶数条（除起点和终点），而此图中不是所有点都有偶数条关联边。,v,1,v,2,v,4,v,3,v,4,v,5,v,3,v,2,v,1,有向图,G1,无向图,G2,顶点,弧,出度，入度,顶点,边,度,图,是由顶点,(vertex),集合及顶点间的关系集合组成的一种数据结构：,Graph,(,V,E,),其中,V,= ,x,|,x,某个数据对象,是顶点的有穷非空集合；,E,= |,x,y,V,是顶点之间关系的有穷集合，也叫,做边,(edge),的集合,。,图又可以分为,有向图,和,无向图,一、图的概念,二、图的表示法,v,1,v,2,v,4,v,3,v,4,v,5,v,3,v,2,v,1,有向图,G1,无向图,G2,顶点,弧,出度，入度,顶点,边,度,G1=(V,E),V=v1,v2,v3,v4,E=,G2=(V,E),V=v1,v2,v3,v4,v5,E=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v4,v5),三、图的相关概念,图的阶：,图中结点的个数。,结点的度：,图中与结点,A,关联的边的数目，称为结点,A,的度。,入度：,在有向图中，把以结点,V,为终点的边的数目称为,V,的入度；,出度：,在有向图中，把以结点,U,为起点的边的数目称为,U,的出度；,奇点：,度数为奇数的结点；,偶点：,度数为偶数的结点；,终端结点：,在有向图中，出度为,0,的结点；,四、图的基本定理,定理,1,：图中所有结点的度数之和等于边数的,2,倍；,定理,2,：任意一个图一定有偶数个奇点；,连通,：如果图中结点,U,，,V,之间存在一条从,U,通过若干条边、点到达,V,的通路，则称,U,、,V,是连通的。,路,(,径）,：从一个结点出发，沿着某些边连续地移动而到达另一个指定的结点，这种依次由结点和边组成的序列，叫“路”或者“路径” 。,路径长度,：路径上边的数目。,简单路径,：在一个路径上，各个结点都不相同，则称为简单路径。,回路,：起点和终点相同的路径，称为回路，或“环” 。,连通图,：对于图,G,中的任一对不同顶点,U,、,V,，都有一条（,U,，,V,）通路，则称图,G,是连通的。,强连通图,：在有向图,G,中，每一对结点之间都有路径的图。,网络,：带权的连通图。,五、图的计算机存储表示,1,、邻接矩阵表示法（顺序存储）,1,或权值,当,vi,与,vj,之间有边或弧时，取值为,1,或权值,0,或,当,vi,与,vj,之间无边或弧时，取值为,0,或（无穷大）,邻接矩阵是表示顶点之间相邻关系的矩阵，设,G=V,，,E,是一个度为,n,的图（顶点序号分别用,1,2,n,表示），则,G,的邻接矩阵是一个,n,阶方阵，,Gi,j,的值定义如下：,上面三个图的邻接矩阵见下图：,无向图的邻接矩阵是对称的，有向图的是不对称的。,采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点,i,和,j,之间有无边（或弧），以及边上的权值，只要看,Ai,j,的值即可，因为可以根据,i,j,的值随机查找存取，所以时间复杂性为,O,（,1,）。也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂性均为,O,（,n,）。,但是，邻接矩阵表示法的空间复杂性为,O,（,n*n,），如果用来表示稀疏图，则会造成很大的空间浪费。,2,、邻接表表示法（链式存储）,3,、边集数组表示法,边集数组是利用一维数组存储图中所有边的一种图的表示方法。每个数组元素存储一条边的起点、终点和权值（如果有的话）。在边集数组中查找一条边或一个顶点的度都需要扫描整个数组。,所以其时间复杂性为,O,（,e,），,e,为边数。,这种表示方法适合那些对边依次进行处理的运算,，而不适合对顶点的运算和对任意一条边的运算。,从空间复杂性上讲，边集数组适合于存储稀疏图。,program xy;,type edge=record,tfrom,tend,da:integer;,/,起点、终点、权值,end;,var a:array1.100 of edge;,