图的基本概念和术语

图G=V,E

V:顶点数据元素的又穷非空集合

E:边的有穷集合。

无向图每条边都是无方向的G2

有向图 每条边都是有方向的G1

完全图任意两个点都有一条边相连

假设有n个顶点

无向完全图中有n*n-1/2条边{Cn2}

有向完全图中有n*(n-1)条边2*Cn2

稀疏图有很少的边或弧x<nlognx为边的数目n为顶点的数目 。

稠密图有较多的边或弧的图。

网边/弧带权的图

邻接有边/弧相连的两个顶点之间的关系

存在vivj则成vi和vj互为邻接点无向图用

存在<vi,vj>则称vi邻接到vjvj邻接于vi有向图用<>有先后关系有序的

关联依附边/弧于=与顶点之间的关系

存在<vi,vj>/(vivj)则称该边/弧关联与vi和vj

顶点的度与该顶点相关联的边的数目记为TDv

在有向图中顶点的度等于该顶点的入度与出度之和。

顶点v的入度是以v为终点的有向边的条数基座IDv

顶点v的出度是以v为始点的有向边的条数记作ODv

TD=ID+OD

 例子引入

 路径接续的边构成的顶点序列。若干条相连的边构成的路径

路径的长度路径上边或弧的数目/权值之和。

eg不带权的路径

带权的路径

 

 回路环第一个顶点和最后一个顶点相同的路径。

简单路径除起点和终点可以相同外其余顶点均不相同的路径。

简单回路除路径的起点和终点相同其余顶点均不相同的路径。

  

 

权与网

 

 子图

连通分量

 将非连通图可分成多个连通分量连通分量都为极大连通子图

强连通分量 

 有向图的极大连通子图

 

极小连通子图 该子图是G的连通子图在该子图中删除任何一条边子图不再连通

生成树包含无向图G所有顶点的极小连通子图。

生成森林对非连通图由各个连通分量的生成树的集合。