- ベストアンサー
「木は２部グラフである。」を証明して下さい！
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
お気に召さない？ 自明すぎて困っちゃうんですが、そうだな、木のノードが奇数番目と偶数番目に分けられる。つまりノードに赤と青の色を付けて、どの辺も一端が赤、他端が青のノードを繋ぐようにできる。 どれでも良いから一つノードを選んで赤にする。 これに辺１本で繋がっている全てのノードを青にする。 青のノードに辺１本で繋がっている全てのノードを赤にする。 これを繰り返せば、木は連結しているから全てのノードに色が付きます。 次に、木はループがないから、一度赤がついたノードは何度色を塗っても赤ですし、青がついたノードは青。 これなら証明っぽいですか？
その他の回答 (1)
- stomachman
- ベストアンサー率57% (1014/1775)
２部グラフ：ノードを二つの部分集合A,Bに分けて、どの辺も一端をAに他端をBに持つようにできること。 木が２部グラフであることは、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明。 背理法？ 木が２部グラフでないとすると、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明であることと矛盾する。QED
関連するQ&A
- グラフ理論（木について）の証明
2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？ ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 （もし、点の個数を使うときはn，辺の個数はeを用いて教えてください） よろしくお願いします。
- 締切済み
- 数学・算数
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- グラフ理論においての「木」
（１）木はすべて二部グラフであることを証明せよ。 （２）どのような木が完全二部グラフとなるか？ についてそれぞれしりたいのですが・・・。（１）は自明なような気がしますが、きちんとした証明方法が知りたいです。片方だけでもいいのでお願いしますm(__)m
- ベストアンサー
- 数学・算数
- 完全グラフが平面的となるための証明について
完全グラフKnと完全２部グラフKn,mが平面的となるためのn,mの範囲を求め、証明せよ。 という問題があるのですが証明が分かりません。 完全グラフはn≦4、完全グラフ２部グラフはn=1 or 2。 どなたか証明を教えてください。
- ベストアンサー
- 数学・算数
- Ｋ_nの全域木の数の証明
Ｋ_nはn点からなるグラフ（図形）で、ある任意の点は自分自身以外の点と辺で結ばれています。つまり各辺の次数がn-1のグラフです。 このグラフの全域木の数は一般的にn^(n-2)個であることが知られているそうなのですが、どう証明すればいいでしょうか。 全域木とは、全ての点を通る「木」のことです。つまり全ての点と点を結びつけつつも閉路が存在しないようなグラフのことをいいます。 どなたか分かる方、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 【グラフ理論】証明問題が分かりません。【難問】
テストに向けてグラフ理論の勉強をしているのですが・・・ 下記の証明問題で行き詰まってしまいました。 『uv ∉ E(G) → uw ∉ E(G)というグラフは完全K部グラフしか存在しない事を証明せよ。』 当方、証明問題に滅法弱く、どう解けば良いのか方針すら分かりません。 方針や証明の過程など詳しくご教授して頂ければ幸いです。 何卒宜しくお願い致します。
- 締切済み
- 数学・算数
- グラフ理論の木（tree,木構造,樹木）について
グラフ理論でいう木（[木構造][tree][樹木]）のグラフにおいて、「点数が７の木」の種類が一体何種類あるのかがわかりません。 どなたかわかる方いたら教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 木の２つまたは３つの中心の求め方と証明(特に証明）
１．木の１つの中心の求め方 解．端点を削っていくやり方で求められます。 ２．木の２つの中心の求め方 解．１．で求めた中心を通る線を取り、 ２つの木にする。 その２つの木の中心（２つ）がそのまま解になります。 ３．木の３つの中心の求め方 解．２．で求めた中心を通る線(２本）を取り、 ３つの木にする。 その３つの木の中心（３つ）がそのまま解になります。 ２．と３．の証明を教えてください。
- 締切済み
- 数学・算数
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
