情報数学の問題。

質問

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

ｎ個の頂点を持つ有限グラフＧに対し、次は同値である。
（ⅰ）Ｇは木である。
（ⅱ）Ｇはサイクルを持たず、ｎ－１本の辺を持つ。
（ⅲ）Ｇは連結であり、ｎ－１本の辺を持つ。

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

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

回答No.1

stomachman · ベストアンサー

（a）Ｇは木である。 （サイクルがなく連結）
（b）Ｇはサイクルを持たず、ｎ－１本の辺を持つ。
（c）Ｇは連結であり、ｎ－１本の辺を持つ。

a->b,a->c
木だからサイクルがなく連結。辺の数をmとする。端点（辺１本しかない）とその辺を取っても木であるから、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?

お礼

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