В теорії графів граф перестановки — це граф, вершини якого відповідають елементам перестановки, а ребра представляють пари елементів, порядок слідування яких змінився після перестановки. Графи перестановки можна визначити геометрично як графи перетинів відрізків, кінці яких лежать на двох паралельних прямих. Різні перестановки можуть дати один і той самий граф перестановки. Заданий граф має єдине подання (з точністю до симетрії) якщо він є простим з точки зору .
Визначення та опис
Нехай σ = (σ1,σ2, …, σn) — деяка перестановка чисел від 1 до n. Для σ граф перестановки має n вершин v1, v2, …, vn і в цьому графі ребро vivj існує для будь-яких двох індексів i та j, для яких i < j і σi > σj. Таким чином, для двох індексів i та j ребро в графі визначається точно так само, як визначається (транспозиція) в перестановці.
Якщо задано перестановку σ, можна визначити множину відрізків si з кінцевими точками (i,0) і (σi,1). Кінцеві точки цих відрізків розташовуються на двох паралельних прямих y = 0 і y = 1, і два відрізки мають непорожній перетин тоді і тільки тоді, коли вони відповідають інверсії в перестановці. Таким чином, граф перестановки для σ збігається з графом перетинів відрізків. Для будь-яких двох паралельних прямих і будь-якого скінченного набору відрізків з кінцями на цих прямих граф перетинів відрізків є графом перестановки. Якщо всі скінченні точки відрізків різні, перестановку, відповідну графу перестановки, можна отримати нумерацією відрізків на одній з прямих (послідовно, наприклад, зліва направо), тоді числа на інший прямий дадуть шукану перестановку.
Графи перестановки можна описати деякими іншими еквівалентними способами:
- Граф G є графом перестановки тоді й лише тоді, коли G — , у якому можна побудувати екватор, тобто додаткову хорду, яка буде перетинати всі інші хорди.
- Граф G є графом перестановки тоді й лише тоді, коли G і його доповнення є графами порівнянності.
- Граф G є графом перестановки тоді й лише тоді, коли він є графом порівнянності частково впорядкованої множини, у якого [en] не перевищує двох.
- Якщо граф G є графом перестановок, то таким буде і доповнення. Перестановку, відповідну доповненням графа G, можна отримати як зворотну перестановку тій, яка відповідає графу G.
Ефективні алгоритми
Можна перевірити, чи є граф графом перестановки, і побудувати відповідну йому перестановку за лінійний час.
Як для підкласу досконалих графів, багато задач, NP-повних для довільних графів, для графів перестановки можна розв'язати ефективно. Наприклад:
- Максимальна кліка в графі перестановок відповідає найбільшій спадній підпослідовності в перестановці, яка визначає граф, так що задачу про кліку для графів перестановки можна розв'язати за поліноміальний час при використанні алгоритму пошуку найбільшої спадної послідовності.
- Подібним чином зростаюча послідовність у перестановці відповідає незалежній множині того ж розміру у графі перестановки.
- Деревну ширина і шляхову ширина графів перестановки можна обчислити за поліноміальний час. Алгоритми обчислення цих величин використовують той факт, що число входжень мінімальних вершинних сепараторів у граф перестановки залежить поліноміально від розміру графа.
Відношення до інших класів графів
Графи перестановки є особливим випадком колових графів, графів порівнянності, доповненням графів порівнянності і .
Підкласами графів перестановки є двочасткові графи перестановок і кографи.
Примітки
- , Eric W. Perm
- Brandstädt, Le, Spinrad, 1999, твердження 4.7.1, стор.57.
- Dushnik, Miller, 1941.
- Baker, Fishburn, Roberts, 1971.
- McConnell, Spinrad, 1999.
- Golumbic, 1980.
- Bodlaender, Kloks, Kratsch, 1995.
Література
- K. A. Baker, P. C. Fishburn, F. S. Roberts. Partial orders of dimension 2 // Networks. — 1971. — Т. 2, вип. 1 (13 липня). — С. 11–28. — DOI: .
- Hans L. Bodlaender, Ton Kloks, Dieter Kratsch. Treewidth and pathwidth of permutation graphs // SIAM Journal on Discrete Mathematics. — 1995. — Т. 8, вип. 4 (13 липня). — С. 606—616. — DOI: .
- 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 (13 липня). — С. 600—610. — DOI: .
- M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — 13 липня. — С. 159.
- Ross M. McConnell, Jeremy P. Spinrad. Modular decomposition and transitive orientation // . — 1999. — Т. 201, вип. 1—3 (13 липня). — С. 189—241. — DOI: .
Посилання
- . Information System on Graph Classes and their Inclusions. Архів оригіналу за 4 квітня 2014. Процитовано 17 грудня 2020.
- Weisstein, Eric W. Permutation Graph(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi grafiv graf perestanovki ce graf vershini yakogo vidpovidayut elementam perestanovki a rebra predstavlyayut pari elementiv poryadok sliduvannya yakih zminivsya pislya perestanovki Grafi perestanovki mozhna viznachiti geometrichno yak grafi peretiniv vidrizkiv kinci yakih lezhat na dvoh paralelnih pryamih Rizni perestanovki mozhut dati odin i toj samij graf perestanovki Zadanij graf maye yedine podannya z tochnistyu do simetriyi yaksho vin ye prostim z tochki zoru Perestanovka 4 3 5 1 2 i vidpovidnij graf perestanovkiViznachennya ta opisNehaj s s1 s2 sn deyaka perestanovka chisel vid 1 do n Dlya s graf perestanovki maye n vershin v1 v2 vn i v comu grafi rebro vivj isnuye dlya bud yakih dvoh indeksiv i ta j dlya yakih i lt j i si gt sj Takim chinom dlya dvoh indeksiv i ta j rebro v grafi viznachayetsya tochno tak samo yak viznachayetsya transpoziciya v perestanovci Yaksho zadano perestanovku s mozhna viznachiti mnozhinu vidrizkiv si z kincevimi tochkami i 0 i si 1 Kincevi tochki cih vidrizkiv roztashovuyutsya na dvoh paralelnih pryamih y 0 i y 1 i dva vidrizki mayut neporozhnij peretin todi i tilki todi koli voni vidpovidayut inversiyi v perestanovci Takim chinom graf perestanovki dlya s zbigayetsya z grafom peretiniv vidrizkiv Dlya bud yakih dvoh paralelnih pryamih i bud yakogo skinchennogo naboru vidrizkiv z kincyami na cih pryamih graf peretiniv vidrizkiv ye grafom perestanovki Yaksho vsi skinchenni tochki vidrizkiv rizni perestanovku vidpovidnu grafu perestanovki mozhna otrimati numeraciyeyu vidrizkiv na odnij z pryamih poslidovno napriklad zliva napravo todi chisla na inshij pryamij dadut shukanu perestanovku Grafi perestanovki mozhna opisati deyakimi inshimi ekvivalentnimi sposobami Graf G ye grafom perestanovki todi j lishe todi koli G u yakomu mozhna pobuduvati ekvator tobto dodatkovu hordu yaka bude peretinati vsi inshi hordi Graf G ye grafom perestanovki todi j lishe todi koli G i jogo dopovnennya G displaystyle overline G ye grafami porivnyannosti Graf G ye grafom perestanovki todi j lishe todi koli vin ye grafom porivnyannosti chastkovo vporyadkovanoyi mnozhini u yakogo en ne perevishuye dvoh Yaksho graf G ye grafom perestanovok to takim bude i dopovnennya Perestanovku vidpovidnu dopovnennyam grafa G mozhna otrimati yak zvorotnu perestanovku tij yaka vidpovidaye grafu G Efektivni algoritmiMozhna pereviriti chi ye graf grafom perestanovki i pobuduvati vidpovidnu jomu perestanovku za linijnij chas Yak dlya pidklasu doskonalih grafiv bagato zadach NP povnih dlya dovilnih grafiv dlya grafiv perestanovki mozhna rozv yazati efektivno Napriklad Maksimalna klika v grafi perestanovok vidpovidaye najbilshij spadnij pidposlidovnosti v perestanovci yaka viznachaye graf tak sho zadachu pro kliku dlya grafiv perestanovki mozhna rozv yazati za polinomialnij chas pri vikoristanni algoritmu poshuku najbilshoyi spadnoyi poslidovnosti Podibnim chinom zrostayucha poslidovnist u perestanovci vidpovidaye nezalezhnij mnozhini togo zh rozmiru u grafi perestanovki Derevnu shirina i shlyahovu shirina grafiv perestanovki mozhna obchisliti za polinomialnij chas Algoritmi obchislennya cih velichin vikoristovuyut toj fakt sho chislo vhodzhen minimalnih vershinnih separatoriv u graf perestanovki zalezhit polinomialno vid rozmiru grafa Vidnoshennya do inshih klasiv grafivGrafi perestanovki ye osoblivim vipadkom kolovih grafiv grafiv porivnyannosti dopovnennyam grafiv porivnyannosti i Pidklasami grafiv perestanovki ye dvochastkovi grafi perestanovok i kografi Primitki Eric W Perm Brandstadt Le Spinrad 1999 tverdzhennya 4 7 1 stor 57 Dushnik Miller 1941 Baker Fishburn Roberts 1971 McConnell Spinrad 1999 Golumbic 1980 Bodlaender Kloks Kratsch 1995 LiteraturaK A Baker P C Fishburn F S Roberts Partial orders of dimension 2 Networks 1971 T 2 vip 1 13 lipnya S 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 T 8 vip 4 13 lipnya S 606 616 DOI 10 1137 S089548019223992X Andreas Brandstadt 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 T 63 vip 3 13 lipnya S 600 610 DOI 10 2307 2371374 M C Golumbic Algorithmic Graph Theory and Perfect Graphs Academic Press 1980 13 lipnya S 159 Ross M McConnell Jeremy P Spinrad Modular decomposition and transitive orientation 1999 T 201 vip 1 3 13 lipnya S 189 241 DOI 10 1016 S0012 365X 98 00319 7 Posilannya Information System on Graph Classes and their Inclusions Arhiv originalu za 4 kvitnya 2014 Procitovano 17 grudnya 2020 Weisstein Eric W Permutation Graph angl na sajti Wolfram MathWorld