4.3. 部分有向グラフ

\(D=\left( V,A,\psi\right) \) を多重有向グラフとする。

1. \(D\) の部分多重有向グラフ (submultidigraph) とは、\(W\subseteq V\), \(B\subseteq A\), \(\chi=\psi |_{B}\) が成り立つような多重有向グラフ \(E=\left( W,B,\chi\right) \) を言う。部分多重有向グラフは単に部分有向グラフ (subdigraph) とも呼ぶ。

2. \(S\) を \(V\) の部分集合とする。集合 \(S\) に関する \(D\) の誘導部分有向グラフ (induced subdigraph of \(D\) on the set \(S\)) とは、次に示す \(D\) の部分有向グラフを言う:

   \[ \left( S,\ \ A^{\prime},\ \ \psi|_{A^{\prime}}\right) \]

   ここで \(A^{\prime}\) は次のように定義される:

   \[ A^{\prime}\colonequals \left\{ a\in A\mid a\text{ の始点と終点の両方が } S \text{ に属する}\right\} \]

3. \(D\) の誘導部分有向グラフ (induced subdigraph) とは、何らかの \(S \subseteq V\) に関する \(D\) の誘導部分有向グラフを意味する。