-PR-
解決済み

情報数学の問題。

  • すぐに回答を!
  • 質問No.34144
  • 閲覧数101
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

お礼率 33% (6/18)

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

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

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

個の3問の問題をどうかお願いします。
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル14

ベストアンサー率 57% (1014/1775)

(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?
お礼コメント
lampes

お礼率 33% (6/18)

とてもわかりやすい説明で助かりました、どうもありがとうございました。
投稿日時 - 2001-02-01 02:23:11
関連するQ&A
-PR-
-PR-
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


新大学生・新社会人のパソコンの悩みを解決!

いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ