グラフ理論において、グラフの道（みち）またはパス（英: path）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。
道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al. (1990) では、道に関するより進んだアルゴリズム的項目を網羅している。 無向グラフだけでなく、有向グラフにも道はあり、頂点の列において常に前の頂点から次の頂点へ辺が向かっている。「有向道; directed path」、「有向閉道; directed cycle」といった呼称もよく使われる。 頂点が複数回出現しない道を単純道 (simple path) と呼び、始点/終点以外の頂点が複数回出現しない閉道を単純閉道 (simple cycle) と呼ぶ。最近では "simple"（単純）は最初から含意されていることが多く、閉道と言えば単純閉道を意味し、道といえば単純道を意味する。 ただし常にそういう意味で使われるとは限らない。書籍によっては（例えば Bondy and Murty 1976）、頂点が反復する道を歩道 (walk) と呼び、ここでいう単純道を道 (path) と呼んでいる。歩道（walk）から辺の反復を除いたものを小道（trail
道の種類
道の上で隣接しない頂点間に辺が存在しない道を誘導道 (induced path) と呼ぶ。
グラフの全ての頂点を含む単純閉道をハミルトン閉路と呼ぶ。
共通する内部頂点を持たない2つの道は互いに「独立」、あるいは「内部頂点が互いに素 (点素)」であるという。また、共通する内部の辺を持たない2つの道は互いに「辺素」であるという
道を構成する辺の数を道の「長さ」と呼び、複数回出現する辺は複数回カウントする。頂点が1つでも道ということができ、その場合の長さはゼロである。
重み付きグラフは各辺に値（重み）が対応しているグラフである。この場合「道の重み」は、道に属する辺の重みの総和である。重み (weight) ではなく、コスト (cost) とか長さ (length) と呼ぶこともある。
関連項目
グラフ理論
最短経路問題
巡回セールスマン問題
中国人郵便配達問題
参考文献
Bondy, J. A.; Murty, U. S. R. (1976). Graph Theory with Applications. North Holland. pp. 12?21. .mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}ISBN 0-444-19451-7
Diestel, Reinhard (2005). ⇒Graph Theory (3rd ed. ed.). Graduate Texts in Mathematics, vol. 173, Springer-Verlag. pp. 6?9. ISBN 3-540-26182-6. ⇒http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. pp. 5?6. ISBN 0-521-28881-9
Korte, Bernhard; Lovasz, Laszlo; Promel, Hans Jurgen; Schrijver, Alexander (Eds.) (1990). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics 9, Springer-Verlag. ISBN 0-387-52685-4
典拠管理データベース: 国立図書館
⇒イスラエル
アメリカ