Qiyshiq qism - Skew partition - Wikipedia

A-ning qiyshiq bo'limi akkord grafigi. Bo'limning chap tomonida yuqori va pastki qismlar bir-biridan uzilgan. Bo'limning o'ng tomonida yuqoridan pastgacha barcha mumkin bo'lgan qirralar mavjud bo'lib, ular qo'shimchasi ajratilgan grafikni hosil qiladi.

Yilda grafik nazariyasi, a qiyshiq qism grafigi a bo'lim uning vertikallarini ikkita pastki qismga, masalan induktsiya qilingan subgraf ikkita kichik to'plamdan biri tomonidan hosil qilingan uzilgan va boshqa pastki qism tomonidan hosil qilingan induktsiya subgrafasi to'ldiruvchi uzilgan grafik. Skew bo'limlari nazariyasida muhim rol o'ynaydi mukammal grafikalar.

Ta'rif

Grafikning egri qismi ${ displaystyle G}$ uning tepaliklarini ikkita pastki qismga bo'lishidir ${ displaystyle X}$ va ${ displaystyle Y}$ buning uchun induktsiya qilingan subgraf ${ displaystyle G [X]}$ ajratilgan va induktsiya qilingan subgraf ${ displaystyle G [Y]}$ ajratilgan grafigini to'ldiruvchi (bir-biridan ajratilgan). ${ displaystyle G}$ tepaliklarining bo'limi bilan tavsiflanishi mumkin ${ displaystyle G}$ to'rtta kichik guruhga ${ displaystyle A}$ , ${ displaystyle B}$ , ${ displaystyle C}$ va ${ displaystyle D}$ , hech qanday chekka yo'q ${ displaystyle A}$ ga ${ displaystyle B}$ va shunday bo'lishi mumkin bo'lgan barcha qirralar ${ displaystyle C}$ ga ${ displaystyle D}$ mavjud; bunday bo'lim uchun induktsiya qilingan subgrafalar ${ displaystyle G [A cup B]}$ va ${ displaystyle G [C cup D]}$ mos ravishda ajratilgan va birgalikda ajratilgan, shuning uchun olishimiz mumkin ${ displaystyle X = A kubok B}$ va ${ displaystyle Y = C stakan D}$ .

Misollar

Har bir yo'l grafigi to'rt yoki undan ortiq tepaliklar bilan birgalikda ajratilgan to'siq bo'linmasi mavjud ${ displaystyle Y}$ yo'lning ichki qirralaridan va ajratilgan to'plamlardan biridir ${ displaystyle X}$ ushbu qirraning har ikki tomonidagi tepaliklardan iborat. Biroq, bu mumkin emas tsikl grafigi qiyalik qismiga ega bo'lish uchun har qanday uzunlik: tsiklning qaysi kichik to'plamlari to'plam sifatida tanlanishidan qat'iy nazar ${ displaystyle X}$ , to'ldiruvchi to'plam ${ displaystyle Y}$ bir xil miqdordagi ulangan komponentlarga ega bo'ladi, shuning uchun buning iloji yo'q ${ displaystyle X}$ ajratish va ${ displaystyle Y}$ aloqani uzish.

Agar grafada qiyalik bo'limi bo'lsa, unda ham shunday bo'ladi to'ldiruvchi. Masalan, yo'l grafikalarining qo'shimchalarida qiyalik bo'laklari mavjud, tsikl grafikalarining qo'shimchalarida esa yo'q.

Maxsus holatlar

Agar grafik o'zi uzilgan bo'lsa, unda faqat uchta oddiy istisno (an.) bo'sh grafik, bitta qirrasi va uchta tepasi bo'lgan grafik yoki to'rtta vertex mukammal moslik ) uning qiyshiq bo'limi bor, unda bo'linmaning bir-biriga bog'langan tomoni bitta chekkaning so'nggi nuqtalaridan, ajratilgan tomoni esa boshqa barcha tepaliklardan iborat. Xuddi shu sababga ko'ra, agar grafikni to'ldiruvchisi uzilgan bo'lsa, unda uchta istisnolarning tegishli to'plami bilan u skeys bo'limi bo'lishi kerak.^[1]

Agar grafada a bo'lsa klik ajratuvchi (olib tashlash qolgan tepaliklarni uzib qo'yadigan klik), bir nechta tepalik bilan, keyin klik ichiga bo'linish va qolgan tepalar qiyshiq bo'lak hosil qiladi. Bitta tepalikka ega bo'lgan kesma kesma an artikulyatsiya nuqtasi; agar bunday tepalik mavjud bo'lsa, unda oddiygina istisnolardan tashqari, bir-biridan ajratilgan tomon shu tepalik va uning qo'shnilaridan iborat bo'lgan skew bo'limi mavjud.^[1]

A yulduzcha to'plami grafada ${ displaystyle G}$ a tepalikni ajratuvchi unda ajratuvchi tepaliklardan biri boshqalarga qo'shni. Har qanday klik ajratgich - bu yulduzlar to'plami. Shubhasiz, yulduzlar to'plami (bir nechta tepalikka ega) grafasida bir-biriga bog'langan subgraf yulduzlar to'plamidagi tepalardan, ajratilgan subgraf esa qolgan barcha tepaliklardan iborat bo'lgan skew bo'limi mavjud.^[1]

A modul (yoki bir hil to'plam) nrivrivial to'plamdir ${ displaystyle H}$ ning tepaliklari ${ displaystyle G}$ Shunday qilib, har bir tepalik uchun ${ displaystyle v}$ bu emas ${ displaystyle H}$ , yoki ${ displaystyle v}$ barcha tepaliklarga qo'shni ${ displaystyle H}$ yoki ularning hech biriga. Agar grafik ${ displaystyle G}$ moduli bor ${ displaystyle H}$ va uning tashqarisida, barcha vertikallarga qo'shni ikkala tepalik ham mavjud ${ displaystyle H}$ va ularning hech biriga qo'shni bo'lmagan boshqa tepaliklar, keyin ${ displaystyle G}$ moduldagi qo'shnilari bilan birgalikda modulda bitta tepadan iborat yulduzcha to'plamiga ega. Boshqa tomondan, agar ushbu ikkita kichik to'plamdan biri bo'sh bo'lgan modul mavjud bo'lsa, u holda grafik o'chiriladi yoki birgalikda o'chiriladi va yana (uchta oddiy istisnolardan tashqari) u qiyshiq kesimga ega.^[1]

Tarix

Skew bo'limlari tomonidan kiritilgan Chvatal (1985) bilan bog'liq mukammal grafikalar. Chvatal minimal darajada nomukammal grafada yulduzlar to'plami bo'lmasligini isbotladi. Arzimagan holda, uzilgan grafikalar minimal darajada nomukammal bo'lishi mumkin emas, shuningdek, kriker ajratgichlari yoki modullari bo'lgan grafikalar minimal darajada nomukammal bo'lishi mumkin emasligi ma'lum bo'lgan.^[2] Klod Berge 1960-yillarning boshlarida mukammal grafikalar Berge grafikalari bilan bir xil, grafika induksiya qilingan g'alati tsikl (besh va undan ortiq uzunlikdagi) yoki uning to'ldiruvchisi va (chunki tsikllar va ularning qo'shimchalari qiyshiq bo'laklarga ega emasligi sababli) minimal bo'lmagan -Berge grafigida skew bo'limi bo'lishi mumkin. Ushbu natijalardan kelib chiqqan holda, Chvatal hech bir minimal nomukammal grafada qiyalik bo'lagi bo'lmasligi mumkin deb taxmin qildi. Bir nechta mualliflar ushbu taxminning maxsus holatlarini isbotladilar, ammo bu ko'p yillar davomida hal qilinmadi.^[3]

Skew bo'limlari ulardan foydalanilganda ahamiyat kasb etdi Chudnovskiy va boshq. (2006) isbotlash uchun kuchli mukammal grafik teoremasi Berge grafikalari haqiqatan ham mukammal grafikalar bilan bir xil ekanligi. Chudnovskiy va boshq. Chvatalning gumonini to'g'ridan-to'g'ri isbotlay olmadi, aksincha teoremaga minimal qarshi misol (agar mavjud bo'lsa) muvozanatli skew bo'limi bo'lmasligi mumkin bo'lgan zaifroq natijani isbotladi. induktsiya qilingan yo'l qismning bir tomonida so'nggi nuqtalar, boshqa tomonida esa ichki tepaliklar teng uzunlikka ega. Ushbu natija ularni isbotlashda asosiy lemmani shakllantirdi va Chvatal lemmasining to'liq versiyasi ularning teoremasidan kelib chiqdi.^[4]

Strukturaviy grafik nazariyasida

Skew bo'limlari tomonidan ishlatiladigan mukammal grafiklarning tarkibiy dekompozitsiyasining asosiy tarkibiy qismlaridan biri hisoblanadi Chudnovskiy va boshq. (2006) kuchli mukammal grafik teoremasini isbotlashning bir qismi sifatida. Chudnovskiy va boshq. har bir mukammal grafik yoki beshta mukammal grafikaning bir sinfiga tegishli ekanligini yoki uning oddiyroq grafikalarga bo'linishining to'rt turidan biriga ega ekanligini ko'rsatdi, ulardan biri qiyshiq qismdir.

Eğimli bo'linmalardan foydalangan holda strukturaviy parchalanishning oddiyroq misoli berilgan Seymur (2006). U buni kuzatadi taqqoslash grafigi bu to'liq, bo'ladi ikki tomonlama yoki skew bo'limi bor. Uchun, agar a ning har bir elementi bo'lsa qisman buyurtma qilingan to'plam yoki a minimal element yoki maksimal element, keyin mos keladigan taqqoslash grafigi ikki tomonlama. Agar buyurtma a umumiy buyurtma, keyin mos keladigan taqqoslash grafigi to'ldiriladi. Agar bu ikkala holat ham paydo bo'lmasa, lekin minimal va maksimal bo'lmagan har qanday element boshqa barcha elementlar bilan taqqoslansa, u holda minimal yoki minimal bo'lmagan qismlarga bo'linish (agar bitta minimal element bo'lsa) yoki bo'linish maksimal va maksimal bo'lmagan elementlar (agar bir nechta maksimal element bo'lsa) yulduzlar to'plamini hosil qiladi. Va qolgan holatda, element mavjud ${ displaystyle x}$ minimal bo'lmagan, maksimal bo'lmagan va boshqa barcha elementlar bilan taqqoslanmaydigan qisman tartibning; bu holda, bir-biridan ajratilgan tomoni bilan taqqoslanadigan elementlardan iborat bo'lgan skew bo'limi (yulduzlar to'plamining komplementi) mavjud. ${ displaystyle x}$ (shu jumladan emas ${ displaystyle x}$ o'zi) va ajratilgan tomon qolgan elementlardan iborat.

The akkord grafikalari shunga o'xshash turdagi yanada sodda dekompozitsiyaga ega: ular to'liq yoki ular klik ajratgichga ega.Xeyvord (1985) Shunga o'xshash tarzda har bir bog'langan va bir-biriga bog'langan zaif xordal grafigi (induksiyasiz tsikli bo'lmagan yoki uning uzunligi to'rtdan kattaroq grafika) to'rtta va undan ortiq tepaliklar bilan yulduz kesimi yoki uning komplementiga ega bo'lib, undan Chvattal lemmasi kelib chiqadi. har bir bunday grafik mukammaldir.

Algoritmlar va murakkablik

Agar mavjud bo'lsa, berilgan grafikaning egri qismi, agar mavjud bo'lsa, uni topish mumkin polinom vaqti. Bu dastlab tomonidan ko'rsatilgan de Figueiredo va boshq. (2000) ammo juda katta ish vaqti bilan ${ displaystyle O (n ^ {101})}$ , qayerda ${ displaystyle n}$ bu kirish grafasidagi tepalar soni. Kennedi va Rid (2008) ishlash vaqtini yaxshilagan ${ displaystyle O (n ^ {4} m)}$ ; Bu yerga ${ displaystyle m}$ bu kirish qirralarining soni.

Bu To'liq emas grafada birgalikda ajratilgan tomonning qismlaridan biri mustaqil bo'lgan egri qism mavjudligini tekshirish.^[5]Berilgan grafada muvozanatli skew bo'limi mavjudligini tekshirish, shuningdek, o'zboshimchalik bilan grafikalarda NP bilan to'ldirilgan, ammo polinom vaqtida mukammal grafikalarda echilishi mumkin.^[6]

Izohlar

^ ^a ^b ^v ^d Rid (2008).
^ Rid (2008). Minimal nomukammal grafikalarda modullarning yo'qligi tomonidan ishlatilgan Lovash (1972) uning isboti bilan zaif mukammal grafik teoremasi.
^ Qarang Cornuéjols & Reed (1993) qismning birgalikda ajratilgan tomoni ko'p tomonli bo'lgan holat uchun va Roussel va Rubio (2001) birgalikda ajratilgan tomonning ikki qismidan biri mustaqil bo'lgan holat uchun.
^ Seymur (2006).
^ Dantas va boshq. (2004).
^ Trotignon (2008).

Adabiyotlar

Chudnovskiy, Mariya; Robertson, Nil; Seymur, Pol; Tomas, Robin (2006), "Kuchli mukammal grafik teoremasi", Matematika yilnomalari, 164 (1): 51–229, arXiv:matematik / 0212070, doi:10.4007 / annals.2006.164.51.
Chvatal, V. (1985), "Yulduzlar to'plami va mukammal grafikalar", Kombinatorial nazariya jurnali, B seriyasi, 39 (3): 189–199, doi:10.1016/0095-8956(85)90049-8, JANOB 0815391.
Kornueyols, G.; Rid, B. (1993), "Minimal nomukammal grafikalarda to'liq ko'p qismli kesmalar", Kombinatorial nazariya jurnali, B seriyasi, 59 (2): 191–198, doi:10.1006 / jctb.1993.1065, JANOB 1244930.
Dantas, Simone; de Figueiredo, Celina M. H.; Klayn, Sulamita; Gravye, Silveyn; Rid, Bryus A. (2004), "Stew skew partition problem", Diskret amaliy matematika, 143 (1–3): 17–22, doi:10.1016 / j.dam.2004.01.001, JANOB 2087864.
de Figueiredo, Celina M. H.; Klayn, Sulamita; Kohayakava, Yoshixaru; Rid, Bryus A. (2000), "Nishabli qismlarni samarali topish", Algoritmlar jurnali, 37 (2): 505–521, doi:10.1006 / jagm.1999.1122, JANOB 1788847.
Xeyvord, Rayan B. (1985), "Zaif uchburchakli grafikalar", Kombinatorial nazariya jurnali, B seriyasi, 39 (3): 200–208, doi:10.1016/0095-8956(85)90050-4, JANOB 0815392.
Kennedi, Uilyam S.; Rid, Bryus (2008), "Tez skew qismini tanib olish", Hisoblash geometriyasi va grafikalar nazariyasi: Xalqaro konferentsiya, KyotoCGGT 2007, Kioto, Yaponiya, 2007 yil 11-15 iyun, Qayta ko'rib chiqilgan tanlangan maqolalar, Kompyuter fanidan ma'ruza matnlari, 4535, Berlin: Springer, 101-107 betlar, doi:10.1007/978-3-540-89550-3_11, JANOB 2672388.
Lovash, Laslo (1972), "Oddiy gipergrafalar va mukammal grafik gipotezasi", Diskret matematika, 2 (3): 253–267, doi:10.1016 / 0012-365X (72) 90006-4.
Rid, Bryus (2008), "Bo'sh qismlarni mukammal grafikalarda" (PDF), Diskret amaliy matematika, 156 (7): 1150–1156, doi:10.1016 / j.dam.2007.05.054, JANOB 2404228.
Russel, F.; Rubio, P. (2001), "Minimal nomukammal grafikalardagi qiyalik bo'limlari to'g'risida", Kombinatorial nazariya jurnali, B seriyasi, 83 (2): 171–190, doi:10.1006 / jctb.2001.2044, JANOB 1866394.
Seymur, Pol (2006), "Kuchli mukammal grafika gipotezasining isboti qanday topildi" (PDF), Gazette des Mathématiciens (109): 69–83, JANOB 2245898.
Trotignon, Nikolas (2008), "Berge grafikalarini parchalash va muvozanatli egri qismlarni aniqlash" (PDF), Kombinatorial nazariya jurnali, B seriyasi, 98 (1): 173–225, doi:10.1016 / j.jctb.2007.07.004, JANOB 2368032.

[r08-1] v ^d Rid (2008).

[2] Rid (2008). Minimal nomukammal grafikalarda modullarning yo'qligi tomonidan ishlatilgan Lovash (1972) uning isboti bilan zaif mukammal grafik teoremasi.

[3] Qarang Cornuéjols & Reed (1993) qismning birgalikda ajratilgan tomoni ko'p tomonli bo'lgan holat uchun va Roussel va Rubio (2001) birgalikda ajratilgan tomonning ikki qismidan biri mustaqil bo'lgan holat uchun.

[4] Seymur (2006).

[5] Dantas va boshq. (2004).

[6] Trotignon (2008).

[1]

[2]

[3]

[4]

[5]

[6]