連結グラフには全域木が必ず存在する

計算量

• 頂点の数を $N$、辺の数を $M$ とする
  • 辺の重みでソート: $O(M \log M)$
  • UF を使ったメインの部分: $O(M \alpha(N))$
    • $\alpha$ はアッカーマンの逆関数

問題

• ABC352 E - Clique Connect
  • グラフの辺が複数のクリーク（1つのクリークに対して辺重みはすべて同じ）で与えられる
  • 辺の数がとても多いため、愚直に辺の重みでソートしてクラスカル法をするのは無理。
• Q3. K 本の辺を選ぶ | アルゴ式
  • 頂点の数 N に対して、N-1 本選ぶのではなく、K 本選ぶ場合も同様に解ける。
• どの最小全域木にも含まれているような辺の本数（Q5. 絶対使う辺 (2) | アルゴ式）
  • 絶対使う→ないと最小性を満たさなくなる
  • 最小全域木を1つ構成して候補を絞る
    • 一般にn個の共通部分を求める問題では1つまたは2つの集合からかなり絞れることがある。
• 各辺はある最小全域木に含まれているか？
• Q6. グリッドグラフ (2) | アルゴ式

  • 平面上のすべての領域にいけるように辺を除去するときの辺重み最小は？

    

  • 双対グラフ（面を頂点としたグラフ）を考える

    • 双対グラフについては グラフ を参照

証明

• 「縮約」が使える？
  • Q2. 最小全域木 | アルゴ式 (解説)

最小全域木の応用

知りたい（最小全域木が求まると何が嬉しい？）