[清华大学-数据结构-王红梅]第6章-专题1-图的逻辑结构幻灯片.ppt

专题1:图的逻辑结构
1
2
3
图的定义
图的基本术语
图的抽象数据类型定义
4
图的遍历操作
欧拉1707年出生在瑞士的巴塞尔城,19岁开始发表论文,直到76岁。几乎每一个数学领域都可以看到欧拉的名字,从初等几何的欧拉线,多面体的欧拉定理,立体解析几何的欧拉变换公式,四次方程的欧拉解法到数论中的欧拉函数,微分方程的欧拉方程,级数论的欧拉常数,变分学的欧拉方程,复变函数的欧拉公式等等。据统计他一生共写下了886本书籍和论文,其中分析、代数、数论占40%,几何占18%,物理和力学占28%,天文学占11%,弹道学、航海学、建筑学等占3%。欧拉对著名的哥尼斯堡七桥问题的解答开创了图论的研究。
图论——欧拉
能否从某个地方出发,穿过所有的桥仅一次后再回到出发点?
哥尼斯堡七桥问题
C
A
D
B
七桥问题的图模型
哥尼斯堡七桥问题
欧拉回路的判定规则:
1. 如果通奇数桥的地方多于两个,则不存在欧拉回路;
2. 如果没有一个地方是通奇数桥的,则无论从哪里出发,都能找到欧拉回路。
图的定义
图的逻辑结构
图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:
G=(V,E)
其中:G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。
在线性表中,元素个数可以为零,称为空表;
在树中,结点个数可以为零,称为空树;
在图中,顶点个数不能为零,但可以没有边。
图的逻辑结构
如果图的任意两个顶点之间的边都是无向边,则称该图为无向图。
若顶点vi和vj之间的边没有方向,则称这条边为无向边,表示为(vi,vj)。
若从顶点vi到vj的边有方向,则称这条边为有向边,表示为<vi,vj>。
如果图的任意两个顶点之间的边都是有向边,则称该图为有向图。
V0
V1
V2
V3
V4
V0
V1
V2
V3
图的逻辑结构
图的基本术语
邻接、依附
无向图中,对于任意两个顶点vi和顶点vj,若存在边(vi,vj),则称顶点vi和顶点vj互为邻接点,同时称边(vi,vj)依附于顶点vi和顶点vj。
V0的邻接点: V1 、V3
V1的邻接点: V0 、V2 、V4
V0
V1
V2
V3
V4
图的逻辑结构
图的基本术语
邻接、依附
有向图中,对于任意两个顶点vi和顶点vj,若存在弧<vi,vj>,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi,同时称弧<vi,vj>依附于顶点vi和顶点vj 。
V0
V1
V2
V3
V0的邻接点: V1 、V2
V2的邻接点: V3
在线性结构中,数据元素之间仅具有线性关系;
在树结构中,结点之间具有层次关系;
在图结构中,任意两个顶点之间都可能有关系。
F
E
C
B
A
D
线性结构
A
B
C
D
E
F
树结构
不同结构中逻辑关系的对比
V0
V1
V2
V3
V4
图结构