10.1 頂点の次数
有向グラフの頂点の入次数 (in-degree) とは、その頂点に向かう矢印の個数を言う。同様に、頂点の出次数 (out-degree) とは、その頂点から出る矢印の個数を言う。正確には次の通りである:
定義 10.1.1
有向グラフ \(G\) と \(v \in V(G)\) に対して、入次数 (in-degree) \(\operatorname{indeg}(v)\) と出次数 (out-degree) \(\operatorname{outdeg}(v)\) は次のように定義される:
\[ \begin{aligned} \operatorname{indeg}(v) &::= | \left\{ e \in \text{E}(G) \; | \; \operatorname{head}(e) = v \right\} | \\ \operatorname{outdeg}(v) &::= | \left\{ e \in \text{E}(G) \; | \; \operatorname{tail}(e) = v \right\} | \end{aligned} \]
この定義から次の系が直ちに得られる:
補題 10.1.2[握手補題 (handshaking lemma)]
\[ \sum_{v \in V(G)} \operatorname{indeg}(v) = \sum_{v \in V(G)} \operatorname{outdeg}(v) \]
証明 両辺とも \(| E(G) |\) に等しい。 ■