Рұқсат ету графигі - Permutation graph

Орнын ауыстыру графигінен төмен (4,3,5,1,2) сәйкес диаграмма

Жылы математика, а ауыстыру графигі Бұл график оның төбелері а элементтерін білдіреді ауыстыру, және оның шеттері бейнеленген ауыстыру арқылы қалпына келтірілетін жұп элементтер. Рұқсат графиктері геометриялық тұрғыдан анықталуы мүмкін қиылысу графиктері соңғы нүктелері екіге жататын сызық сегменттері параллель сызықтар. Әр түрлі ауыстырулар бірдей ауыстыру графигін тудыруы мүмкін; Берілген графиктің ерекше көрінісі болады (егер ол симметрияға дейін болса), егер ол қатысты қарапайым болса модульдік ыдырау.^[1]

Анықтама және сипаттама

Егер σ = (σ₁, σ₂, ..., σ_n) кез келген ауыстыру 1-ден сандарға дейін n, содан кейін σ болатын пермутация графигін анықтауға болады n төбелер v₁, v₂, ..., v_nжәне оның шеті бар v_менv_j кез келген екі индекс үшін мен және j ол үшін мен < j және σ_мен > σ_j. Яғни, екі индекс мен және j ауыстыру графигіндегі жиекті дәл олар анықтаған кезде анықтаңыз инверсия ауыстыруда.

Орналастыру σ берілгенде, жиынтығын да анықтауға болады сызық сегменттері с_мен соңғы нүктелермен (мен, 0) және (σ_мен, 1). Бұл сегменттердің соңғы нүктелері екі параллель түзудің бойында жатыр ж = 0 және ж = 1, және екі сегменттің орны ауыстырудағы инверсияға сәйкес болған жағдайда ғана бос емес қиылысы болады. Сонымен, σ-нің ауыстыру графигі -мен сәйкес келеді қиылысу графигі сегменттердің Әрбір екі параллель түзулер үшін және екі түзуде де соңғы нүктелері бар сызық сегменттерінің әрбір ақырлы жиынтығы үшін, кесінділердің қиылысу графигі орын ауыстыру графигі болып табылады; егер сегменттің соңғы нүктелері бір-бірінен ерекшеленетін болса, онда ол ауыстыру графигі болып табылатын ауыстыруды екі жолдың біріндегі сегменттерді ретімен нөмірлеу және осы сандарды сегменттің соңғы нүктелері пайда болған ретпен оқу арқылы беруге болады. екінші жолда.

Рұқсат графиктерінің басқа да баламалы сипаттамалары бар:

График G тек егер болса, онда бұл ауыстыру графигі G Бұл шеңбер сызбасы бұл мойындайды экватор, яғни, басқа аккордты қиып өтетін қосымша аккорд.^[2]
График G егер бұл екеуі де болса ғана ауыстыру графигі болып табылады G және оның толықтыру ${displaystyle {overline {G}}}$ болып табылады салыстырмалы графиктер.^[3]
График G егер ол болған жағдайда ғана, ол ауыстыру графигі болып табылады салыстыру графигі а жартылай тапсырыс берілген жиынтық бар тапсырыс өлшемі ең көп дегенде екі.^[4]
Егер график болса G бұл ауыстыру графигі, сонымен қатар оның толықтырушысы. Толықтауышын білдіретін ауыстыру G ұсынылған ауыстыруды ауыстыру арқылы алуға болады G.

Тиімді алгоритмдер

Берілген графиктің орнын ауыстыру графигі екендігін тексеруге болады, ал егер солай болса, оны бейнелейтін ауыстыру құрса, сызықтық уақыт.^[5]

Кіші сыныбы ретінде тамаша графиктер, көптеген проблемалар NP аяқталды ерікті графиктер үшін ауыстыру графиктері үшін тиімді түрде шешілуі мүмкін. Мысалы:

ең үлкен клика ауыстыру графигінде сәйкес келеді ең ұзаққа созылатын төмендеу графикті анықтайтын орын ауыстыруда клика проблемасы шешілуі мүмкін көпмүшелік уақыт ауыстыру графиктері үшін ең ұзын кішірейетін алгоритмді қолдану арқылы.^[6]
сол сияқты, ауыстырудағы өсіп келе жатқан келесілер an сәйкес келеді тәуелсіз жиынтық сәйкес ауыстыру графигіндегі бірдей өлшемді.
The кеңдік және жол ені ауыстыру графиктерін көпмүшелік уақытта есептеуге болады; бұл алгоритмдер ең төменгі шыңдарды бөлгіштерді қосу ауыстыру графигінде график өлшемінде көпмүшелік болады.^[7]

Басқа графикалық кластармен байланыс

Рұқсат графиктері - бұл ерекше жағдай шеңбер сызбалары, салыстырмалы графиктер, салыстырмалы графиктердің толықтылығы және трапециялы графиктер.

Орын ауыстыру графиктерінің ішкі сыныптарына екі жақты ауыстыру графиктері (сипатталады Spinrad, Brandstädt & Stewart 1987 ж ) және ографтар.

Ескертулер

^ Brandstädt, Le & Spinrad (1999), б.191.
^ Brandstädt, Le & Spinrad (1999), Ұсыныс 4.7.1, б.57.
^ Душник және Миллер (1941).
^ Бейкер, Фишберн және Робертс (1971).
^ МакКоннелл және Спинрад (1999).
^ Голумбич (1980).
^ Bodlaender, Kloks & Kratsch (1995)

Әдебиеттер тізімі

Бейкер, Кирби А .; Фишберн, Питер С.; Робертс, Фред С. (1971), «2 өлшемнің ішінара тапсырыстары», Желілер, 2 (1): 11–28, дои:10.1002 / таза.3230020103.
Бодлаендер, Ханс Л.; Клокс, Тон; Крач, Дитер (1995), «Пермутациялық графиктердің кеңдігі мен кеңдігі», Дискретті математика бойынша SIAM журналы, 8 (4): 606–616, дои:10.1137 / S089548019223992X, hdl:1874/16657.
Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми П. (1999), Графикалық сыныптар: сауалнама, SIAM дискретті математика және қолданбалы монографиялары, ISBN 0-89871-432-X.
Душник, Бен; Миллер, Эдвин В. (1941), «Ішінара тапсырыс берілген жиынтықтар» (PDF), Американдық математика журналы, 63 (3): 600–610, дои:10.2307/2371374, JSTOR 2371374.
Голумбич, Мартин С. (1980), Алгоритмдік графика теориясы және мінсіз графиктер, Информатика және қолданбалы математика, Academic Press, б. 159.
МакКоннелл, Росс М .; Спинрад, Джереми П. (2011), «Модульдік ыдырау және өтпелі бағдар», Дискретті математика, 201 (1–3): 189–241, arXiv:1010.5447, дои:10.1016 / S0012-365X (98) 00319-7, МЫРЗА 1687819.
Спинрад, Джереми П .; Брандштадт, Андреас; Стюарт, Лорна К. (1987), «Екі жақты ауыстыру графиктері», Дискретті қолданбалы математика, 18 (3): 279–292, дои:10.1016 / s0166-218x (87) 80003-3.

Сыртқы сілтемелер

[1] Brandstädt, Le & Spinrad (1999), б.191.

[2] Brandstädt, Le & Spinrad (1999), Ұсыныс 4.7.1, б.57.

[3] Душник және Миллер (1941).

[4] Бейкер, Фишберн және Робертс (1971).

[5] МакКоннелл және Спинрад (1999).

[6] Голумбич (1980).

[7] Bodlaender, Kloks & Kratsch (1995)

[1]

[2]

[3]

[4]

[5]

[6]

[7]