置換グラフ
σ = (σ1,σ2, ..., σn) を 1から n までの置換とすると、 n 頂点(v1, v2, ..., vn)の置換グラフを定義できる。 i < j であり σi > σjであるとき、 vivj に辺を有するグラフが置換グラフとなる。つまり、 i と j の大小関係が入れ替わっているような組に対して、置換グラフは辺を有する。 置換σが与えられると、( i, 0) から (σi, 1)へと伸びる線分 siが定義できる。 線分の端点は2本の平行な線 y = 0 (置換前)と y = 1 (置換後)上にあり、2つの要素が順列の反転に対応する場合に限り、交点が生じる。したがって、σの置換グラフは要素の交差グラフと一致する。線分の終点が全て異なる場合、置換グラフで定義された置換は、2つの線のうちの1つの線上のセグメントに連続した番号を付け(図中の上の12345)、もう一方の線上での、線分のもう一方の端点の数字が置換後の数列(43512)となる。
置換グラフは、以下のような同値な特徴を持つ。 グラフ G が置換グラフであれば、そしてその時に限り
G はcircle graphであり、他のすべての弦と交差する追加の弦「赤道」を認める 。
G とその補グラフ G ̄ {\displaystyle {\overline {G}}} が「比較可能グラフ」である
高々2のorder dimension を持つ半順序集合の比較可能グラフcomparability graphである
グラフ G が置換グラフであれば
補グラフも置換グラフである。
置換グラフ(ちかんグラフ、英: permutation graph)もしくは順列グラフ(じゅんれつグラフ)とは、それぞれの頂点が置換の要素に対応し、それぞれの辺がその入れ替えに対応するグラフである。 置換グラフは幾何的にも定義でき、図のように置換時に交差する線が、頂点の隣接関係と一致するグラフである。異なる置換が同じ置換グラフを持つ場合があるが、モジュラー分解が素であれば置換グラフは(対称なものを除き)一意となる。