置換グラフのソースを表示

[[Image:Permutation graph.svg|thumb|300px|置換 (4,3,5,1,2)に対応するマッチングの図。下はその置換。置換時に交差する線が、頂点の隣接関係と一致している]]

'''置換グラフ'''（ちかんグラフ、{{Lang-en-short|permutation graph}}）もしくは'''順列グラフ'''（じゅんれつグラフ）とは、それぞれの頂点が[[置換_(数学)|置換]]の要素に対応し、それぞれの辺がその入れ替えに対応するグラフである。
置換グラフは幾何的にも定義でき、図のように置換時に交差する線が、頂点の隣接関係と一致するグラフである。異なる置換が同じ置換グラフを持つ場合があるが、モジュラー分解が素であれば置換グラフは（対称なものを除き）一意となる<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, p.191.</ref>。

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

置換グラフは、以下のような同値な特徴を持つ。
グラフ ''G'' が置換グラフであれば、そしてその時に限り
* ''G'' はcircle graphであり、他のすべての弦と交差する追加の弦「赤道」を認める <ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, Proposition&nbsp;4.7.1, p.57.</ref>。
* ''G'' とその補グラフ<math>\overline{G}</math> が「比較可能グラフ」である<ref>{{harvtxt|Dushnik||Miller|1941}}.</ref>
* 高々2のorder dimension を持つ[[順序集合|半順序集合]]の比較可能グラフ[[comparability graph]]である<ref>{{harvtxt|Baker|Fishburn|Roberts|1971}}.</ref>
グラフ ''G'' が置換グラフであれば
* 補グラフも置換グラフである。

==効率的なアルゴリズム==
与えられたグラフが置換グラフであるかを判定し、もし置換グラフであればその置換を導出する処理は、線形時間で処理可能である<ref>{{harvtxt|McConnell|Spinrad|1999}}</ref>。

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

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

==他のグラフとの関連==
* 置換グラフは[[circle graph]]の特殊な例である。
* 置換グラフは[[比較可能グラフ]]の特殊な例である。
* 置換グラフは[[比較可能グラフ]]の補グラフの特殊な例である。
* 置換グラフは[[台形グラフ]]の特殊な例である。

置換グラフは[[2部グラフ]]やcographなどの派生がある(詳しくは <ref>{{harvtxt|Spinrad|Brandstädt|Stewart|1987}}</ref>)。

==注釈・出典==
{{reflist|2}}

==参考文献==
*{{citation
 | last1 = Baker | first1 = K. A.
 | last2 = Fishburn | first2 = P. | author2-link = Peter C. Fishburn
 | last3 = Roberts | first3 = F. S. | author3-link = Fred S. Roberts
 | doi = 10.1002/net.3230020103
 | issue = 1
 | journal = Networks
 | pages = 11–28
 | title = Partial orders of dimension 2
 | volume = 2
 | year = 1971}}.
*{{citation
 | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender
 | last2 = Kloks | first2 = Ton
 | last3 = Kratsch | first3 = Dieter
 | doi = 10.1137/S089548019223992X
 | issue = 4
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | pages = 606–616
 | title = Treewidth and pathwidth of permutation graphs
 | volume = 8
 | year = 1995}}.
*{{citation
 | last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt
 | last2 = Le | first2 = Van Bang
 | last3 = Spinrad | first3 = Jeremy
 | title = Graph Classes: A Survey
 | publisher = SIAM Monographs on Discrete Mathematics and Applications
 | year = 1999
 | isbn = 0-89871-432-X}}.
*{{citation
 | doi = 10.2307/2371374
 | last1 = Dushnik | first1 = Ben
 | last2 = Miller | first2 = E. W.
 | title = Partially ordered sets
 | journal = [[American Journal of Mathematics]]
 | volume = 63 | issue = 3 | year = 1941 | pages = 600–610
 | jstor = 2371374}}.
*{{citation|first=M. C.|last=Golumbic|authorlink=Martin Charles Golumbic|title=Algorithmic Graph Theory and Perfect Graphs|series=Computer Science and Applied Mathematics|publisher=Academic Press|year=1980|page=159}}.
*{{citation
 | last1 = McConnell | first1 = Ross M.
 | last2 = Spinrad | first2 = Jeremy P.
 | doi = 10.1016/S0012-365X(98)00319-7
 | issue = 1-3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1687819
 | pages = 189–241
 | title = Modular decomposition and transitive orientation
 | volume = 201
 | year = 1999}}.
*{{citation
 | last1 = Spinrad | first1 = Jeremy P.
 | last2 = Brandstädt | first2 = Andreas
 | last3 = Stewart | first3 = Lorna K.
 | journal = [[Discrete Applied Mathematics (journal)|Discrete Applied Mathematics]]
 | pages = 279–292
 | title = Bipartite permutation graphs
 | volume = 18
 | year = 1987}}.

== 外部リンク ==
* {{citation | contribution-url = http://www.graphclasses.org/classes/gc_23.html
 | contribution = Permutation graph
 | url = http://www.graphclasses.org/index.html
 | title = Information System on Graph Classes and their Inclusions}}
* {{mathworld|id=PermutationGraph|title=Permutation Graph}}

{{デフォルトソート:ちかんくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]