有向グラフ
概要
有向グラフ（directed graph）とは、頂点の集合 $V$ と、順序対の集合 $A\subset V\times V$（有向辺の集合）の組 $(V,A)$ のことである。有向辺 $(u,v)$ は $u$ から $v$ への向きをもち、$A$ は $V$ 上の二項関係と同じものである。本記事ではループ $(v,v)$ を許すが、許さない流儀や多重辺を許す流儀もある。向きがあるため、$u$ から $v$ へ有向歩道で行けても $v$ から $u$ へ行けるとは限らず、互いに行き来できる頂点のまとまり（強連結成分）を 1 点につぶした有向グラフは有向閉路をもたない。有限の有向グラフが有向閉路をもたないことは、すべての有向辺が前から後ろへ向くように頂点を一列に並べられること（位相的順序）と同値である。単純無向グラフは、ループのない対称な有向グラフとみなせる。
定義
本記事の「有向グラフ」は、辺に向きがある グラフ である。記法は グラフ の記事の定義「向きと多重辺とループを許す変種」に揃え、頂点の集合を $V$、有向辺の集合を $A$ と書く。
有向グラフ（directed graph, digraph）とは、集合 $V$ と、順序対の集合 $A\subset V\times V$ の組 $D=(V,A)$ のことをいう。$V$ の元を $D$ の 頂点、$A$ の元を $D$ の 有向辺（arc）という。有向辺 $(u,v)$ を $u$ から $v$ への有向辺といい、$u$ をその 始点（tail）、$v$ をその 終点（head）という。$(v,v)$ の形の有向辺を ループ という。$V$ が有限のとき $D$ を有限有向グラフという。
- 頂点 $v$ の 外近傍 を $N^+_D(v):=\{w\in V\mid(v,w)\in A\}$、内近傍 を $N^-_D(v):=\{u\in V\mid(u,v)\in A\}$ と書く。
- ループをもたない有向グラフを ループなし有向グラフ という。
- $D$ の各有向辺の向きを逆にした $D^{\mathrm{op}}:=(V,\{(v,u)\mid(u,v)\in A\})$ を $D$ の 逆有向グラフ（converse）という。
$A\subset V\times V$ であるから、有向辺の集合 $A$ は $V$ 上の 二項関係 そのものであり、逆に $V$ 上の二項関係 $R$ は有向グラフ $(V,R)$ を定める。この対応で、$V$ を固定したときの有向グラフと $V$ 上の二項関係は 1 対 1 に対応する。ループ $(v,v)$ は関係 $v\,R\,v$ に、逆有向グラフは 逆関係 にあたる。同じ始点と終点をもつ有向辺は 1 本しかない（$A$ は集合なので）。
有向グラフの定義には流儀の差がある。本記事は二項関係との対応を保つためにループを許す。BJG09 第 1 章は、有向グラフを「頂点集合が空でない有限集合で、有向辺は相異なる 2 頂点の順序対」と定め、ループを除く。Die17 §1.10 は、辺の集合 $E$ と始点・終点を与える 2 つの写像 $\mathrm{init},\mathrm{ter}\colon E\to V$ の組を有向グラフと呼び、同じ始点と終点をもつ複数の辺やループを許す。これは グラフ の記事でいう 多重有向グラフ $(V,E,i,t)$ にあたる。本記事の有向グラフは、多重有向グラフのうち「$i(e)=i(e')$ かつ $t(e)=t(e')$ ならば $e=e'$」を満たすものと同じものである（$e\mapsto(i(e),t(e))$ で $E$ を $V\times V$ の部分集合と同一視する）。文献を読むときは、ループと多重辺の扱いを確かめる必要がある。
$D=(V,A)$ を有向グラフとする。
- $D$ の 基礎グラフ（underlying graph）とは、ループを除き向きを忘れて得られる単純無向グラフ
$$G(D):=\bigl(V,\ \{\{u,v\}\mid u\neq v,\ (u,v)\in A\ \text{または}\ (v,u)\in A\}\bigr)$$
のことをいう。 - 単純無向グラフ $G=(V,E)$ の 向き付け（orientation）とは、各辺 $\{u,v\}\in E$ について $(u,v)$ と $(v,u)$ のちょうど一方を選んで得られる有向グラフのことをいう。向き付けの基礎グラフは $G$ である。
- $D$ が 対称（symmetric）であるとは、$(u,v)\in A$ ならば $(v,u)\in A$ となることをいう。
ループなしの対称な有向グラフ $(V,A)$ と単純無向グラフ $(V,E)$ は、$\{u,v\}\in E\iff(u,v)\in A$ によって 1 対 1 に対応する。これは グラフ の記事で、無向グラフの辺集合を対称かつ非反射的な二項関係と同一視したことの言い換えである。この意味で、無向グラフは有向グラフの特別な場合とみなせる。
$D=(V,A)$ を有向グラフとする。
- 有向歩道（directed walk）とは、頂点の有限列 $v_0,v_1,\dots,v_\ell$（$\ell\ge0$）であって、各 $i=1,\dots,\ell$ について $(v_{i-1},v_i)\in A$ となるものをいう。$\ell$ をその長さといい、$v_0$ から $v_\ell$ への有向歩道という。
- 頂点 $v_0,\dots,v_\ell$ が相異なる有向歩道を 有向道（directed path）という。
- 有向閉路（directed cycle）とは、有向歩道 $v_0,v_1,\dots,v_\ell$ であって、$\ell\ge1$、$v_\ell=v_0$、かつ $v_1,\dots,v_\ell$ が相異なるものをいう。
- 有向閉路をもたない有向グラフを 非巡回有向グラフ（directed acyclic graph、DAG）という。
無向グラフの閉路には長さ $3$ 以上を課した（グラフ の記事の定義「歩道・道・閉路の定義」）が、有向閉路には課さない。長さ $1$ の有向閉路 $v,v$ はループ $(v,v)$ であり、長さ $2$ の有向閉路 $u,v,u$ は相異なる 2 本の有向辺 $(u,v)$、$(v,u)$ からなる。無向グラフで長さ $2$ の閉歩道 $u,v,u$ を閉路から除いたのは同じ辺を往復するだけだからであり、有向グラフの $(u,v)$ と $(v,u)$ は別の有向辺なので、この往復は除かない。とくに、非巡回有向グラフはループをもたない。
$D=(V,A)$ を有向グラフとする。
- 頂点 $v$ が頂点 $u$ から 到達可能（reachable）であるとは、$u$ から $v$ への有向歩道が存在することをいい、$u\rightsquigarrow v$ と書く。長さ $0$ の有向歩道により $u\rightsquigarrow u$ である。
- $D$ が 強連結（strongly connected）であるとは、$V\neq\emptyset$ であって、任意の $u,v\in V$ について $u\rightsquigarrow v$ となることをいう。
- $D$ が 弱連結（weakly connected）であるとは、基礎グラフ $G(D)$ が 連結グラフ であることをいう。
- $u\rightsquigarrow v$ かつ $v\rightsquigarrow u$ であるとき $u\sim v$ と書く。$\sim$ は $V$ 上の 同値関係 であり（prop-directed-graph-strong-components）、その各 同値類 を $D$ の 強連結成分（strongly connected component）という。
有向歩道があれば、同じ始点と終点をもつ有向道がある。有向歩道 $v_0,\dots,v_\ell$ で $v_i=v_j$（$i< j$）となる箇所があれば、$v_{i+1},\dots,v_j$ を取り除いても有向歩道であり、長さが短くなるからである。関係 $\rightsquigarrow$ は二項関係 $A$ の反射推移閉包（$A$ を含む最小の反射的かつ推移的な関係）にほかならない（推移閉包）。
直感
有向グラフは「一方向の結びつき」を表す。一方通行の道路網、Web ページの間のリンク、仕事の前後関係、状態の遷移、「$a$ は $b$ を割り切る」のような関係は、いずれも頂点を対象、有向辺を「$u$ から $v$ へ」の結びつきとして描ける。向きがあるため、$u$ から $v$ へ行けても $v$ から $u$ へ戻れるとは限らない。無向グラフの連結性が一つの同値関係で済んだのに対し、有向グラフでは「行ける」と「行き来できる」が分かれ、行き来できる頂点のまとまり（強連結成分）と、その間の一方向の流れ（prop-directed-graph-condensation）という二層の構造が現れる。有向閉路がない場合は、すべての有向辺が同じ向きを向くように頂点を一列に並べられる（thm-directed-graph-topological-order）。
例と反例
- $V=\{1,2,3,4,6\}$ 上の関係「$a\neq b$ かつ $a$ は $b$ を割り切る」の有向グラフの有向辺は $(1,2),(1,3),(1,4),(1,6),(2,4),(2,6),(3,6)$ の 7 本である。有向辺 $(a,b)$ では $a< b$ なので、有向歩道に沿って頂点の値は増え続け、有向閉路はない。すなわちこれは非巡回有向グラフである。$(2,4)$ はあるが $(4,2)$ はないので対称でない。
- $V=\{1,2,3\}$ 上の関係 $\le$ の有向グラフは、3 本のループ $(1,1),(2,2),(3,3)$ と $(1,2),(1,3),(2,3)$ からなる。一般に、関係 $R$ が 反射関係 であることはすべての頂点にループがあること、推移関係 であることは「$(u,v),(v,w)\in A$ ならば $(u,w)\in A$」、対称関係 であることは有向グラフが対称であることにあたる。
- 写像 $f\colon V\to V$ の 写像のグラフ $\{(v,f(v))\mid v\in V\}$ を有向辺の集合とする有向グラフでは、すべての頂点の出次数が $1$ である（次数(グラフ) の記事の定義「多重グラフと有向グラフの次数」）。$V$ が有限なら、各頂点から有向辺をたどり続けるといずれ有向閉路に入る。
- $n\ge1$ に対し、頂点 $0,1,\dots,n-1$ と有向辺 $(i,i+1\bmod n)$ からなる有向グラフを 有向閉路グラフ $\vec C_n$ という。$\vec C_1$ はループ 1 本、$\vec C_2$ は $(0,1),(1,0)$ からなる。$\vec C_n$ は強連結である。どの頂点 $i$ からも有向辺をたどって任意の頂点 $j$ に着くからである。$n\ge3$ のとき $\vec C_n$ は閉路グラフ $C_n$ の向き付けである。
- 完全グラフ $K_n$ の向き付けを $n$ 頂点の トーナメント（tournament）という。$n$ 人の総当たり戦で、$u$ が $v$ に勝ったときに $(u,v)$ を置いた記録にあたる。頂点 $1,\dots,n$ について $i< j$ のとき $(i,j)$ を置いたものを推移的トーナメントといい、これは非巡回である。一方、$n\ge3$ のとき、有向辺 $(1,2),(2,3),(3,1)$ を含むトーナメントは長さ $3$ の有向閉路 $1,2,3,1$ をもち、非巡回でない。
頂点 $1,2,3$ と有向辺 $(1,2),(2,3)$ からなる有向グラフ $D$ を考える。基礎グラフは道グラフ $P_3$ で連結なので、$D$ は弱連結である。しかし $3$ から出る有向辺はないので、$3$ から $1$ へ到達できず、$D$ は強連結でない。満たす性質：弱連結である。満たさない性質：強連結である。破る含意：「基礎グラフが連結 ⇒ 強連結」は成り立たない。$D$ の強連結成分は $\{1\},\{2\},\{3\}$ の 3 つである。逆向きの含意「強連結 ⇒ 弱連結」は成り立つ。$u\rightsquigarrow v$ を与える有向歩道は、向きを忘れると基礎グラフで $u$ と $v$ を結ぶ歩道になるからである（基礎グラフではループが除かれるが、有向歩道からループをたどる箇所 $v_{i-1}=v_i$ を取り除いても同じ始点と終点をもつ有向歩道のままである）。
- 頂点 $1,2,3$ と有向辺 $(1,2),(2,3),(1,3)$ からなる有向グラフは、有向辺 $(a,b)$ で $a< b$ となるので有向閉路をもたない。しかし基礎グラフは三角形 $K_3$ で閉路をもつ。満たす性質：非巡回有向グラフである。満たさない性質：基礎グラフが 森 である。破る含意：「非巡回有向グラフ ⇒ 基礎グラフが森」は成り立たない。
- 有向辺 $(u,v),(v,u)$ だけからなる有向グラフ $\vec C_2$ は長さ $2$ の有向閉路をもつが、基礎グラフは辺 1 本の道グラフ $P_2$ で閉路をもたない。破る含意：「有向閉路をもつ ⇒ 基礎グラフが閉路をもつ」は成り立たない。逆に、長さ $3$ 以上の有向閉路は基礎グラフの閉路を与える（頂点が相異なるので）。
性質
有限有向グラフでは、出次数の総和と入次数の総和はともに有向辺の本数に等しい（次数(グラフ) の記事の命題「有向グラフの出次数と入次数の総和」）。以下では到達可能性と有向閉路を扱う。
有向グラフ $D=(V,A)$ の頂点の関係 $\sim$（$u\rightsquigarrow v$ かつ $v\rightsquigarrow u$）は $V$ 上の同値関係である。各強連結成分 $C$ について、$C$ の頂点と、始点・終点がともに $C$ に属する有向辺全体からなる有向グラフ $D[C]:=(C,A\cap(C\times C))$ は強連結である。$D$ が強連結であることと、強連結成分がちょうど 1 個であることは同値である。
関係 $\rightsquigarrow$ は反射的（長さ $0$ の有向歩道）かつ推移的（$u$ から $v$ への有向歩道と $v$ から $w$ への有向歩道を $v$ でつなぐ）である。よって $\sim$ は反射的かつ推移的であり、定義から対称的なので同値関係である。
$C$ を同値類とし、$u,v\in C$ とする。$u$ から $v$ への $D$ の有向歩道 $v_0,\dots,v_\ell$ をとる。各 $v_i$ について、$v_0,\dots,v_i$ により $u\rightsquigarrow v_i$、$v_i,\dots,v_\ell$ と $v\rightsquigarrow u$ をつないで $v_i\rightsquigarrow u$ なので、$v_i\sim u$、すなわち $v_i\in C$ である。したがって各有向辺 $(v_{i-1},v_i)$ は $A\cap(C\times C)$ に属し、この有向歩道は $D[C]$ の有向歩道である。$C\neq\emptyset$ とあわせて $D[C]$ は強連結である。
$D$ が強連結なら、$V\neq\emptyset$ で任意の 2 頂点が $\sim$ の関係にあるので同値類は $V$ の 1 個だけである。逆に同値類が 1 個だけなら、それは $V$ で $V\neq\emptyset$ であり、任意の $u,v$ について $u\rightsquigarrow v$ なので $D$ は強連結である。$\square$
強連結成分どうしの関係は、成分を 1 点につぶした有向グラフで表せる。有向グラフ $D=(V,A)$ の強連結成分全体の集合を $V/{\sim}$ とし、相異なる成分 $C,C'$ について「$u\in C$、$v\in C'$ となる有向辺 $(u,v)\in A$ がある」とき $(C,C')$ を有向辺とする有向グラフ $D/{\sim}$ を、$D$ の 凝縮（condensation）という。
任意の有向グラフ $D$ の凝縮 $D/{\sim}$ は非巡回有向グラフである。
$D/{\sim}$ はループをもたない（有向辺は相異なる成分の間にだけ置いた）ので、長さ $1$ の有向閉路はない。長さ $\ell\ge2$ の有向閉路 $C_0,C_1,\dots,C_\ell=C_0$ があったとする。各 $i$ について、$u_i\in C_{i-1}$、$w_i\in C_i$ となる有向辺 $(u_i,w_i)\in A$ をとる。同じ強連結成分の頂点は互いに到達可能なので、$w_i\rightsquigarrow u_{i+1}$（ともに $C_i$ に属する。添字は $\ell$ を法とする）である。したがって、任意の $x\in C_0$、$y\in C_1$ について
$$x\rightsquigarrow u_1\to w_1\rightsquigarrow y,\qquad y\rightsquigarrow u_2\to w_2\rightsquigarrow u_3\to\cdots\to w_\ell\rightsquigarrow x$$
であり（$\to$ は有向辺）、$x\sim y$ となる。よって $C_0=C_1$ となり、有向辺 $(C_0,C_1)$ が相異なる成分の間にあることに反する。$\square$
非巡回有向グラフは、頂点を一列に並べてすべての有向辺を「前から後ろへ」向けられる有向グラフとして特徴づけられる。このような並べ方を 位相的順序（topological order）という。
空でない有限の非巡回有向グラフ $D=(V,A)$ には、入次数が $0$ の頂点（源点、source）が存在する。
すべての頂点の入次数が $1$ 以上であると仮定する。$n:=|V|$ とし、頂点 $w_0$ をとる。$w_0,\dots,w_k$ まで定まったとき、$w_k$ の入次数は $1$ 以上なので $(w_{k+1},w_k)\in A$ となる頂点 $w_{k+1}$ がとれる（$V$ は有限なので、あらかじめ $V$ の元に番号を付けておき、条件を満たすもののうち番号最小のものをとればよい）。こうして得た $n+1$ 個の頂点 $w_0,\dots,w_n$ の中には等しいものがあるので（鳩の巣原理）、$w_i=w_j$ かつ $i< j$ となる組のうち $j-i$ が最小のものをとる。最小性により $w_{i+1},\dots,w_j$ は相異なる。列 $w_j,w_{j-1},\dots,w_i$ は、各 $(w_{k+1},w_k)\in A$ により長さ $j-i\ge1$ の有向歩道であり、$w_i=w_j$ で $w_{j-1},\dots,w_i$ は相異なるので有向閉路である。これは非巡回性に反する。$\square$
有限有向グラフ $D=(V,A)$、$n:=|V|$ について、次は同値である。
- $D$ は非巡回有向グラフである。
- $V$ の元の並べ方 $v_1,v_2,\dots,v_n$（$V$ の番号付け）であって、任意の有向辺 $(v_i,v_j)\in A$ について $i< j$ となるものが存在する。
2 ⇒ 1：有向閉路 $v_{i_0},v_{i_1},\dots,v_{i_\ell}=v_{i_0}$（$\ell\ge1$）があれば、各有向辺について添字が増えるので $i_0< i_1<\cdots< i_\ell=i_0$ となり矛盾する。
1 ⇒ 2：$n$ についての帰納法で示す。$n=0$ なら空の並べ方でよい。$n\ge1$ とする。lem-directed-graph-source により入次数 $0$ の頂点 $v_1$ がある。$V':=V\setminus\{v_1\}$ とおき、$D$ から $v_1$ とそれに接続する有向辺を除いた有向グラフ $D':=(V',A\cap(V'\times V'))$ を考える。$D'$ の有向閉路は $D$ の有向閉路でもあるので、$D'$ は非巡回である。帰納法の仮定により $V'$ の並べ方 $v_2,\dots,v_n$ で $D'$ の有向辺が添字を増やすものがある。$D$ の有向辺 $(v_i,v_j)$ は、$v_1$ に接続しないなら $D'$ の有向辺なので $i< j$ である。$v_1$ に接続するなら、$v_1$ の入次数は $0$ なので $v_j\neq v_1$ であり、$v_i=v_1$、$i=1< j$ である（ループ $(v_1,v_1)$ は入次数を $1$ 増やすので存在しない）。$\square$
位相的順序は一般には一意でない。頂点 $1,2$ だけで有向辺のない有向グラフでは $1,2$ と $2,1$ のどちらも位相的順序である。上の証明は、入次数 $0$ の頂点を取り除くことを繰り返す算法（仕事の手順を決める算法として用いられる）でもある（BJG09 第 2 章）。
有限有向グラフは行列でも表せる。頂点を $v_1,\dots,v_n$ と番号付けし、$n$ 次正方 行列 $M=(m_{ij})$ を、$(v_i,v_j)\in A$ のとき $m_{ij}:=1$、そうでないとき $m_{ij}:=0$ と定めて、$D$ の 隣接行列（隣接行列）という。$D$ が対称であることは $M$ が 対称行列 であることと同値であり、一般の有向グラフの隣接行列は対称とは限らない（$\vec C_3$ の頂点を $v_i:=i-1$ と番号付けると $m_{12}=1$、$m_{21}=0$）。ループ $(v_i,v_i)$ は対角成分 $m_{ii}=1$ にあたる。
有限有向グラフ $D$ の隣接行列を $M$ とし、$k\in\mathbb{N}$ とする。$M^k$ の $(i,j)$ 成分は、$v_i$ から $v_j$ への長さ $k$ の有向歩道の個数に等しい。ただし $M^0$ は 単位行列 とする。
$v_i$ から $v_j$ への長さ $k$ の有向歩道の個数を $w_k(i,j)$ とおき、$k$ についての帰納法で $(M^k)_{ij}=w_k(i,j)$ を示す。$k=0$ のとき、長さ $0$ の有向歩道は 1 頂点だけの列 $v_i$ なので、$w_0(i,j)$ は $i=j$ なら $1$、そうでなければ $0$ であり、単位行列の成分に一致する。
$k$ で成り立つとする。$v_i$ から $v_j$ への長さ $k+1$ の有向歩道 $v_i=x_0,x_1,\dots,x_{k+1}=v_j$ は、最後から 2 番目の頂点 $x_k=v_l$ によって分類でき、長さ $k$ の有向歩道 $x_0,\dots,x_k$（$v_i$ から $v_l$ へ）と有向辺 $(v_l,v_j)\in A$ の組と 1 対 1 に対応する。$v_l$ を固定したときのその個数は $w_k(i,l)\,m_{lj}$ である（$m_{lj}\in\{0,1\}$）。したがって
$$w_{k+1}(i,j)=\sum_{l=1}^{n}w_k(i,l)\,m_{lj}=\sum_{l=1}^{n}(M^k)_{il}\,m_{lj}=(M^{k+1})_{ij}$$
である。$\square$
この命題から、$v_j$ が $v_i$ から到達可能であることは、ある $k$ について $(M^k)_{ij}\ge1$ となることと同値であり、$k\le n-1$ の範囲を調べれば足りる（$i\ne j$ なら有向道の長さは $n-1$ 以下なので）。とくに $D$ が非巡回であることは $M$ が 冪零行列 であること（$M^n=0$）と同値である。実際、非巡回なら有向歩道は有向道で（頂点が繰り返すと、その間から有向閉路が取り出せる）、長さ $n$ の有向道はない。逆に長さ $\ell$ の有向閉路 $v_i,\dots,v_i$ があれば、それを $m$ 回続けてたどると長さ $m\ell$ の有向歩道になるので、$m\ell\ge n$ となる $m$ について $(M^{m\ell})_{ii}\ge1$ である。$M^n=0$ なら $k\ge n$ のすべてで $M^k=0$ であり、$(M^{m\ell})_{ii}\ge1$ に反する。したがって有向閉路があれば $M^n\ne0$ である。
補足
- 無向グラフとの関係：単純無向グラフは、ループなしの対称な有向グラフと同一視できる（def-directed-graph-underlying の直後）。この同一視のもとで、無向グラフの連結性は強連結性と一致する。無向の歩道は両向きの有向辺をたどる有向歩道だからである。ただし閉路については、無向グラフの辺 $uv$ に対応する $(u,v),(v,u)$ が長さ $2$ の有向閉路をなすので、閉路の概念は一致しない。
- 次数：頂点 $v$ の出次数 $|N^+_D(v)|$・入次数 $|N^-_D(v)|$ とその性質は 次数(グラフ) の記事で扱われている。
- 応用：非巡回有向グラフは作業の前後関係、半順序の Hasse図、計算の依存関係を表す。有限の 半順序集合 $(P,\le)$ の順序関係から反射的な対 $(p,p)$ を除いた有向グラフは非巡回であり、その位相的順序は $\le$ を拡張する 全順序（線形拡大）にほかならない。重みつきの有向グラフでは 最短路問題 や ネットワークフロー が論じられる（BJG09 第 3 章・第 4 章）。
- 文献：本記事の用語はおおむね BJG09 第 1 章・第 2 章と Wes01 §1.4 に従い、多重有向グラフとしての定義は Die17 §1.10 を参照した。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
