2006-07-09から1日間の記事一覧

2.2 木、閉路、カット (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

グラフにおける閉路とカット 閉路はぐるっと一巡するタイプのグラフ 定義としては、点と辺を交互にたどってもとの点に戻ってくるような点と辺の集合である。ただし、このとき点と辺はそれぞれ1度ずつしか使用しないし、1度は使用するものとする。 カットは…