道路 (圖論)
（重新導向自路径 (图论)）
在圖論中，一個圖中一條道路或稱路徑（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.