文档介绍：、。通信网络示例如下图所示:图G是由一个顶点集V和一个边集E构成的数据结构。记为二元组形式:G=(V,E)其中:V是由顶点构成的非空有限集合,记为:V={V0,V1,V2,…Vn-1}E是由V中顶点的对偶构成的有限集合,记为:E={(V0,V2),(V3,V4),…},若E为空,则图中只有顶点而没有边。其中对偶可以表示成:(Vi,Vj)—无序的对偶称为边,即(Vi,Vj)=(Vj,Vi),其图称为无向图<Vi,Vj>—有序的对偶称为弧,即<Vi,Vj>≠<Vj,Vi>,则称Vi为弧尾,称Vj为弧头,该图称为有向图二、图的定义有向图和无向图示例:无向图G1的二元组表示:V(G1)={V1,V2,V3,V4}E(G1)={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4),(V3,V4)}有向图G3的二元组表示:V(G3)={V1,V2,V3}E(G3)={<V1,V2>,<V1,V3>,<V2,V3>,<V3,V2>}在无向图中,若存在一条边(Vi,Vj),则称Vi和Vj互为邻接点(Adjacent)在有向图中,若存在一条弧<Vi,Vj>,则称Vi为此弧的起点,称Vj为此弧的终点,称Vi邻接到Vj,Vj邻接自Vi,Vi和Vj互为邻接点。、入度和出度在无向图中,与顶点v相邻接的边数称为该顶点的度,记为D(v)。在有向图中,顶点v的度又分为入度和出度两种:以顶点v为终点(弧头)的弧的数目称为顶点v的入度,记为ID(v);以顶点v为起点(弧尾)的弧的数目称为顶点v的出度,记为OD(v);有向图顶点v的度为该顶点的入度和出度之和,即D(v)=ID(v)+OD(v)无论是有向图还是无向图,一个图的顶点数n、边(弧)数e和每个顶点的度di之间满足以下的关系式:即在有向图或无向图中:所有顶点度数之和:边数=2:、稠密图和稀疏图在图G中:若G为无向图,任意两个顶点之间都有一条边,称G为无向完全图。顶点数为n,无向完全图的边数:2=n(n1)/2若G为有向图,任意两个顶点Vi,Vj之间都有弧<Vi,Vj>、<Vj,Vi>,称G为有向完全图。如顶点数为n,有向完全图的弧数:e=Pn2=n(n1)例如,无向图G1就是4个顶点无向完全图。若一个图接近完全图,则称其为稠密图;反之,若一个图含有很少条边或弧(即e<<n2),则称其为稀疏图。=(V,E)和G′=(V′,E′)且V′是V的子集,即V′V,E′是E的子集,即E′E则称图G′为图G的子图。、回路和路径长度在无向图G中,若存在一个顶点序列(Vp,Vi1,Vi2,…,Vin,Vq),使(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)均为图G的边,则该称顶点的序列为顶点Vp到顶点Vq的路径。若G是有向图,则路径是有向的。路径长度定义为路径上的边数或者弧的数目。若一条路径中不出现重复顶点,则称此路径为简单路径。若一条路径的起点和终点相同(Vp=Vq)称为回路或环。除了起点和终点相同外,其余顶点不相同的回路,称为简单回路或简单环。