chapter5 图——基本术语.ppt

《chapter5 图——基本术语.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、能不能既不重复又不遗漏地一次相继走遍这七座桥？？哥尼斯堡七桥问题欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等

2、占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论——欧拉CADB七桥问题的图模型哥尼斯堡七桥问题欧拉回路的判定规则：1.如果奇数点多于两个，则不会实现；2.如果只有两个奇数点，可以从任一奇数点出发，最后回到另一个奇数点；3.如果没有奇数点，则无论从哪里出发，都能走通。第五章图本章的主要内容是:图的逻辑结构图的存储结构及实现图的

3、连通性最小生成树最短路径AOV网与拓扑排序AOE网与关键路径ADTGraph{数据对象V：具有相同特性的数据元素的集合。数据关系R：R=｛VR｝VR＝{

4、v,w∈V且P(v,w)，表示从v到w的一条弧v→w，并称v为弧尾，w为弧头。谓词P(v,w)定义了弧的意义或信息}基本操作P：p260-262｝ADTGraphABECD非空有限5.1图的逻辑结构图的定义在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。5.

5、1图的逻辑结构如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V1V2V3V4V5V1V2V3V4G1=(V,VR)其中V={V1,V2,V3,V4,V5}VR={,,,,,}5.1图的逻辑结构V1V2V3V4

6、V5V1V2V3V4V5G2=(V,VR)其中V={V1,V2,V3,V4,V5}VR={（V1,V2）,（V1,V4）,（V2,V3）,（V2,V5）,（V3,V4）,（V3,V5）}5.1图的逻辑结构图的基本术语简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图简单图V1V2V3V4V5数据结构中讨论的都是简单图。5.1图的逻辑结构邻接、依附无向图中，任意两顶点vi，vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同

7、时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4图的基本术语有向图中，任意两个顶点vi，vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。V1V2V3V4V1的邻接点：V2、V3V3的邻接点：V4线性结构，元素之间的关系为线性关系：前驱和后继；树结构，结点之间的关系为层次关系：双亲和孩子；图结构，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同

8、结构中逻辑关系的对比无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。图的基本术语V1V2V3V1V2V3V45.1图的逻辑结构含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？5.1图的逻辑结构含有n个顶点的无向完全图有n×(n-1)/2条边。含有n个顶点的有向完全图有n×(n-1)条边。V1V2V3V1V2V3V4稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的

9、图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。5.1图的逻辑结构图的基本术语顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。V1V2V3V4V55.1图的逻辑结构在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？有向图呢？å==niievTD12)(V1