|
|
|
图G是由两个集合V和E构成的二元组，记作G=（V，E），其中V是图中顶点的非空有限集合，E是图中边的有限集合。从数据结构的逻辑关系角度来看，图中任一顶点都有可能与图中其他顶点有关系，而图中所有顶点都有可能与某一顶点有关系。在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。
|
|
|
|
.有向图：若图中每条边都是有方向的，则称为有向图。从顶点νi到νj的有向边<vi，vj>也称为弧，起点νi称为弧尾；终点νj称为弧头。在有向图中，<νi，νj>与<νj，vi>分别表示两条弧，如下图（a）所示。
|
|
|
|
|
|
|
|
.无向图：若图中的每条边都是无方向的，顶点νi和νj之间的边用（νi，νj）表示。在无向图中，（νi，νj）与（νj，νi）表示的是同一条边。5个顶点的一个无向图如上图（b）所示。
|
|
|
|
.完全图：若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图共有n（n-1）/2条边。类似地，有n个顶点的有向完全图中弧的数目为n（n-1），即任意两个不同顶点之间都存在方向相反的两条弧。
|
|
|
|
.度、出度和入度：顶点ν的度是指关联于该顶点的边的数目，记作D（ν）。若G为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为ID（ν）和OD（ν）。例如，上图（a）中，顶点1，2，3，4的入度分别为1，2，1，1，出度分别为3，0，0，2。上图（b）中，顶点1，2，3，4，5的度分别为3，2，4，3，2。
|
|
|
|
.路径：在无向图G中，从顶点νp到顶点νq的路径是指存在一个顶点序列νp，νi1，νi2，…，νin，νq，使得（νp，νi1），（νi1，νi2），…，（νin，νq）均属于E（G）。若G是有向图，其路径也是有方向的，它由E（G）中的有向边<νp，νi1>，<νi1，νi2>，…，<νin，νq>组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了νp和νq可以相同外，其余顶点均不相同，这种路径称为一条简单路径。
|
|
|
.子图：若有两个图G=（V，E）和G'=（V'，E'），如果 且 ，则称G'为G的子图。
|
|
|
|
.连通图：在无向图G中，若从顶点νi到顶点νj有路径，则称顶点νi和顶点νj是连通的。如果无向图G中任意两个顶点都是连通的，则称其为连通图。上图（b）所示的无向图是连通图。
|
|
|
|
.强连通图：在有向图G中，如果对于每一对顶点νi，νj∈V且νi≠νj，从顶点νi到顶点νj和从顶点νj到顶点νi都存在路径，则称图G为强连通图。上图（a）所示的有向图不是强连通图。以顶点1和顶点3为例，顶点1至顶点3存在路径，而顶点3至顶点1没有路径。
|
|
|
|
|
|
从图的逻辑结构的定义来看，图中的顶点之间不存在全序关系（即无法将图中的顶点排列成一个线性序列），任何一个顶点都可被看成第一个顶点；另一方面，任一顶点的邻接点之间也不存在次序关系。为便于运算，为图中每个顶点赋予一个序号。
|
|
|
