- グラフの辺が複数のクリーク（1つのクリークに対して辺重みはすべて同じ）で与えられる
- 辺の数がとても多いため、愚直に辺の重みでソートしてクラスカル法をするのは無理。
- 頂点の数 N に対して、N-1 本選ぶのではなく、K 本選ぶ場合も同様に解ける。
- 絶対使う→ないと最小性を満たさなくなる
- 最小全域木を1つ構成して候補を絞る
- 一般にn個の共通部分を求める問題では1つまたは2つの集合からかなり絞れることがある。
-
平面上のすべての領域にいけるように辺を除去するときの辺重み最小は？
-
双対グラフ（面を頂点としたグラフ）を考える