
No.2ベストアンサー
- 回答日時:
お気に召さない?
自明すぎて困っちゃうんですが、そうだな、木のノードが奇数番目と偶数番目に分けられる。つまりノードに赤と青の色を付けて、どの辺も一端が赤、他端が青のノードを繋ぐようにできる。
どれでも良いから一つノードを選んで赤にする。
これに辺1本で繋がっている全てのノードを青にする。
青のノードに辺1本で繋がっている全てのノードを赤にする。
これを繰り返せば、木は連結しているから全てのノードに色が付きます。
次に、木はループがないから、一度赤がついたノードは何度色を塗っても赤ですし、青がついたノードは青。
これなら証明っぽいですか?
No.1
- 回答日時:
2部グラフ:ノードを二つの部分集合A,Bに分けて、どの辺も一端をAに他端をBに持つようにできること。
木が2部グラフであることは、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明。
背理法?
木が2部グラフでないとすると、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明であることと矛盾する。QED
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
三次関数のグラフ 微分した二次...
-
f(x)=sin(1/x)(xは0以外)を0に...
-
連続関数・・
-
数学の質問:関数の書き方
-
数3 関数の極限 どういう問題の...
-
f(x)>0とはどういうグラフなの...
-
合成関数
-
直線y=ax+bが2点P(1,-1)、Q(2,1...
-
数学の質問です。分数関数の分...
-
信号検出理論のグラフ作成方法...
-
「2次不等式2x²+3x+m+1<0を満た...
-
Lineweaver Burkの式のプロット...
-
数学2の問題です。 座標平面上...
-
数学
-
増減表について
-
grape でグラフの範囲どう指定...
-
三角関数のグラフについて
-
関数f(x)=x3乗−ax2条+(1-2a)x+4...
-
「グラフの概形を描け」と「グ...
-
片対数グラフを普通のグラフに...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の質問です。分数関数の分...
-
数3 関数の極限 どういう問題の...
-
数学の質問:関数の書き方
-
10の1.2乗が、なぜ16になるのか...
-
「グラフの概形を描け」と「グ...
-
タンジェントとアークタンジェ...
-
4乗のグラフ
-
ゴンペルツ曲線の式
-
積分の面積を求める問題で 上−...
-
関数の極限について
-
2点集中荷重片持ち梁について
-
極値と変曲点を同時に持つ点あ...
-
f(x)=sin(1/x)(xは0以外)を0に...
-
三角関数について。
-
三角関数 y=cos3θのグラフの書...
-
数学
-
直線y=ax+bが2点P(1,-1)、Q(2,1...
-
関数のグラフでy'''はなにを意...
-
増減表について
-
Lineweaver Burkの式のプロット...
おすすめ情報