图的定义和术语

2014/11/14 posted in  算法&数据结构

终于看到和图论有关的东西了,这次只是整理《数据结构》的图的知识,等C++过完,看《图论算法理论实现及应用》,再详细深入图论吧。 图是一种较线性表和树更为复杂的数据结构。不同线性表一对一的关系,图表示的多对多的关系。

术语

在图中的数据元素通常称作顶点

VR是两个顶点之间的关系的集合。若属于VR,则表示从v到w的一条弧,且称v为弧尾或初始点,称w为弧头或终端点,此时的图称为有向图,若属于VR必有属于VR,即VR是对称的,则以无序对(v,w)代替这两个有序对,表示v和w之间的一条边,此时的图称为无向图。

属于VR,则vi!=vj,那么,对于无向图,e的取值范围是0到(n(n-1))/2。有(n(n-1))/2条边的无向图成为完全图。

对于有向图,e的取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。

又很少条边或弧的图成为稀疏图,反之称为稠密图。

有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权。这种带权的图通常称为网。

假设有两个图G=(V,{E})和G'=(V',{E'}),如果V'属于V且E'属于E,则称G'为G 的子图。

对于无向图G=(V,{E}),如果边(v,v')属于E,则称顶点v和v'互为邻接点,即v和v'相邻接。边(v,v')依附于顶点v和v',或者说(v,v')与顶点v和v'相关联。

顶点v的度和v相关联的边的数目记为TD(V)。对于有向图G=(V,{A}),如果弧(v,v')属于A,则称顶点v邻接到顶点为v',顶点v'邻接自顶点v。弧和顶点v,v'相关联。以顶点v为头的弧的数目称为v的入度,记为ID(v);以v为尾的弧的数目称为v的出度,记为OD(v);顶点的度为TD(v)=ID(v)+OD(v)。第一个顶点和最后一个顶点相同的路经称为回路或环。

序列中顶点不重复出现的路经称为简单路经。

除了第一个顶点和最后一个顶点之外,其余顶点之外,其余顶点不重复出现的回路称为简单回路或简单环。

在无向图G中,如果从顶点v到顶点v'有路径,则称v和v'是连通的。

对于图中任意两点是连通的,则称图为连通图。

连通分量指的是无向图中的极大连通子图。

在有向图G中,如果对于每一对vi,vj属于V,vi!=vj,从vi到vj和vj到vi都存在路经,则称为强连通图。

有向图的极大强连通子图称作有向图的强连通分量。

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

一棵有向图的生成森林有若干棵有向树组成。