順列グラフ

数学のグラフ理論の分野において、順列グラフとは、頂点が順列の要素を表し、辺が順列によって反転された要素のペアを表すグラフである。順列グラフは、端点が2本の平行線上にある線分の交差グラフとして幾何学的に定義されることもある。異なる順列から同じ順列グラフが生じることもある。与えられたグラフは、モジュラー分解に関して素であれば、 （順列対称性を除いて）一意の表現を持つ。^[1]

が からまでの数の任意の順列である場合、 には頂点があり、の前に が現れる任意の2 つのインデックスに対して辺が存在する、 からの順列グラフを定義できます。つまり、2 つのインデックスと は、順列の 反転を決定するのとまったく同じときに、順列グラフの辺を決定します。${\displaystyle \rho =(\sigma _{1},\sigma _{2},...,\sigma _{n})}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle \sigma}$${\displaystyle n}$ ${\displaystyle v_{1},v_{2},...,v_{n}}$${\displaystyle v_{i}v_{j}}$${\displaystyle i<j}$${\displaystyle j}$${\displaystyle i}$${\displaystyle \rho}$${\displaystyle i}$${\displaystyle j}$

順列 が与えられた場合、 となる端点がおよびである線分の集合を決定することもできます。これらの線分の端点は 2 本の平行線および上にあり、2 つの線分の交差が空でない場合、および が順列 の反転に対応する場合のみ、それらの線分は交差します。したがって、 の順列グラフは線分の交差グラフと一致します。任意の 2 本の平行線、および両方の線上に端点がある線分の任意の有限集合について、線分の交差グラフは順列グラフです。線分の端点がすべて異なる場合、それが順列グラフである順列は、2 本の線のうちの 1 本上の線分に連続した番号を付け、線分の端点がもう一方の線に現れる順序でこれらの番号を読み取ることによって与えられます。 ${\displaystyle \sigma}$ ${\displaystyle s_{i}}$${\displaystyle (i,0)}$${\displaystyle (k,1)}$${\displaystyle \sigma _{k}=i}$${\displaystyle y=0}$${\displaystyle y=1}$${\displaystyle \sigma}$

順列グラフには、他にも同等の特性がいくつかあります。

• グラフが順列グラフである場合、かつそのグラフが赤道、つまり他のすべての弦と交差する追加の弦を許容する円グラフである場合に限ります。 ^[2]${\displaystyle G}$${\displaystyle G}$
• グラフが順列グラフである場合、そしてその補グラフが比較可能性グラフである場合に限ります。^[3]${\displaystyle G}$${\displaystyle G}$ ${\displaystyle {\overline {G}}}$
• グラフが順列グラフとなるのは、順序次元が最大2である部分順序集合の比較可能性グラフである場合に限ります。^[4]${\displaystyle G}$
• グラフが順列グラフである場合、その補グラフも順列グラフです。 の補グラフを表す順列は、を表す順列を逆にすることで得られます。${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

与えられたグラフが順列グラフであるかどうかをテストし、そうであればそれを表す順列を線形時間で構築することが可能である。^[5]

完全グラフのサブクラスとして、任意のグラフに対してNP 完全である多くの問題は、順列グラフに対して効率的に解決できます。たとえば、

• 順列グラフにおける最大のクリークは、グラフを定義する順列における最長減少部分列に対応するため、クリーク問題は、最長減少部分列アルゴリズムを使用することで、順列グラフに対して多項式時間で解決できる可能性がある。^[6]
• 同様に、順列内の増加する部分列は、対応する順列グラフ内の同じサイズの独立集合に対応します。
• 順列グラフのツリー幅とパス幅は多項式時間で計算できる。これらのアルゴリズムは、順列グラフ内の包含最小頂点セパレータの数がグラフのサイズの多項式であるという事実を利用している。^[7]

順列グラフは、円グラフ、比較可能性グラフ、比較可能性グラフの補グラフ、台形グラフの特殊なケースです。

順列グラフのサブクラスには、二部順列グラフ（Spinrad、Brandstädt、Stewart 1987 によって特徴付けられる）とコグラフが含まれます。

• ベイカー、カービー A.;フィッシュバーン、ピーター C .;ロバーツ、フレッド S. (1971)、「2 次元の部分順序」、ネットワーク、2 (1): 11–28、doi :10.1002/net.3230020103。
• Bodlaender, Hans L. ; Kloks, Ton; Kratsch, Dieter (1995)、「順列グラフのツリー幅とパス幅」、SIAM Journal on Discrete Mathematics、8 (4): 606–616、doi :10.1137/S089548019223992X、hdl : 1874/16657。
• Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy P. (1999)、「グラフクラス：概要」、SIAM Monographs on Discrete Mathematics and Applications、ISBN 0-89871-432-X。
• ダシュニク、ベン; ミラー、エドウィン W. (1941)、「部分順序集合」、アメリカ数学誌、63 (3): 600–610、doi :10.2307/2371374、JSTOR  2371374。
• ゴルビック、マーティン C. (1980)、「アルゴリズムグラフ理論と完全グラフ」、コンピュータサイエンスと応用数学、アカデミックプレス、p. 159。
• McConnell, Ross M.; Spinrad, Jeremy P. (1999)、「モジュラー分解と推移的指向」、離散数学、201 (1–3): 189–241、doi :10.1016/S0012-365X(98)00319-7、MR  1687819。
• スピンラッド、ジェレミー P.;ブランドシュテット、アンドレアス;スチュワート、ローナ K. (1987)、「二部順列グラフ」、離散応用数学、18 (3): 279–292、doi : 10.1016/s0166-218x(87)80003-3。

• 「順列グラフ」、グラフクラスとその包含に関する情報システム
• ワイスタイン、エリック W.、「順列グラフ」、MathWorld