资源描述：
《图的定义和术语ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径1第七章图在线性结构中，数据元素之间是一对一的线性关系，除第一个数据元素和最后一个数据元素之外，每个数据元素只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间是一对多的层次和分支的关系，除根结点外，每个数据元素都只有一个直接前驱（即双亲结点），但每个数据元素都可能有多个直接后继（即孩子结点）。然而在图型结构中，数据元素之间的关系是任意的，是多对多的关系，既图中任意两个结点之间都可能相关。27.1图的定义和术语图中的数据元素通常称为顶点。图G由两个集
2、合V和E组成，通常记为G＝(V，E)其中，V是图中顶点的有穷非空集合，E是V中顶点间的边的有穷集。除此之外，也通常将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。图可分为无向图和有向图两类。37.1图的定义和术语无向图：图中的每条边都是无方向的。在无向图中，一条无向边是由两个顶点组成的无序对，通常用圆括号表示。例如（vi，vj）表示一条无向边，在无向图中，（vi，vj）和（vj，vi）是两条相同的无向边。（无向）完全图：任意两个顶点之间都有一条无向边的无向图。（无向）完全图是含有n个顶点和n(n-1)/2条边的无
3、向图。47.1图的定义和术语如下图G是一个无向图BCAFED图G可记作：G＝（V，E），其中V＝{A,B,C,D,E,F}E={(A,B),(A,E),(B,F),(B,E),(C,F),(C,D),(D,F)}若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接；同时称边(vi，vj)依附于顶点vi和vj，或称边(vi，vj)与顶点vi和vj相关联。57.1图的定义和术语有向图：图中的每条边都是有方向的。在有向图中，一条有向边是由两个顶点组成的有序对，通常用尖括号表示。例如表示一条有向边，vi是边的起始点，vj是边的终点。因此，
4、和是两条不同的有向边。有向边也称为弧，边的起始点称为弧尾，终点称为弧头。67.1图的定义和术语如下图G是一个有向图ABECF图G可记作：G＝（V，E），其中V＝{A,B,C,D,E,F}E={,,,,,,}若＜vi,vj＞是图中的一条有向边，则称顶点vj是vi的领接点，或称顶点vi邻接到vj，或顶点vj邻接自顶点vi，并称弧＜vi,vj＞依附于顶点vi和vj，或称弧＜vi,vj＞与顶点vi和vj相关联。77.1图的定义和术语有向完全图：任意两个顶点之间都有一对相向的有向边的有
5、向图。即含有n个顶点和n(n-1)条弧（有向边）的有向图。ABECF1597211132权：与图的边或弧相关的数。这些权可以表示从一个顶点到另一个顶点的距离或者耗费。网：弧（或边）带权的图称为网。87.1图的定义和术语子图：给定图G1=（V1，E1）、图G2=（V2，E2），若V1是V2的子集，E1是E2的子集，则称G1是G2的子图。例：ABECF图GAB图G1CF图G3E图G2CE图G497.1图的定义和术语无向图中顶点v的度：指的是和v相关联的边的数目，通常记为D(v)。BCAFED例：在右图中D(B)=D(F)＝3D(A)=D(C)=D(D)=D(E)=2结论无向图
6、中：顶点的度之和=边数的两倍107.1图的定义和术语有向图中顶点v的度分为入度和出度。顶点v的入度：以顶点v为终点的有向边的数目，记为ID(v)；顶点v的出度：以顶点v为起始点的有向边的数目，记为OD(v)；有向图中顶点v的度则定义为该顶点的入度和出度之和，即D(v)＝ID(v)十OD(v)。117.1图的定义和术语例：在下面的有向图中ID(A)=1；OD(A)=2;D(A)=3ID(C)=1；OD(C)=1;D(C)=3ABECF结论有向图中：顶点入度之和=顶点出度之和=弧数127.1图的定义和术语在无向图G中，若存在一个顶点序列（vp,vi1,…，vin，vq），使得
7、(vp，vil)，(vi1,vi2)，…，(vin，vq)均属于边集E(G)，则称顶点vp到vq存在一条路径。若G是有向图，则路径也是有向的，它由E(G)中的有向边＜vp，vil＞,＜vil，vi2＞,…，＜vin，vq＞组成。路径长度：该路径上边的数目。序列中顶点不重复出现的路径称为简单路径。起点和终点相同(vp＝vq)的路径称为回路。若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为简单回路或简单环。137.1图的定义和术语例如：在有向图G中：（A,B,C,F）是图G的一条路径，它是由有向边序列
