-PR-
解決済み

「木は2部グラフである。」を証明して下さい!

  • 暇なときにでも
  • 質問No.34135
  • 閲覧数1264
  • ありがとう数6
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 33% (6/18)

「木は2部グラフである。」
これを証明して欲しいのです。
出来れば背理法で。
よろしくお願いします。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

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

  • 回答No.2
レベル14

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

お気に召さない?
自明すぎて困っちゃうんですが、そうだな、木のノードが奇数番目と偶数番目に分けられる。つまりノードに赤と青の色を付けて、どの辺も一端が赤、他端が青のノードを繋ぐようにできる。

どれでも良いから一つノードを選んで赤にする。
これに辺1本で繋がっている全てのノードを青にする。
青のノードに辺1本で繋がっている全てのノードを赤にする。

これを繰り返せば、木は連結しているから全てのノードに色が付きます。
次に、木はループがないから、一度赤がついたノードは何度色を塗っても赤ですし、青がついたノードは青。

これなら証明っぽいですか?
-PR-
-PR-

その他の回答 (全1件)

  • 回答No.1
レベル14

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

2部グラフ:ノードを二つの部分集合A,Bに分けて、どの辺も一端をAに他端をBに持つようにできること。

木が2部グラフであることは、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明。

背理法?
木が2部グラフでないとすると、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明であることと矛盾する。QED


このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

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

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

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ