数学意义上的图包含两个要素,即顶点集V与边集E,可以形象的表示为 G=(V; E),其中顶点数(vertex)n=|V|,边数(edge/arc)e=|E|。另外,同一条边的两个顶点,彼此邻接(adjacency),同一顶点自我邻接,构成自环(self-loop)。不含自环,即为简单图(simple graph),对于非简单图(non-simple),这里暂不讨论。顶点与其所属的边,彼此关联(incidence),与同一顶点关联的边数称为(degree/valency)。形象地说,所谓邻接关系就是顶点与顶点之间的关系,而关联关系则是顶点与边之间的关系。进一步对图进行分类,若邻接顶点u和v的次序无所谓,则(u, v)为无向边(undirected edge),进而,所有边均无方向的图,即无向图(undigraph)。反之,有向图(digraph)中均为有向边(directed edge),u、v分别称作边(u, v)的(tail)、(head)。无向边、有向边并存的图,称作混合图(mixed graph)。因为有向图通用性更强,故本文主要针对有向图介绍相关结构及算法。所谓路径,也就是由一系列的顶点按照依次邻接的关系构成的一个序列,如:路径π=<V0, V1, …, Vk>,则长度|π|=k。进一步,如果路径中不含重复节点,则为简单路径,即Vi=Vj除非i=j。更特别的,如果起点和终点是重合的路径则为环路,即V0=Vk。如果在一个有向图中不包含任何的环路,则为有向无环图(DAG)。在所有的环路中,各边恰好出现1次的环路称为欧拉环路,即|π|=|E|,各顶点恰好出现1次的环路称为哈密尔顿环路,即|π|=|V|。



发表评论

电子邮件地址不会被公开。 必填项已用*标注