置換グラフ

置換グラフ（ちかんグラフ、英: permutation graph）もしくは順列グラフ（じゅんれつグラフ）とは、それぞれの頂点が置換の要素に対応し、それぞれの辺がその入れ替えに対応するグラフである。置換グラフは幾何的にも定義でき、図のように置換時に交差する線が、頂点の隣接関係と一致するグラフである。異なる置換が同じ置換グラフを持つ場合があるが、モジュラー分解が素であれば置換グラフは（対称なものを除き）一意となる^[1]。

定義と特徴

σ = (σ₁,σ₂, ..., σ_n) を 1から n までの置換とすると、 n 頂点（v₁, v₂, ..., v_n）の置換グラフを定義できる。 i < j であり σ_i > σ_jであるとき、 v_iv_j に辺を有するグラフが置換グラフとなる。つまり、 i と j の大小関係が入れ替わっているような組に対して、置換グラフは辺を有する。置換σが与えられると、( i, 0) から (σ_i, 1)へと伸びる線分 s_iが定義できる。線分の端点は2本の平行な線 y = 0 （置換前）と y = 1 （置換後）上にあり、2つの要素が順列の反転に対応する場合に限り、交点が生じる。したがって、σの置換グラフは要素の交差グラフと一致する。線分の終点が全て異なる場合、置換グラフで定義された置換は、2つの線のうちの1つの線上のセグメントに連続した番号を付け（図中の上の12345）、もう一方の線上での、線分のもう一方の端点の数字が置換後の数列（43512）となる。

置換グラフは、以下のような同値な特徴を持つ。グラフ G が置換グラフであれば、そしてその時に限り

G はcircle graphであり、他のすべての弦と交差する追加の弦「赤道」を認める ^[2]。
G とその補グラフ ${\overline {G}}$ が「比較可能グラフ」である^[3]
高々2のorder dimension を持つ半順序集合の比較可能グラフcomparability graphである^[4]

グラフ G が置換グラフであれば

補グラフも置換グラフである。

効率的なアルゴリズム

与えられたグラフが置換グラフであるかを判定し、もし置換グラフであればその置換を導出する処理は、線形時間で処理可能である^[5]。

一般のグラフに対してはNP-完全であるような問題に対しても、入力が置換グラフであれば、パーフェクトグラフの一種として、効率的なアルゴリズムが存在する場合がある。

置換グラフの最大クリークはグラフを定義する順列の最長増加（減少）部分列に対応するため、最長増加（減少）部分列を導出するアルゴリズムを使用して、置換グラフの最大クリーク問題を多項式時間で解くことが可能。^[6]
同様に、置換において増加部分列は、対応する置換グラフにおける同じサイズの独立集合に対応する。
置換グラフの木幅とパス幅は多項式時間で計算できる。そのアルゴリズムは、頂点分離の数がグラフのサイズの多項式で表されることに由来する^[7]。

他のグラフとの関連

置換グラフはcircle graphの特殊な例である。
置換グラフは比較可能グラフの特殊な例である。
置換グラフは比較可能グラフの補グラフの特殊な例である。
置換グラフは台形グラフの特殊な例である。

置換グラフは2部グラフやcographなどの派生がある(詳しくは ^[8])。

注釈・出典

^ Brandstädt, Le & Spinrad (1999), p.191.
^ Brandstädt, Le & Spinrad (1999), Proposition 4.7.1, p.57.
^ Dushnik, & Miller (1941).
^ Baker, Fishburn & Roberts (1971).
^ McConnell & Spinrad (1999)
^ Golumbic (1980).
^ Bodlaender, Kloks & Kratsch (1995)
^ Spinrad, Brandstädt & Stewart (1987)

参考文献

Baker, K. A.; Fishburn, P.; Roberts, F. S. (1971), “Partial orders of dimension 2”, Networks 2 (1): 11–28, doi:10.1002/net.3230020103 .
Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter (1995), “Treewidth and pathwidth of permutation graphs”, SIAM Journal on Discrete Mathematics 8 (4): 606–616, doi:10.1137/S089548019223992X .
Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X .
Dushnik, Ben; Miller, E. W. (1941), “Partially ordered sets”, American Journal of Mathematics 63 (3): 600–610, doi:10.2307/2371374, JSTOR 2371374, https://jstor.org/stable/2371374 .
Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, p. 159 .
McConnell, Ross M.; Spinrad, Jeremy P. (1999), “Modular decomposition and transitive orientation”, Discrete Mathematics 201 (1-3): 189–241, doi:10.1016/S0012-365X(98)00319-7, MR1687819 .
Spinrad, Jeremy P.; Brandstädt, Andreas; Stewart, Lorna K. (1987), “Bipartite permutation graphs”, Discrete Applied Mathematics 18: 279–292 .

外部リンク

[1] Brandstädt, Le & Spinrad (1999), p.191.

[2] Brandstädt, Le & Spinrad (1999), Proposition 4.7.1, p.57.

[3] Dushnik, & Miller (1941).

[4] Baker, Fishburn & Roberts (1971).

[5] McConnell & Spinrad (1999)

[6] Golumbic (1980).

[7] Bodlaender, Kloks & Kratsch (1995)

[8] Spinrad, Brandstädt & Stewart (1987)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]