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

Перестановка (4, 3, 5, 1, 2) і відповідний граф перестановки

В теорії графів граф перестановки — це граф, вершини якого відповідають елементам перестановки, а ребра представляють пари елементів, порядок слідування яких змінився після перестановки. Графи перестановки можна визначити геометрично як графи перетинів відрізків, кінці яких лежать на двох паралельних прямих. Різні перестановки можуть дати один і той самий граф перестановки. Заданий граф має єдине подання (з точністю до симетрії) якщо він є простим з точки зору модульної декомпозиції.

Визначення та опис

Нехай σ = (σ₁,σ₂, …, σ_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 — круговий граф, у якому можна побудувати екватор, тобто додаткову хорду, яка буде перетинати всі інші хорди.
• Граф G є графом перестановки тоді й лише тоді, коли G і його доповнення ${\overline {G}}$ є графами порівнянності.
• Граф G є графом перестановки тоді й лише тоді, коли він є графом порівнянності частково впорядкованої множини, у якого розмірність не перевищує двох.
• Якщо граф G є графом перестановок, то таким буде і доповнення. Перестановку, відповідну доповненням графу G, можна отримати як зворотну перестановку тій, яка відповідає графу G.

Ефективні алгоритми

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

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

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

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

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

Відношення до інших класів графів

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

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

Література

• K. A. Baker, P. C. Fishburn, F. S. Roberts. Partial orders of dimension 2 // Networks. — 1971. — Т. 2, вип. 1 (18 травня). — С. 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 (18 травня). — С. 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 (18 травня). — С. 600—610. — DOI:10.2307/2371374.
• M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — 18 травня. — С. 159.
• Ross M. McConnell, Jeremy P. Spinrad. Modular decomposition and transitive orientation // Discrete Mathematics. — 1999. — Т. 201, вип. 1—3 (18 травня). — С. 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.