木と探索 木の種類 木の性質 閉路、連結
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、8.1(木の種類)、8.1.5(木の性質)、問の8.5の解答を求めてみる。
仮定より、Gは閉路ではない。
また、隣接しない2頂点間に辺を加えると閉路ができるので加えた辺を取り除いたGは連結である。
よってGは木である。
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、8.1(木の種類)、8.1.5(木の性質)、問の8.5の解答を求めてみる。
仮定より、Gは閉路ではない。
また、隣接しない2頂点間に辺を加えると閉路ができるので加えた辺を取り除いたGは連結である。
よってGは木である。