(17)--第5章 图-图的术语数据结构.ppt

《(17)--第5章 图-图的术语数据结构.ppt》由会员分享，可在线阅读，更多相关《(17)--第5章 图-图的术语数据结构.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6 6章章 图图图的术语6.1 6.1 案例引入案例引入案例案例6.1 6.1：六度空间理论：六度空间理论你和任何一个陌生人之你和任何一个陌生人之间所间隔的人不会超过间所间隔的人不会超过6 6个，也就是说，最多通个，也就是说，最多通过过6 6个中间人你就能够认个中间人你就能够认识任何一个陌生人。识任何一个陌生人。哥尼斯堡七桥图的定义G=(V,E)V：顶点(数据元素)的有穷非空集合；E：边的有穷集合。有向图G2无向图G1边（v1，v2）弧图的术语-完全图无向完全图无向完全图有向完全图有向完全图n(n-1)/2 条边n(n-1)条弧图的术语-邻接、依附n无向图中，对于任意两个顶点vi和顶点vj

2、，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，即vi和vj相邻接，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V4V2V3图G1图的术语-邻接、依附n有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。图G2V1V4V2V3图的术语-稀疏图、稠密图、度n稀疏图：有很少边或弧的图（enlog2n）;n稠密图：有较多边或弧的图。n顶点的度：在无向图中，顶点v的度是指依附于该顶点的边的数目，通常记为TD(v)。n顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；

3、n顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。n在有向图中,顶点的度等于该顶点的入度与出度之和。图的术语-稀疏图、稠密图、度V1V4V2V3图G1图G2V1V4V2V3=niievTD12)(evODvIDiiii=11)()(nn图的术语-权、网n权：是指对边或弧赋予的有意义的数值量。可以表示从一个顶点到另一个顶点的距离或耗费。n网：带权的图称为网。V1V4V2V321739图G3图的术语-路径n路径：p在无向图G=(V,E)中，从顶点vi到顶点vj之间的路径是一个顶点序列(vi=vk0,vk1,vk2,vkm=vj)，其中，(vkj,vkj+1)E（1

4、jm）。p若G是有向图，则路径也是有方向的，顶点序列满足E。V1V4V2V3图G1V1 到到V3的路径：的路径：V1 V3 V1 V2 V3 V1 V2 V4 V3图的术语-路径长度n路径长度：p非带权图，路径上边或弧的个数；p带权图，路径上各边或弧的权值之和；V1V4V2V3图G1V1V4V2V321739图G3图的术语-回路、简单路径、简单回路n回路(环)：第一个顶点和最后一个顶点相同的路径。n简单路径：序列中顶点不重复出现的路径。n简单回路(简单环)：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。图的术语-子图n子图：设有两个图G=（V，E）、G1=（V1，E1），若V1 V

5、，E1 E，则称 G1是G的子图。(a)(a)(b)(b)(c)(c)V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2图的术语-连通、连通图、强连通图n连通：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。n连通图：如果图中任意两个顶点都是连通的，则称该图是连通图（强连通图）。V0 V4 V3 V1 V2 V0 V1 V2 V3（a）连通图（b）强连通图图的术语-极大（小）连通子图、连通分量n极大连通子图：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。n极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。n连通分量：非连通图的极大连通子图称为连通分量。V0 V2 V3 V1 V5 V4 V0 V2 V3 V1 V5 V4图a图b图c V0 V2 V3 V1图d谢谢！谢谢！