試験問題の範囲内の問題なのですが、解答が無いので教えてください。

n個の頂点を持つ有限グラフGに対し、次は同値である。
(ⅰ)Gは木である。
(ⅱ)Gはサイクルを持たず、n-1本の辺を持つ。
(ⅲ)Gは連結であり、n-1本の辺を持つ。

 (1)(ⅰ)→(ⅱ)
 (2)(ⅱ)→(ⅲ)
 (3)(ⅲ)→(ⅰ)

個の3問の問題をどうかお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (1件)

(a)Gは木である。

(サイクルがなく連結)
(b)Gはサイクルを持たず、n-1本の辺を持つ。
(c)Gは連結であり、n-1本の辺を持つ。

a->b,a->c
木だからサイクルがなく連結。辺の数をmとする。端点(辺1本しかない)とその辺を取っても木であるから、n-mは一定。この操作を繰り返すと、孤立点が残る。よってn-m=1。

b->c
サイクルがなくn-1本の辺を持ち、連結でないとする。適当に辺を加えて連結すればこれは木で、辺の数>n-1。一方木ならm=n-1のはずで、矛盾。
c->b
連結でn-1本の辺を持ち、サイクルがあるとする。サイクルを構成する辺の一つを取ればサイクルはなくなり、連結でサイクルがないからこれは木で、辺の数<n-1。一方木ならm=n-1のはずで、矛盾。

b->a
サイクルがなくn-1本の辺を持てばb->cにより連結であるから、木。

こんなのでOK?
    • good
    • 0
この回答へのお礼

とてもわかりやすい説明で助かりました、どうもありがとうございました。

お礼日時:2001/02/01 02:23

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

おすすめ情報