- ベストアンサー
グラフ理論においての「木」
（１）木はすべて二部グラフであることを証明せよ。 （２）どのような木が完全二部グラフとなるか？ についてそれぞれしりたいのですが・・・。（１）は自明なような気がしますが、きちんとした証明方法が知りたいです。片方だけでもいいのでお願いしますm(__)m
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
木(tree)では、任意の2点は、一つの路(path)で結ばれているから、ある点から数えて奇数番目の点と偶数番目の点で二分割すれば、二部グラフになる。 木に含まれる路の長さが、2以内であれば完全二部グラフになる。
その他の回答 (1)
- Mell-Lily
- ベストアンサー率27% (258/936)
回答No.1
参考URLをご覧ください。
