道路 (图论)

在图论中，一个图中一条道路（path）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。

一个有向圈。去掉箭头，它就是一个圈。这不是一个简单圈，因为蓝顶点用了两次。

道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (1985) 或 Diestel (2005)、Korte et al. (1990) 包含了图中关于道路的更高等算法论题。

不同类型的道路

相同的概念用于无向图与有向图，边的方向为从一个顶点到下一个顶点。通常术语有向道路与有向圈用于有向情形。

一个没有重复顶点的道路称为简单道路，而一个除了起点与终点没有重复顶点的道路叫做简单圈。在现代图论中，大多数蕴含了“简单”，比如“圈”意味着“简单圈”而“道路”意味着“简单道路”，但这种约定也不总是总被遵守，特别是在应用图论中。一些作者（比如 Bondy and Murty 1976）使用术语“漫游”（walk）表示一个顶点或边可以重复的道路，而将术语“道路”保留给简单道路。

一条使得没有图的边连接道路中两个不相邻顶点的道路称为导出道路。

一个包含图中所有顶点的简单圈称为哈密顿圈。

如果两条道路没有任何公共内部顶点则称为无关的（或内部顶点不交）。

一条道路的长度是这条道路使用的边数，重复道路算上重复次数。在单顶点情形长度可以为零。

一个加权图在图中的每条边上给出一个值（权重）。加权图中一条道路的权是经过的边的权之和。有时使用成本（cost）或长度一词代替权。

相关条目

参考文献

  • Bondy, J. A.; Murty, U. S. R. Graph Theory with Applications. North Holland. 1976: 12–21. ISBN 0-444-19451-7. 
  • Diestel, Reinhard. Graph Theory 3rd ed. Graduate Texts in Mathematics, vol. 173, Springer-Verlag. 2005: 6–9 [2009-05-28]. ISBN 3-540-26182-6. （原始内容存档于2011-07-28）. 
  • Gibbons, A. Algorithmic Graph Theory. Cambridge University Press. 1985: 5–6. ISBN 0-521-28881-9. 
  • Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (Eds.). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics 9, Springer-Verlag. 1990. ISBN 0-387-52685-4.