置換グラフ

置換グラフ（ちかんグラフ、）もしくは順列グラフ（じゅんれつグラフ）とは、それぞれの頂点が置換の要素に対応し、それぞれの辺がその入れ替えに対応するグラフである。
置換グラフは幾何的にも定義でき、図のように置換時に交差する線が、頂点の隣接関係と一致するグラフである。異なる置換が同じ置換グラフを持つ場合があるが、モジュラー分解が素であれば置換グラフは（対称なものを除き）一意となる。
定義と特徴.
σ = (σ1,σ2, ..., σ"n") を 1から "n" までの置換とすると、 "n" 頂点（"v"1, "v"2, ..., "v""n"）の置換グラフを定義できる。
"i" < "j" であり σ"i" > σ"j"であるとき、 "v""i""v""j" に辺を有するグラフが置換グラフとなる。つまり、 "i" と "j" の大小関係が入れ替わっているような組に対して、置換グラフは辺を有する。
置換σが与えられると、( "i", 0) から (σ"i", 1)へと伸びる線分 "si"が定義できる。 線分の端点は2本の平行な線 "y" = 0 （置換前）と "y" = 1 （置換後）上にあり、2つの要素が順列の反転に対応する場合に限り、交点が生じる。したがって、σの置換グラフは要素の交差グラフと一致する。線分の終点が全て異なる場合、置換グラフで定義された置換は、2つの線のうちの1つの線上のセグメントに連続した番号を付け（図中の上の12345）、もう一方の線上での、線分のもう一方の端点の数字が置換後の数列（43512）となる。
置換グラフは、以下のような同値な特徴を持つ。
グラフ "G" が置換グラフであれば、そしてその時に限り
グラフ "G" が置換グラフであれば
効率的なアルゴリズム.
与えられたグラフが置換グラフであるかを判定し、もし置換グラフであればその置換を導出する処理は、線形時間で処理可能である。
一般のグラフに対してはNP-完全であるような問題に対しても、入力が置換グラフであれば、パーフェクトグラフの一種として、効率的なアルゴリズムが存在する場合がある。
他のグラフとの関連.
置換グラフは2部グラフやcographなどの派生がある(詳しくは )。