图的总复习

一、图的定义Graph

图是由顶点vertex集合及顶点间关系集合组成的一种数据结构：

顶点的集合  和 边的集合

二、无向图

用（x,y）表示两个顶点x和y之间的一条边（edge）

边是无方向的

N={V，E}，V={0,1,2,3，4，5}   E={（0，1）......}

无向图有

一个有n个顶点的无向图最多有：

（n-1）n/2条边

如果一个无向图有（n-1）n/2条边

则称之为无向完全图。

邻接点：如果（x,y）属于E，称x和y互为邻接点，或x和y相邻接。

依附：边（x，y）依附于顶点x，y

相关联：边（x,y）与顶点x，y

顶点的度：与顶点x相关联的变的个数，记为TD（x）

三、有向图（Digragh）

用<x,y>表示从顶点x到顶点y之间的一条弧Arc

x为弧尾，y为弧头

四、网Network

网：带权的图被称为网

权：与弧或者边相关的数

五、

路径：是一个从顶点x到顶点y的序列

六、

回路

回路或环：路径的开始顶点与最后一个顶点相同

简单路径：在路径的顶点序列中，顶点不重复出现

七、连通

连通：如果顶点x到y有路径，称x和y是连通的

连通图：图中所有顶点都是连通的

八、子图

九、生成树

连通图的生成树是该图的一个极小连通子图。

设连通图有n个顶点，生成树也包含这n个顶点。

生成树有多少条边？n-1条

一、图的顺序存储结构