置換グラフ

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