グラフの基礎有向グラフ有向グラフの用語有向辺、頂点、始点と終点、弧、入次数、出次数、形式的定義

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第7章(グラフの基礎)、7.3(有向グラフ)、7.3.1(有向グラフの用語)、問7.15の解答を求めてみる。

問題の有向グラフの形式的定義。

\begin{array}{l} G_{10} = (V_{10}, E_{10}) \\ V_{10} = {a, b, c, d, b} \\ E_{10} = {(a, b), \\ (b, a), (b, c), \\ (c, d), \\ (d, e), \\ (e, b), (e, c)} \end{array}

各頂点の入次数と出次数。

\begin{array}{l} \deg_{G}^{+} (a) = 1 \\ \deg_{G}^{+} (b) = 2 \\ \deg_{G}^{+} (c) = 2 \\ \deg_{G}^{+} (d) = 1 \\ \deg_{G}^{+} (e) = 1 \end{array}

\begin{array}{l} \deg_{G}^{-} (a) = 1 \\ \deg_{G}^{-} (b) = 2 \\ \deg_{G}^{-} (c) = 1 \\ \deg_{G}^{-} (d) = 1 \\ \deg_{G}^{-} (e) = 2 \end{array}