計算機科学のブログ

グラフの基礎グラフの連結性部分グラフと誘導部分グラフ頂点と辺、包含関係

本の表紙

情報系のための離散数学
 楽天ブックス
Yahoo!ショッピング
au PAY マーケット

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第7章(グラフの基礎)、7.2(グラフの連結性)、7.2.1(部分グラフと誘導部分グラフ)、問7.7の解答を求めてみる。

部分グラフ。

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

これが誘動部分グラフではないことについて。

\begin{array}{l} {a, c} \in E_{7} \\ {a, c} \notin E_{0} \end{array}

誘動部分グラフ。

\begin{array}{l} V_{1} = {a, b, c} \\ E_{1} = {{a, b}, {b, c}, {c, a}} \\ G = (V_{1}, E_{1}) \end{array}

これが実際に誘動で1分グラフであることの確認。

{a, b}, {a, c}, {b, c} \in E_{1}