道(グラフ)
概要
道(グラフ)（path）とは、グラフの頂点の列 $v_0,v_1,\dots,v_\ell$ であって、隣り合う頂点が辺で結ばれ、頂点がすべて相異なるもののことで、$\ell$ をその長さという。頂点の重複を許す列は歩道とよばれ、歩道から繰り返しを除くと道が得られる。同じ 2 頂点を結ぶ相異なる 2 本の道からは閉路が作れ、最小次数が $\delta$ の有限グラフには長さ $\delta$ 以上の道があり、連結グラフの最長の道どうしは必ず頂点を共有する。道は連結性・距離・木・閉路の定義の基礎であり、互いに交わらない道の本数は Menger の定理やネットワークフローで調べられる。
前提知識: グラフ
グラフの道（path）とは、辺をたどって頂点から頂点へ移る列のうち、同じ頂点を 2 度通らないもののことである。道は 2 頂点が「つながっている」ことの最も基本的な証拠であり、連結グラフ・距離(グラフ)・閉路・木などの定義はどれも道を使って述べられる。同じ頂点を何度通ってもよい列は歩道（walk）とよばれ、歩道から繰り返しを取り除くと道が得られる。
この記事では、歩道と道の定義と基本操作を述べたあと、道どうしの関係から閉路を作る定理（thm-pathg-two-paths）、最小次数から長い道と長い閉路の存在を導く定理（thm-pathg-long-path）、連結グラフの最長の道どうしが必ず交わるという定理（thm-pathg-longest-meet）を証明する。位相空間の連続な曲線としての道は 道(位相) で扱う。
定義
この記事の「グラフ」は、グラフ の記事の定義「グラフの定義」の単純無向グラフ $G=(V,E)$（$E\subset[V]^2$）である。辺 $\{u,v\}$ を $uv$ と書く。
$G=(V,E)$ をグラフとする。
- $G$ の歩道（walk）とは、頂点の有限列 $W=(v_0,v_1,\dots,v_\ell)$（$\ell\ge0$）であって、各 $i=1,\dots,\ell$ について $v_{i-1}v_i\in E$ となるものをいう。$\ell$ を $W$ の長さ、$v_0$ を始点、$v_\ell$ を終点といい、$W$ は $v_0$ と $v_\ell$ を結ぶという。始点が $u$、終点が $v$ の歩道を $u$–$v$ 歩道という。$v_1,\dots,v_{\ell-1}$ を $W$ の内部頂点という。
- 頂点 $v_0,v_1,\dots,v_\ell$ が相異なる歩道を道（path）という。$u$–$v$ 歩道である道を $u$–$v$ 道という。
- 辺 $v_0v_1,\dots,v_{\ell-1}v_\ell$ が相異なる歩道を小道（trail）という。
この定義は グラフ の記事の定義「歩道・道・閉路の定義」と同じである。長さ $0$ の道 $(v_0)$ も道であり、各頂点 $v$ はそれ自身と長さ $0$ の道で結ばれる。道では頂点が相異なるので辺も相異なり、道は小道である。単純グラフでは辺 $v_{i-1}v_i$ は 2 頂点から決まるので、歩道は頂点の列だけで指定できる。
道は頂点の「列」として定めたが、道の頂点と辺だけを集めた部分グラフを道とよぶこともある。
道 $P=(v_0,\dots,v_\ell)$ に対し、頂点集合 $\{v_0,\dots,v_\ell\}$ と辺集合 $\{v_{i-1}v_i\mid 1\le i\le\ell\}$ からなる $G$ の部分グラフを $P$ の定める部分グラフという。$G$ の部分グラフで、ある道の定める部分グラフになっているものも道とよぶ。
道 $(v_0,\dots,v_\ell)$ の定める部分グラフは、$i\mapsto v_{i-1}$（$1\le i\le\ell+1$）によりグラフ の記事の例「道グラフと閉路グラフ」の道グラフ $P_{\ell+1}$ と同型である。列 $(v_0,\dots,v_\ell)$ と逆順の列 $(v_\ell,\dots,v_0)$ は同じ部分グラフを定める。長さ $\ell\ge1$ の道の部分グラフを定める列はこの 2 つだけである。部分グラフ $P$ の中で次数 $1$ の頂点は $v_0,v_\ell$ の 2 つだけなので端点が決まり、端点の一方から始めると、残りの頂点は「直前の頂点以外の隣接頂点」として順に決まるからである。したがって $G$ の長さ $\ell\ge1$ の道は、列として数えると部分グラフとして数えた個数のちょうど 2 倍ある。
歩道について、次の操作を使う。$W=(v_0,\dots,v_\ell)$、$W'=(w_0,\dots,w_k)$ を歩道とする。
- $W$ の逆：$W^{-1}:=(v_\ell,v_{\ell-1},\dots,v_0)$。$W$ が道なら $W^{-1}$ も道である。
- $W$ と $W'$ の連結：$v_\ell=w_0$ のとき $WW':=(v_0,\dots,v_\ell=w_0,w_1,\dots,w_k)$。長さ $\ell+k$ の歩道である。$W,W'$ が道でも $WW'$ は道とは限らない。
- $W$ の区間：$0\le i\le j\le\ell$ に対し $W[v_i,v_j]:=(v_i,v_{i+1},\dots,v_j)$。$W$ が道なら区間も道である（道では頂点が相異なるので、区間は頂点 $v_i$ と $v_j$ で決まる）。
有向グラフ では辺の向きに沿った有向歩道・有向道を考える（有向グラフ の記事の定義「有向歩道・有向道・有向閉路」）。平行辺をもつ多重グラフでは、歩道を頂点と辺の交互列 $(v_0,e_1,v_1,\dots,e_\ell,v_\ell)$ として指定する必要がある。
直感
道は「地図の上で同じ交差点を 2 度通らない経路」である。どこかを 2 度通る経路は、2 度目に戻ってきた時点で間の寄り道を切り捨てれば短くなるので、2 頂点を最短で結ぶ経路は必ず道である。逆に言えば、2 頂点を結ぶ経路が 2 通りあれば、その違いの部分に「一周して戻る」構造、すなわち閉路がひそんでいる（thm-pathg-two-paths）。木が「閉路をもたない連結グラフ」でありながら「どの 2 頂点もただ 1 本の道で結ばれるグラフ」でもあるのは、この見方による。
各頂点の次数のような局所的な情報からも、道について大域的なことがわかる。最長の道の端の頂点は、道の外に出る辺をもたない（もてば道を延ばせる）ので、すべての隣接頂点を道の上にもつ。この「最長のものを考える」議論が、thm-pathg-long-path と thm-pathg-longest-meet の証明の中心である。
例と反例
完全グラフ $K_n$（$n\ge2$）の相異なる 2 頂点 $u,v$ を結ぶ道を数える。内部頂点が $k$ 個（$0\le k\le n-2$）の $u$–$v$ 道は、残りの $n-2$ 頂点から $k$ 個を選んで並べる方法と 1 対 1 に対応する。$K_n$ ではどの 2 頂点も隣接するので、どの並べ方も道になるからである。よって $u$–$v$ 道の本数は
$$
\sum_{k=0}^{n-2}\frac{(n-2)!}{(n-2-k)!}
$$
である。$K_4$ の頂点を $u,v,a,b$ とすると、$(u,v)$、$(u,a,v)$、$(u,b,v)$、$(u,a,b,v)$、$(u,b,a,v)$ の $1+2+2=5$ 本である。
始点と終点が同じ歩道 $(v_0,\dots,v_\ell)$（$v_\ell=v_0$）は、$\ell\ge1$ なら頂点 $v_0$ を 2 度含むので道ではない。満たす性質：歩道である。満たさない定義条件：頂点が相異なる。閉じた歩道のうち、始点以外の頂点が相異なり長さが $3$ 以上のものが閉路であり、道とは別の概念である。道 $(v_0,\dots,v_\ell)$（$\ell\ge2$）の両端点が隣接するとき、道に辺 $v_\ell v_0$ を加えた $(v_0,\dots,v_\ell,v_0)$ は閉路である。
2 つの三角形 $v,a,b$ と $v,c,d$ が頂点 $v$ を共有するグラフ（蝶ネクタイ形）で、列 $(a,b,v,c,d,v)$ は 5 本の辺 $ab,bv,vc,cd,dv$ が相異なる歩道なので小道であるが、頂点 $v$ を 2 度通るので道ではない。満たす性質：小道である。満たさない定義条件：頂点が相異なる。「小道ならば道」は成り立たない。
性質
歩道から道へ
$u$–$v$ 歩道があれば $u$–$v$ 道がある。これは 距離(グラフ) の記事の補題「歩道からの道の取り出し」であり、同記事では、歩道で同じ頂点が 2 度現れたら間の部分を除くことを繰り返して、長さがもとの歩道以下の道を得ている。この操作は歩道の区間を除くだけなので、得られる道の頂点と辺は、どれももとの歩道の頂点と辺である。特に、2 頂点 $u,v$ を結ぶ最短の歩道は道であり、その長さが距離(グラフ) $d_G(u,v)$ である。
歩道の言葉で言い換えると、2 頂点が道で結ばれるという関係の推移性は、道 $P$ と道 $Q$ を連結した歩道 $PQ$ から道を取り出すことで示される。これが連結グラフ・連結成分(グラフ)の定義の基礎になっている（グラフ の記事の命題「連結成分への分解」）。
2 本の道と閉路
$G$ をグラフ、$u,v$ を頂点とし、$P=(p_0,\dots,p_k)$ と $Q=(q_0,\dots,q_l)$ を相異なる $u$–$v$ 道とする（列として相異なる）。このとき $G$ には閉路 $Z$ であって、$Z$ の辺がすべて $P$ または $Q$ の辺であるものが存在する。
まず、一方が他方の始まりの部分と一致することはない。たとえば $k< l$ で $p_j=q_j$（$0\le j\le k$）とすると $q_k=p_k=v=q_l$ となり、$Q$ の頂点が相異なることに反する。$k=l$ なら $P=Q$ となって仮定に反する。$k>l$ の場合も同様である。したがって、$p_j=q_j$ が $0\le j\le i$ で成り立つ最大の $i$ をとると $i<\min(k,l)$ であり、$p_{i+1}\neq q_{i+1}$ である（$p_0=q_0=u$ なので $i\ge0$）。$w:=p_i=q_i$ とおく。
$p_k=v=q_l$ なので、$p_j\in\{q_{i+1},\dots,q_l\}$ となる $j\ge i+1$ が存在する。そのような最小の $j$ をとり、$p_j=q_h$（$h\ge i+1$）とする。列 $Z:=(w=p_i,\ p_{i+1},\ \dots,\ p_j=q_h,\ q_{h-1},\ \dots,\ q_{i+1},\ q_i=w)$ を考える。隣り合う頂点は $P$ または $Q$ の辺で結ばれているので、$Z$ は閉じた歩道であり、その辺は $P$ か $Q$ の辺である。長さは $(j-i)+(h-i)$ である。
$Z$ の始点以外の頂点 $p_{i+1},\dots,p_j,q_{h-1},\dots,q_{i+1},w$ が相異なることを確かめる。$p_{i+1},\dots,p_j$ は $P$ の頂点として相異なり、$w=p_i$ とも異なる。$q_{i+1},\dots,q_{h-1}$ は $Q$ の頂点として相異なり、$q_h$ とも $w=q_i$ とも異なる。$j$ の最小性により $p_{i+1},\dots,p_{j-1}$ は $\{q_{i+1},\dots,q_l\}$ に属さないので、$q_{i+1},\dots,q_{h-1}$ のどれとも異なる。$p_j=q_h$ は $q_{i+1},\dots,q_{h-1}$ と異なる。
最後に長さが $3$ 以上であることを示す。$j-i\ge1$、$h-i\ge1$ なので、長さ $(j-i)+(h-i)$ が $2$ 以下になるのは $j-i=h-i=1$ のときだけである。そのときは $p_{i+1}=p_j=q_h=q_{i+1}$ となり、$i$ の選び方に反する。よって長さは $3$ 以上で、$Z$ は閉路である。$\square$
この定理から、どの 2 頂点も高々 1 本の道で結ばれるグラフは閉路をもたない。逆に閉路 $(z_0,z_1,\dots,z_\ell=z_0)$ があれば、$z_0$ と $z_1$ は辺の道 $(z_0,z_1)$ と、閉路を逆にたどる道 $(z_0,z_{\ell-1},\dots,z_1)$ の 2 本で結ばれる。したがって、閉路をもたないこと（森であること）と、どの 2 頂点も高々 1 本の道で結ばれることは同値である。これは 森 の記事の定理「森の同値条件」の一部であり（同記事の証明も、最後の共通頂点から始めて相手の道の後半に初めて戻る頂点で乗り換える同じ構成による）、連結な場合が 木 の記事の命題「木の三つの基本性質」の 1 である。
グラフ $G$ の辺 $e=uv$ が、$e$ を使わない $u$–$v$ 道をもつことと、$e$ がある閉路の辺であることは同値である。
$e$ を使わない $u$–$v$ 道 $P$ は長さ $2$ 以上（長さ $1$ の $u$–$v$ 道は $(u,v)$ で $e$ を使う）であり、$P$ の後に $e$ で $u$ に戻る列は閉路である（ex-pathg-closed-walk）。逆に $e$ が閉路 $(z_0,\dots,z_\ell=z_0)$ の辺 $z_{m-1}z_m$ なら、閉路を $e$ の反対側に回る列 $(z_{m-1},z_{m-2},\dots,z_0=z_\ell,z_{\ell-1},\dots,z_m)$ は、頂点が相異なり $e$ を使わない $z_{m-1}$–$z_m$ 道である（閉路の辺は相異なる）。必要なら逆にすれば $e$ を使わない $u$–$v$ 道が得られる。$\square$
辺 $e=uv$ を除いたグラフ $G-e$ の連結成分の個数は、$G-e$ で $u$ と $v$ が道で結ばれれば $G$ と同じで、結ばれなければ $G$ より $1$ 多い（連結グラフ の記事の補題「辺を 1 本加えたときの連結成分」）。$G-e$ の $u$–$v$ 道とは $e$ を使わない $G$ の $u$–$v$ 道のことなので、この系とあわせると、有限グラフでは、除くと連結成分が増える辺（橋）は、どの閉路にも含まれない辺のことである。これは 閉路 の記事の定理「閉路に含まれる辺と橋」と同じことである。
最小次数と長い道
頂点の最小次数を $\delta(G)$ と書く（次数(グラフ)）。
$G$ を頂点集合が空でない有限グラフとする。
- $G$ には長さ $\delta(G)$ 以上の道がある。
- $\delta(G)\ge2$ ならば、$G$ には長さ $\delta(G)+1$ 以上の閉路がある（閉路 の記事の定理「最小次数と長い閉路」）。
$G$ は有限なので、道の長さは $|V|-1$ 以下であり、長さが最大の道 $P=(x_0,x_1,\dots,x_\ell)$ がとれる。$x_\ell$ の隣接頂点 $y$ がすべて $P$ の上にあることを示す。$y$ が $P$ の上になければ $(x_0,\dots,x_\ell,y)$ は長さ $\ell+1$ の道となり、$P$ の最大性に反するからである。$x_\ell$ は自分自身と隣接しないので、その隣接頂点は $x_0,\dots,x_{\ell-1}$ の中にあり、$\delta(G)\le\deg(x_\ell)\le\ell$ である。これで 1 が示された。
2 は 閉路 の記事の定理「最小次数と長い閉路」で証明されている。同記事の証明も、1 の証明と同じく長さが最大の道をとり、その端点の隣接頂点がすべて道の上にあることを使って、端点から最も遠い隣接頂点までの部分を閉じて閉路を作る。$\square$
1 は BM76 Exercise 1.6.3（p. 13）、2 は同書 Exercise 1.7.3（p. 15）である。2 の有限性を外せないこと（整数全体を頂点とする道）は、閉路 の記事の節「反例と用語の区別」の表にある。完全グラフ $K_{d+1}$ は $\delta=d$ で、最長の道の長さは $d$、最長の閉路の長さは $d+1$ なので、どちらの評価もこれ以上改善できない。
最長の道どうしは交わる
$G$ を有限な連結グラフとし、$P,Q$ を $G$ の長さが最大の道とする。このとき $P$ と $Q$ は共通の頂点をもつ。
最長の道の長さを $\ell$ とし、$P$ と $Q$ に共通の頂点がないと仮定する。$G$ は連結なので、$P$ の頂点と $Q$ の頂点を結ぶ道がある。そのような道のうち長さが最小のもの $R=(r_0,r_1,\dots,r_m)$（$r_0\in V(P)$、$r_m\in V(Q)$）をとる。$P$ と $Q$ は交わらないので $m\ge1$ である。$R$ の内部頂点 $r_1,\dots,r_{m-1}$ は $P$ にも $Q$ にも属さない。もし $r_a\in V(P)$（$0< a< m$）なら区間 $R[r_a,r_m]$ がより短い道になり、$r_a\in V(Q)$ なら $R[r_0,r_a]$ がより短い道になるからである。
$P=(p_0,\dots,p_\ell)$ で $r_0=p_s$ とすると、$P[p_0,p_s]$ と $P[p_s,p_\ell]$ の長さは $s$ と $\ell-s$ で、大きい方は $\ell/2$ 以上である。その区間を、$p_s$ で終わる向きに並べたものを $P'$ とする（$s\ge\ell-s$ なら $P':=P[p_0,p_s]$、そうでなければ $P':=P[p_s,p_\ell]^{-1}$）。同様に $Q$ を $r_m$ で 2 つに分けた区間のうち長い方を、$r_m$ から始まる向きに並べたものを $Q'$ とする。$Q'$ の長さも $\ell/2$ 以上である。
連結した歩道 $P'RQ'$ の頂点は、$P'$ の頂点（$P$ の頂点）、$R$ の内部頂点（$P,Q$ の外）、$Q'$ の頂点（$Q$ の頂点）であり、$P$ と $Q$ は交わらないので、すべて相異なる。よって $P'RQ'$ は道であり、その長さは
$$
\frac{\ell}{2}+m+\frac{\ell}{2}\ge\ell+1
$$
以上である。これは $\ell$ の最大性に反する。$\square$
これは BM76 Exercise 1.6.10（p. 14）である。連結性の仮定は外せない。2 つの道グラフ $P_3$ を並べた（非交和の）グラフでは、それぞれの $P_3$ が長さ $2$ の最長の道であり、共通の頂点をもたない。
定理の仮定を外した場合
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-pathg-two-paths の「道」を「歩道」に | $K_2$（頂点 $u,v$）の歩道 $(u,v)$ と $(u,v,u,v)$ | 相異なる 2 本の $u$–$v$ 歩道があるが閉路はない |
| thm-pathg-two-paths の単純グラフを多重グラフに | 2 頂点を平行辺 $e,e'$ で結んだ多重グラフ | 2 本の道 $(u,e,v)$、$(u,e',v)$ があるが長さ $3$ 以上の閉路はない |
| thm-pathg-long-path の単純性 | 2 頂点を 3 本の平行辺で結んだ多重グラフ | 最小次数は $3$ だが最長の道の長さは $1$ |
| thm-pathg-longest-meet の連結性 | $P_3$ を 2 つ並べたグラフ | 最長の道 2 本が交わらない |
1 行目：$K_2$ には辺が 1 本しかないので閉路（長さ $3$ 以上）はない。2 本の歩道は長さが $1$ と $3$ で異なる。thm-pathg-two-paths の証明は、頂点が相異なることを、一方が他方の始まりと一致しないことと、閉じた歩道 $Z$ の頂点が相異なることに使っている。
2 行目：多重グラフの道を頂点と辺の交互列とすると、$(u,e,v)$ と $(u,e',v)$ は相異なる道である。証明の構成で得られる閉じた歩道は $(u,e,v,e',u)$ で長さが $2$ であり、グラフ の記事の定義「歩道・道・閉路の定義」の閉路の条件 $\ell\ge3$ を満たさない。単純グラフでは長さ $2$ になりえないことを証明の最後の段落で使っている（平行辺による長さ $2$ の閉路を閉路とみなす流儀もある。グラフ の記事の定義「向きと多重辺とループを許す変種」の後の説明を参照）。
3 行目：2 頂点しかないので道の長さは $1$ 以下である。各頂点には 3 本の辺が接続する。単純グラフでは $\deg(x_\ell)$ は隣接頂点の個数に等しいことを、証明の不等式 $\deg(x_\ell)\le\ell$ に使っている。
4 行目：上で述べたとおりである。
補足
道と歩道の用語には流儀の差がある。BM76 §1.6（p. 12）は歩道を頂点と辺の交互列 $v_0e_1v_1\cdots e_kv_k$ として定め、辺が相異なるものを小道、さらに頂点が相異なるものを道とよび、道の頂点と辺からなる部分グラフも道とよぶ。この記事の定義と同じ考え方である。
すべての頂点を通る道は Hamilton 路とよばれる（Hamilton閉路 の記事の定義「Hamilton閉路とHamilton路」）。2 頂点を結ぶ道の存在は幅優先探索や深さ優先探索によって判定できる。辺に長さがあるときに長さの和が最小の道を求めるのが最短路問題である。
複数の道を「互いに交わらないように」選ぶ問題も基本的である。有限グラフの隣接しない 2 頂点 $s,t$ を結ぶ道で、$s,t$ 以外の頂点を共有しないものの最大本数は、$s$ と $t$ を分けるのに除く必要のある頂点の最小個数に等しい（連結度(グラフ) の記事の定理「Mengerの定理（頂点版）」）。この定理はネットワークフローの最大流最小カット定理から導かれる。
グラフの各辺を線分とみなして端点で貼り合わせた図形では、グラフの道 $(v_0,\dots,v_\ell)$ は線分を順にたどる連続な曲線を与え、道(位相) の意味の道になる（連結グラフ の記事の注意「位相空間の連結性との関係」）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
