道路 (图论)
维基百科,自由的 encyclopedia
在图论中,一个图中一条道路(path)是一个顶点序列,使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的,但有限道路有一个最先顶点,称为起点,和最后顶点,称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。
道路与圈是图论中的基本概念,在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (1985) 或 Diestel (2005)、Korte et al. (1990) 包含了图中关于道路的更高等算法论题。