Граф перестановки

Нехай σ = (σ₁,σ₂, …, σ_n) — деяка перестановка чисел від 1 до n. Для σ граф перестановки має n вершин v₁, v₂, …, v_n і в цьому графі ребро v_iv_j існує для будь-яких двох індексів i та j, для яких i < j і σ_i > σ_j. Таким чином, для двох індексів i та j ребро в графі визначається точно так само, як визначається транспозиція в перестановці.

Якщо задано перестановку σ, можна визначити множину відрізків s_i з кінцевими точками (i,0) і (σ_i,1). Кінцеві точки цих відрізків розташовуються на двох паралельних прямих y = 0 і y = 1, і два відрізки мають непорожній перетин тоді і тільки тоді, коли вони відповідають інверсії в перестановці. Таким чином, граф перестановки для σ збігається з графом перетинів відрізків. Для будь-яких двох паралельних прямих і будь-якого скінченного набору відрізків з кінцями на цих прямих граф перетинів відрізків є графом перестановки. Якщо всі скінченні точки відрізків різні, перестановку, відповідну графу перестановки, можна отримати нумерацією відрізків на одній з прямих (послідовно, наприклад, зліва направо), тоді числа на інший прямий дадуть шукану перестановку.

Графи перестановки можна описати деякими іншими еквівалентними способами:

• Граф G є графом перестановки тоді й лише тоді, коли G — круговий граф, у якому можна побудувати екватор, тобто додаткову хорду, яка буде перетинати всі інші хорди[2].
• Граф G є графом перестановки тоді й лише тоді, коли G і його доповнення ${\displaystyle {\overline {G}}}$ є графами порівнянності[3].
• Граф G є графом перестановки тоді й лише тоді, коли він є графом порівнянності частково впорядкованої множини, у якого розмірність не перевищує двох[4].
• Якщо граф G є графом перестановок, то таким буде і доповнення. Перестановку, відповідну доповненням графу G, можна отримати як зворотну перестановку тій, яка відповідає графу G.

Можна перевірити, чи є граф графом перестановки, і побудувати відповідну йому перестановку за лінійний час[5].

Як для підкласу досконалих графів, багато задач, NP-повних для довільних графів, для графів перестановки можна розв'язати ефективно. Наприклад:

• Максимальна кліка в графі перестановок відповідає найбільшій спадній підпослідовності в перестановці, яка визначає граф, так що задачу про кліку для графів перестановки можна розв'язати за поліноміальний час при використанні алгоритму пошуку найбільшої спадної послідовності[6].

• Подібним чином зростаюча послідовність у перестановці відповідає незалежній множині того ж розміру у графі перестановки.

• Деревну ширина і шляхову ширина графів перестановки можна обчислити за поліноміальний час. Алгоритми обчислення цих величин використовують той факт, що число входжень мінімальних вершинних сепараторів у граф перестановки залежить поліноміально від розміру графу[7].

Графи перестановки є особливим випадком колових графів, графів порівнянності, доповненням графів порівнянності і трапецеїдальних графів.

Підкласами графів перестановки є дводольні графи перестановок і кографи.

• K. A. Baker, P. C. Fishburn, F. S. Roberts. Partial orders of dimension 2 // Networks. — 1971. — Т. 2, вип. 1 (23 січня). — С. 11–28. — DOI:10.1002/net.3230020103.
• Hans L. Bodlaender, Ton Kloks, Dieter Kratsch. Treewidth and pathwidth of permutation graphs // SIAM Journal on Discrete Mathematics. — 1995. — Т. 8, вип. 4 (23 січня). — С. 606—616. — DOI:10.1137/S089548019223992X.
• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999.
• Ben Dushnik, E. W. Miller. Partially ordered sets // American Journal of Mathematics. — 1941. — Т. 63, вип. 3 (23 січня). — С. 600—610. — DOI:10.2307/2371374.
• M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — 23 січня. — С. 159.
• Ross M. McConnell, Jeremy P. Spinrad. Modular decomposition and transitive orientation // Discrete Mathematics. — 1999. — Т. 201, вип. 1—3 (23 січня). — С. 189—241. — DOI:10.1016/S0012-365X(98)00319-7.

• Permutation graph. Information System on Graph Classes and their Inclusions.
• Weisstein, Eric W. Permutation Graph(англ.) на сайті Wolfram MathWorld.