《图的定义和术语》PPT课件

《《图的定义和术语》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。图(Graph)是一种比线性表和树更为复杂的数据结构。图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。7.1图的定义和术语V1V3V2V4V1V2V5V4V3图7.1图的示例(a

2、)有向图G1(b)无向图G2(a)(b)7.1.1图的定义和术语顶点（Vertex)：在图中的数据元素通常称为顶点（Vertex)。约定V表示顶点的有穷非空集合，VR表示两个顶点之间的关系的集合。弧（Arc）：表示两个顶点v和w之间存在一个关系，用表示顶点v到w的一条弧。且称v为弧尾（Tail）或初始点，称w为弧头（Head）或终端点。此时的图称为有向图（Digraph）。其中，顶点偶对的v和w之间是有序的。无向图(Undigraph)：若图关系集合中，顶点偶对的v和w之间是无序的，称图G是无向图。若属于VR，必有属于V

3、R，即VR是对称的。那么用（v,w）代替这两个有序对，表示v和w的一条边（Edge）。如图7.1：设有向图G1和无向图G2，形式化定义分别是：G1=(V1，A1)V1={v1,v2,v3,v4}A1={,,,}G2=(V2，E2)V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v1),(v3,v5)}V1V3V2V4V1V2V5V4V3图7.1图的示例(a)有向图G1(b)无向图G2(a)(b)完全无向图：对于无向图，若图中顶点数为n，用e表示边

4、的数目，则e[0，n(n-1)/2]。具有n(n-1)/2条边的无向图称为完全无向图。完全无向图另外的定义是：对于无向图G=(V，E)，若vi，vjV，当vi≠vj时，有(vi,vj)E，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。完全有向图：对于有向图，若图中顶点数为n，用e表示弧的数目，则e[0，n(n-1)]。具有n(n-1)条边的有向图称为完全有向图。完全有向图另外的定义是：对于有向图G=(V，E)，若vi，vjV，当vi≠vj时，有E并且E，即图中任意两个不同的顶点间都有一条弧，这样的有向

5、图称为完全有向图。有很少边或弧的图（e

6、ee)，记为TD(v)。例如无向图G2。TD(V1)，TD(V2)，TD(V3)，TD(V4)，TD(V5)V1V2V5V4V3G2对于有向图G=(V，E)，若有向弧E，则称顶点v“邻接到”顶点w，顶点w“邻接自”顶点v，弧与顶点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)+

7、ID(v)例如图7.1所示的无向图。OD(v1)，ID(,1)，TD(v1)；OD(v3)，ID(,3)，TD(v1)V1V3V2V4(G1)一般地，如果顶点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。路径的长度：路径上边或有向边(弧)的数目称为该路径的长度。在一条