![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
No.2ベストアンサー
- 回答日時:
お気に召さない?
自明すぎて困っちゃうんですが、そうだな、木のノードが奇数番目と偶数番目に分けられる。つまりノードに赤と青の色を付けて、どの辺も一端が赤、他端が青のノードを繋ぐようにできる。
どれでも良いから一つノードを選んで赤にする。
これに辺1本で繋がっている全てのノードを青にする。
青のノードに辺1本で繋がっている全てのノードを赤にする。
これを繰り返せば、木は連結しているから全てのノードに色が付きます。
次に、木はループがないから、一度赤がついたノードは何度色を塗っても赤ですし、青がついたノードは青。
これなら証明っぽいですか?
No.1
- 回答日時:
2部グラフ:ノードを二つの部分集合A,Bに分けて、どの辺も一端をAに他端をBに持つようにできること。
木が2部グラフであることは、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明。
背理法?
木が2部グラフでないとすると、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明であることと矛盾する。QED
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 グラフ理論の用語について 1 2022/09/16 19:50
- Excel(エクセル) エクセルで、未来の月の数値を表示させないようにしたい 1 2022/05/07 18:58
- 数学 三角関数の和 4 2023/06/17 18:33
- 数学 y=2^x と y=X で 2 2022/05/19 17:08
- Excel(エクセル) Excelの複合グラフ(棒グラフと折れ線グラフ)で各棒グラフに名称を表示させたい 1 2022/08/14 23:26
- 数学 『◯と●の帰納法』 2 2023/04/19 20:57
- 相続税・贈与税 不動産の相続についてですが 2 2023/05/04 11:33
- 計算機科学 エクセルのデータの表すことについて 2 2023/03/05 20:49
- Excel(エクセル) Excelグラフについて教えて下さい。 a1からz1までに計算式を入れてグラフにしました。 まだ値が 2 2022/12/01 14:22
- Excel(エクセル) Excelグラフについて 1 2022/06/16 16:06
このQ&Aを見た人はこんなQ&Aも見ています
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
関数のグラフでy'''はなにを意...
-
タンジェントとアークタンジェ...
-
二次関数のグラフを書く時、写...
-
極値と変曲点を同時に持つ点あ...
-
数学の質問です。分数関数の分...
-
4乗のグラフ
-
問題は「不等式ax²+y²+az²-xy-y...
-
積分の面積を求める問題で 上−...
-
「関数y=M(a)のグラフを書け」...
-
数学
-
三次関数のグラフ 微分した二次...
-
expという理解できない記号があ...
-
「木は2部グラフである。」を...
-
Xについての方程式|x²-1|+x=Kが...
-
「グラフの概形を描け」と「グ...
-
「f(x)とg(x)のグラフで囲まれ...
-
何故グラフを書く際に微分係数...
-
(m-1)(m-4)≧0からどうしてm≦1、...
-
2点集中荷重片持ち梁について
-
この漸近線の書き方教えてくだ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
関数のグラフでy'''はなにを意...
-
4乗のグラフ
-
タンジェントとアークタンジェ...
-
数学の質問です。分数関数の分...
-
数3 関数の極限 どういう問題の...
-
「グラフの概形を描け」と「グ...
-
積分の面積を求める問題で 上−...
-
極値と変曲点を同時に持つ点あ...
-
関数の極限について
-
関数の台というのはどこでも作...
-
10の1.2乗が、なぜ16になるのか...
-
中2数学 一次関数の問題を教え...
-
「2次不等式2x²+3x+m+1<0を満た...
-
-b/2aが2次関数の軸?になる理...
-
2点集中荷重片持ち梁について
-
【 数Ⅰ 2次関数 】 問題 関数y=...
-
三角関数 y=cos3θのグラフの書...
-
ゴンペルツ曲線の式
-
4次関数のグラフの概形は「極大...
-
対数の最小ニ乗法のやり方を教...
おすすめ情報