計算機科学のブログ

木と探索 単純グラフ、連結グラフ、全域木、必要十分条件、閉路

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、章末問題8.4の解答を求めてみる。

単純グラフ G が連結グラフとする.

閉路を含まないならば、Gは全域木である。

閉路を含むならば、閉路がなくなるまで出てたにり除いたものは全域木となる。

よって、Gは全域木である。

逆にGが全域木を含むならば、Gは連結グラフである。