第七章图的定义和术语1.pptVIP

第7章 图 线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。 树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。 图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 7.1 图的定义和术语 7.1.1 图的定义和术语 顶点（Vertex) ：在图中的数据元素通常称为顶点（Vertex)。约定V表示顶点的有穷非空集合，VR表示两个顶点之间的关系的集合。 弧（Arc） ：表示两个顶点v和w之间存在一个关系，用v,w表示顶点v到w的一条弧。且称v为弧尾（Tail）或初始点，称w为弧头（Head）或终端点。此时的图称为有向图（Digraph）。 其中，顶点偶对v,w的v和w之间是有序的。 无向图(Undigraph)： 若图关系集合中，顶点偶对v,w的v和w之间是无序的，称图G是无向图。 若v,w属于VR，必有w, v 属于VR，即VR是对称的。 那么用（v,w）代替这两个有序对，表示v和w的一条边（Edge）。 如图7.1：设有向图G1和无向图G2，形式化定义分别是： G1=(V1 ，A1) V1={v1,v2,v3,v4} A1={v1,v2,v1,v3, v3,v4,v4,v1} G2=(V2 ，E2) V2={v1,v2,v3,v4,v5} E2={(v1,v2), (v1,v4), (v2,v3), (v2,v5), (v3,v1), (v3,v5)} 完全有向图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则e?[0，n(n-1)] 。具有n(n-1)条边的有向图称为完全有向图。 完全有向图另外的定义是： 对于有向图G=(V，E)，若?vi，vj?V ，当vi ≠vj时，有vi ,vj?E并且vj , vi ?E ，即图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。 有很少边或弧的图（en㏒n）的图称为稀疏图，反之称为稠密图。 权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图称为网。 子图和生成子图：设有图G=(V，E)和G’=(V’，E’)，若V’?V且E’?E ，则称图G’是G的子图；若V’=V且E’?E，则称图G’是G的一个生成子图。P7.2 对于无向图G=(V，E)，若边(v,w)?E，则称顶点v和w 互为邻接点，即v和w相邻接。边(v,w)依附(incident)于顶点v和w，或者说(v,w)和顶点v和w相关联。 图G中和v相关联的边的数目称为顶点v的度(degree)，记为TD(v)。例如无向图G2。TD(V1)， TD(V2)，TD(V3)， TD(V4)， TD(V5) 对于有向图G=(V ，E)，若有向弧v,w?E，则称顶点v “邻接到”顶点w，顶点w “邻接自”顶点v ，弧v,w 与顶点v和w “相关联” 。 对有向图G=(V，E)，若?vi ?V ，图G中以顶点v作为尾或初始的有向边(弧)的数目称为顶点v的出度(Outdegree)，记为OD(v) ；以v作为头或终点的有向边(弧)的数目称为顶点v的入度(Indegree)，记为ID(v) 。顶点v的出度与入度之和称为v的度，记为TD(v) 。即 TD(v)=OD(v)+ID(v) 例如图7.1所示的无向图。 OD(v1)，ID(,1)，TD(v1)；OD(v3)，ID(,3) ，TD(v1) 一般地，如果顶点vi在的度记为TD(vi)，那么一个有n个顶点，e条边或弧的图，满足： ∑TD(vi)=2e 路径(Path) ：对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。 对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。 路径的长度：路径上边或有向边(弧)的数目称为该路径的长度。 在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。 连通图、图的连通分量：对无向图G=(V，E)，若?vi ，vj ?V， 又称顶点vi到vj有路径 ，即vi和vj是连通的，