🔀

置換グラフ(permutation graph)を図で理解する：LIS/LDSとの関係

に公開
競プロ
アルゴリズム
グラフ
idea

こんにちは、だいくすとらです (≧▽≦)

今回は 置換グラフ (permutation graph) というやつを、図でさっくり紹介します！

ABC439E問題をやっていたら「これ置換グラフでの最大独立集合を求める問題じゃない？」となったので、それを紹介するための記事です〜

https://x.com/daikusutora3/status/2007728474933604409?s=20

0. 置換グラフってなに？（線分で表せるグラフ）

まず、置換（= 1〜n の並び替え）を 2 本の平行線の間に描きます。

  • 上の段：1,2,...,n を左から順に並べる（これは固定）
  • 下の段：置換 π = (π(1), π(2), ..., π(n)) を左から順に並べる
  • 同じ数字どうしを線で結ぶ
  • 線が交差したら、その 2 本に対応する頂点同士に辺を張る

この「線の交差関係」をそのままグラフにしたものが 置換グラフです。

置換グラフの定義（例）

1. 「交差する条件」は？

数字 a < b の 2 本の線分を考えます。

  • 上の段では a が左、b が右（これは固定）
  • 下の段で a が左、b が右 → 上下で順番が同じ → 交差しない
  • 下の段で a が右、b が左 → 上下で順番が逆 → 交差する

交差する条件

つまり小さい数 a が、下の段で大きい数 b より右に追いやられていたらクロスするということです。これは反転 (inversion) と呼び、以降この特性を使っていきます。

2. LIS（最長増加部分列）⇔ 最大独立集合（交差しない線の最大集合）

ここが一番嬉しさがあるところです。

下の段（置換）を左から見て、増加部分列（LIS）を取ることを考えます。

増加部分列を選ぶと、線が交差しない

増加部分列って「左から右に見たとき、値が増えていくように数字を拾う」ということなので、選んだ数字どうしについては

  • a<b なら、下の段でも a が b より左に出る

が必ず成り立ちます。すると

  • 上の段でも下の段でも順番が同じ
  • だから対応する線分は 交差しない

という関係になります。

置換グラフにおける LIS

交差しない集合 = グラフで「辺がない集合」

置換グラフでは「交差する ⇔ 辺がある」なので、交差しない集合は

  • 選んだ頂点同士に辺が一本もない

という状態です。これはグラフ用語で 独立集合 (independent set) と呼びます。

だから、置換 π から作った置換グラフを G とすると

  • LIS(π) の長さ ＝ G の 最大独立集合の大きさ

になります。

3. LDS（最長減少部分列）⇔ 最大クリーク（互いに交差する線の最大集合）

今度は 減少部分列（LDS）です。

減少部分列は「左から右に見たとき、値がどんどん小さくなるように拾う」ということなので、選んだ数字どうしについては

  • a<b なのに、下の段では b が a より左に出る

が必ず成り立ちます。つまり 順番が逆（反転） なので

  • 対応する線分は必ず 交差する

になります。

置換グラフにおける LDS

置換グラフでは「交差する ⇔ 辺がある」なので、

  • 選んだ頂点が全部つながってる

という状態であると言えます。これは クリーク (clique) と呼びます。よって

  • LDS(π) の長さ ＝ G の 最大クリークの大きさ

になります。

4. まとめ

置換 π から作る置換グラフ G では、

  • 最大独立集合の大きさ → LIS(π)
  • 最大クリークの大きさ → LDS(π)

という対応が成り立ちます。

そして LIS / LDS はどちらも有名なアルゴリズムで O(n log n) で求まるので、置換グラフでは「最大独立集合」「最大クリーク」が高速に求まるというのが嬉しいポイントです！（※わざわざグラフの辺を全部作らなくても、置換をそのまま LIS/LDS すればOKです）

Discussion