道_(グラフ理論)とは？わかりやすく解説

有向閉道の例。矢印がなければ単なる閉道である。青い頂点は2度通るので、単純な閉道（すなわち閉路）ではない。

グラフ理論において、グラフの道（みち）またはパス（英: 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）という。小道（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. 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
Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. pp. 5–6. ISBN 0-521-28881-9
Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (Eds.) (1990). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics 9, Springer-Verlag. ISBN 0-387-52685-4

表話編歴グラフ理論
要素・定義・表現	頂点辺（英語版）グラフ無向有向ラベル付き（英語版）重み付き（英語版）ハイパーグラフ接続行列隣接行列隣接リストラプラシアン行列
指標	位数（英語版）サイズ（英語版）次数次数行列距離（英語版）半径直径内周 (頂点)彩色数辺彩色数（英語版）点連結度辺連結度交叉数（英語版）
部分構造	ループ（英語版）多重辺（英語版）部分グラフ（英語版）誘導部分グラフ道閉道連結成分（英語版）強連結成分（英語版）橋（英語版）カットクリーク独立集合支配集合マッチングオイラー路シュタイナー木全域木ハミルトン路
全体構造	連結グラフ正則グラフ立方体グラフケージ強正則グラフ木平面グラフ 2部グラフ有向非巡回グラフ弦グラフムーアグラフパーフェクトグラフ対称グラフ半対称グラフ頂点推移グラフ辺推移グラフ距離推移グラフ補グラフ双対グラフグラフ同型
固有名を持つグラフ	パスグラフ（英語版） $P n$ 閉路グラフ $C n$ 完全グラフ $K n$ 完全2部グラフ $K m, n$ スター $S n = K 1, n$ 車輪グラフ $W n$ 空グラフピーターセングラフヒーウッドグラフマギーグラフホフマンシングルトングラフフォークマングラフ
トピック・定理	一筆書きオイラーの多面体定理クラトフスキの定理四色定理五色定理ケイリーの公式プリューファー列最短経路問題巡回セールスマン問題中国人郵便配達問題ダイクストラ法ベルマン-フォード法ワーシャル-フロイド法ハミルトン閉路問題最大クリーク問題頂点被覆問題最小頂点被覆問題最大独立集合問題最大流最小カット定理最大カット問題支配集合問題次数直径問題安定結婚問題
カテゴリ / コモンズ


	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの道 (グラフ理論) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

道_(グラフ理論)とは？わかりやすく解説