パスワードを忘れた? アカウント作成
403446 journal
Linux

torlyの日記: よーしパパ隣接しちゃうぞー 2

日記 by torly
 点集合AとBがあり、同じ集合に属する点同士は辺で結ばれていないものとする。木の全ての点をAかBに振り分けられるなら、木は二部グラフであると言える。
 ある点v1∈A、v2と隣接する点v2∈Bとする。木の辺は全て橋なので、閉路は存在しない。故に、v2と隣接している点はv1とは隣接していない。よって、それらは全てAに入れる事が出来る。v1と隣接している点についても同様に、v2と隣接していないので、全てBに入れる事が出来る。これを繰り返せば、全ての点をAかBに入れる事が可能である。よって、木は二部グラフである。

 これで合ってるかなあ…

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by djahok (3730) on 2003年02月06日 20時33分 (#252811) 日記
    点の個数が非可算無限個だとヤバイですね。
    そんなものを"木"と呼ぶかは知りませんが。

    非可算無限個の場合はZornの補題でも使えばよろしいかと。
  • by Anonymous Coward on 2003年02月06日 7時35分 (#252188)
    定義より、木には cycle がない。よってK\"{o}nigの定理[1936](A graph is bipartite iff it has no odd cyle)より、木は二部グラフである。
typodupeerror

犯人はmoriwaka -- Anonymous Coward

読み込み中...