FC2ブログ

30分でできる日記

ぐらふ

(Th)
rを根とする整数重みの最小重み全域有効木問題の解は、存在するのならばどの枝eもweight(e)個以下しか含まれないような(重複を許す)r-cut列の長さの最大値に等しい

Fulkersonさんの示した命題(@1974)だそうだが、命題と証明のオラクルっぷりに思わず吹いた。TarjanさんやらEdmondsさんやら、グラフ理論やってる人には何か常人には見えないものが見えているようにしか見えない。
スポンサーサイト





  1. 2006/10/11(水) 00:32:53|
  2. プログラミング|
  3. トラックバック:0|
  4. コメント:0

はっぴょうしりょう | ホーム | ふぃぼなっち

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://henge.blog66.fc2.com/tb.php/58-017f7692

| ホーム |