4.2. 有向グラフの入次数と出次数
目次
有向グラフで何ができるだろうか？ これまでに本書で説明してきたグラフに関する概念や性質の多くは、適切に改変すれば有向グラフに対しても考えることができる。例えば、グラフの頂点の次数に対応する概念として有向グラフには入次数と出次数がある:
定義 4.2.1
\(D\) を有向グラフ、\(V\) を \(D\) の頂点集合とする (\(D\) は単純有向グラフと多重有向グラフのどちらでも構わない)。\(v \in V\) を \(D\) の頂点とする。このとき:
-
\(v\) の出次数 (outdegree) とは、始点が \(v\) である \(D\) の弧の個数を意味する。\(v\) の出次数は \(\deg^{+}v\) と表記される。
-
\(v\) の入次数 (indegree) とは、終点が \(v\) である \(D\) の弧の個数を意味する。\(v\) の入次数は \(\deg^{-}v\) と表記される。
例 4.2.2
\(\left\{ 1,2,3,4,5,6\right\} \) 上の整除性有向グラフ (描画は例 4.1.3 を参照) では、次が成り立つ:
\[ \begin{aligned} \deg^{+}1 & =6,\quad \deg^{-}1=1,\quad \deg ^{+}2=3,\quad \deg^{-}2=2,\\ \deg^{+}3 & =2,\quad \deg^{-}3=2,\quad \deg ^{+}4=1,\quad \deg^{-}4=3,\\ \deg^{+}5 & =1,\quad \deg^{-}5=2,\quad \deg ^{+}6=1,\quad \deg^{-}6=4 \end{aligned} \]
全ての頂点の次数を足すと辺の個数の二倍になるという Euler による結果 (命題 3.3.2) を思い出してほしい。有向グラフでは次の命題が成り立つ:
命題 4.2.3
\(D\) を有向グラフ、\(V\) を \(D\) の頂点集合、\(A\) を \(D\) の弧集合とする。このとき次の等式が成り立つ:
\[ \sum_{v\in V}\deg^{+}v=\sum_{v\in V}\deg^{-}v=\left\vert A\right\vert \]
出次数の定義より、任意の頂点 \(v \in V\) で次の等式が成り立つ:
\[ \deg^{+}v= \left(\text{始点が } v \text{ である } D \text{ の弧の個数}\right) \]
ここから次の等式を得る:
\[ \begin{aligned} \sum_{v\in V}\deg^{+}v & =\sum_{v\in V}\left(\text{始点が } v \text{ である } D \text{ の弧の個数}\right) \\ & = \left(D \text{ の弧の個数}\right) \\ & \qquad \left( \begin{array}{cc} \because\ \text{全ての辺はちょうど一つの始点を持つので、}\\ \text{各辺は和の中で一度だけ数えられる}\end{array}\right) \\ & =\left\vert A\right\vert \end{aligned} \]
同様に \(\displaystyle \sum_{v\in V}\deg^{-}v=\left\vert A\right\vert \) も示せる。 □