最新閲覧日:

「木は2部グラフである。」
これを証明して欲しいのです。
出来れば背理法で。
よろしくお願いします。

A 回答 (2件)

お気に召さない?


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

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

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

これなら証明っぽいですか?
    • good
    • 0

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



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

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

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

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ