No.1
- 回答日時:
2部グラフ:ノードを二つの部分集合A,Bに分けて、どの辺も一端をAに他端をBに持つようにできること。
木が2部グラフであることは、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明。
背理法?
木が2部グラフでないとすると、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明であることと矛盾する。QED
No.2ベストアンサー
- 回答日時:
お気に召さない?
自明すぎて困っちゃうんですが、そうだな、木のノードが奇数番目と偶数番目に分けられる。つまりノードに赤と青の色を付けて、どの辺も一端が赤、他端が青のノードを繋ぐようにできる。
どれでも良いから一つノードを選んで赤にする。
これに辺1本で繋がっている全てのノードを青にする。
青のノードに辺1本で繋がっている全てのノードを赤にする。
これを繰り返せば、木は連結しているから全てのノードに色が付きます。
次に、木はループがないから、一度赤がついたノードは何度色を塗っても赤ですし、青がついたノードは青。
これなら証明っぽいですか?
お探しの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乗のグラフ
-
f(x)=sin(1/x)(xは0以外)を0に...
-
「グラフの概形を描け」と「グ...
-
Maximaでグラフをコピペする方法
-
eのx乗のグラフはどうやって書...
-
積分の面積を求める問題で 上−...
-
-b/2aが2次関数の軸?になる理...
-
なぜ(3)では(1)と(2)同様...
-
grape でグラフの範囲どう指定...
-
2点集中荷重片持ち梁について
-
有理関数のグラフの質問です
-
増減表について
-
高一の数学です。 -x² + 4x -...
-
スプライン曲面をつくるプログラム
-
expという理解できない記号があ...
-
Xについての方程式|x²-1|+x=Kが...
-
関数の極限について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
積分の面積を求める問題で 上−...
-
天孫降臨の神武天皇のY染色体...
-
関数のグラフでy'''はなにを意...
-
タンジェントとアークタンジェ...
-
4乗のグラフ
-
数学の質問です。分数関数の分...
-
数3 関数の極限 どういう問題の...
-
ゴンペルツ曲線の式
-
増減表について
-
グラフの類似度について
-
10の1.2乗が、なぜ16になるのか...
-
「2次不等式2x²+3x+m+1<0を満た...
-
4次関数のグラフの概形は「極大...
-
関数の極限について
-
数学
-
2点集中荷重片持ち梁について
-
-b/2aが2次関数の軸?になる理...
-
関数f(x)=x3乗−ax2条+(1-2a)x+4...
-
EXCELで緯度、経度を入力して、...
-
「グラフの概形を描け」と「グ...
おすすめ情報