Grafik tuzilish teoremasi - Graph structure theorem

Yilda matematika, grafik tuzilish teoremasi sohasidagi asosiy natijadir grafik nazariyasi. Natija nazariyasi o'rtasida chuqur va asosiy aloqani o'rnatadi voyaga etmaganlar va topologik ko'milishlar. Teorema 23 ta to'plamning o'n ettinchi qismida keltirilgan Nil Robertson va Pol Seymur. Uning isboti juda uzoq va jalb qilingan. Kavarabayashi va Mohar (2007) va Lovash (2006) bu teorema va uning oqibatlarini tavsiflovchi mutaxassis bo'lmaganlar uchun mavjud bo'lgan so'rovlar.

Teoremaning o'rnatilishi va motivatsiyasi

A voyaga etmagan grafik G har qanday grafik H ning subgrafasidan olish mumkin bo'lgan grafika uchun izomorfik G tomonidan shartnoma ba'zi chekkalari. Agar G qiladi emas grafaga ega bo'lish H voyaga etmagan bo'lib, biz buni aytamiz G bu H-ozod. Ruxsat bering H sobit grafik bo'lishi. Intuitiv ravishda, agar G juda katta H- bepul grafik, unda buning uchun "yaxshi sabab" bo'lishi kerak edi. Grafik tuzilish teoremasi bunday "yaxshi sabab" ni tuzilishining qo'pol tavsifi ko'rinishida keltiradi G. Aslida, har bir H- bepul grafik G ikkita tarkibiy kamchiliklardan biriga duch keladi: yoki G ega bo'lish uchun "juda nozik" H voyaga etmaganlikda yoki G singdirish uchun juda sodda (deyarli) sirtga topologik jihatdan joylashtirilgan bo'lishi mumkin H ustiga. Birinchi sabab, agar qo'llaniladi H a planar grafik va ikkala sabab ham qo'llaniladi H planar emas. Dastlab biz ushbu tushunchalarni aniq qilamiz.

Daraxt kengligi

The daraxt kengligi grafik G ning "nozikligini" aniqlovchi musbat tamsayıdir G. Masalan, ulangan grafik G agar u daraxt bo'lsa va faqat G daraxtning kengligi ikkitadir va agar u a bo'lsa ketma-ket parallel grafik. Intuitiv ravishda juda katta grafik G va agar shunday bo'lsa, kichik daraxt kengligiga ega G tugunlari va qirralari kichik grafikalar bilan almashtirilgan ulkan daraxtning tuzilishini oladi. Klik-summa bo'yicha kichik bo'limda daraxt kengligining aniq ta'rifini beramiz. Agar shunday bo'lsa, bu teorema H ning voyaga etmaganidir G, keyin daraxtning kengligi H undan kattaroq emas G. Shuning uchun, bitta "yaxshi sabab" G bolmoq H-free - bu daraxtning kengligi G juda katta emas. Grafik tuzilish teoremasi shuni anglatadiki, ushbu sabab har doim ham har holda amal qiladi H planar hisoblanadi.

Xulosa 1. Har bir planar grafik uchun H, musbat tamsayı mavjud k shunday har bir H-free grafik daraxt kengligidan kamroq k.

Afsuski, ning qiymati k Xulosa 1 da odatda daraxtning kengligidan ancha katta H (qachonki muhim istisno H = K₄, to'rtta tepalikdagi to'liq grafik k= 3). Bu grafik tuzilish teoremasining "qo'pol tuzilishini" tavsiflashi uchun aytilganining bir sababi H- bepul grafikalar.

Yuzaki ko'milishlar

Taxminan, a sirt bu diskning mahalliy topologik tuzilishiga ega bo'lgan fikrlar to'plami. Yuzalar ikkita cheksiz oilaga bo'linadi: yo'naltirilgan yuzalarga quyidagilar kiradi soha, torus, ikki torus va hokazo; The noo'rin yuzalarga quyidagilar kiradi haqiqiy proektsion tekislik, Klein shishasi va hokazo. Grafik joylashadi agar grafani bir-biriga kesib o'tmaydigan yoki tegmaydigan nuqtalar (tepalar) va yoylar (qirralar) to'plami sifatida sirt ustida chizish mumkin bo'lsa, faqat qirralar va tepaliklar to'qnashgan yoki qo'shni bo'lgan joylar bundan mustasno. Grafik planar agar u sharga o'tirsa. Agar grafik G har bir kichik yoshga to'lgan G yana o'sha sirtga joylashadi. Shuning uchun, "yaxshi sabab" G bolmoq H- bepul G yuzasida joylashgan H joylashtirilmaydi.

Qachon H planar emas, grafik tuzilish teoremasi Kuratovskiy teoremasining ulkan umumlashmasi sifatida qaralishi mumkin. Tomonidan tasdiqlangan ushbu teoremaning versiyasi Vagner (1937) agar grafik bo'lsa G ikkalasi ham K₅- bepul va K_3,3-bepul, keyin G planar hisoblanadi. Ushbu teorema grafik uchun "yaxshi sabab" ni keltirib chiqaradi G bo'lmaslik K₅ yoki K_3,3 voyaga etmaganlar sifatida; xususan, G sharga o'ralgan, ikkalasi ham yo'q K₅ na K_3,3 sharga joylashtirilgan. Afsuski, bu "yaxshi sabab" tushunchasi grafik tuzilish teoremasi uchun etarlicha murakkab emas. Yana ikkita tushuncha kerak: klik-summalar va girdoblar.

Klik summalari

A klik grafada G juftlik bilan qo'shni bo'lgan har qanday tepaliklar to'plamidir G. Salbiy bo'lmagan butun son uchun k, a k-klik-sum ikkita grafikadan G va K manfiy bo'lmagan butun sonni tanlash natijasida olingan har qanday grafik m ≤ k, o'lcham klikini tanlash m har birida G va K, ikkita klikni bitta kattalikdagi klikga aniqlash m, so'ngra yangi klikdagi tepaliklarni birlashtiradigan nol yoki undan ko'p qirralarning yo'q qilinishi.

Agar G₁, G₂, ..., G_n bu grafikalar ro'yxati, keyin biz grafikalar ro'yxatiga qo'shilish orqali yangi grafika ishlab chiqarishimiz mumkin k-klik-summa orqali. Ya'ni, biz k-klik-yig'indisi G₁ va G₂, keyin oling k-klik-yig'indisi G₃ natijada olingan grafik bilan va boshqalar. Grafik mavjud daraxt kengligi k orqali olish mumkin bo'lsa k- grafikalar ro'yxatidagi yig'indilar, bu erda ro'yxatdagi har bir grafik ko'pi bilan bo'ladi k + 1 tepalik.

1-xulosa bizga buni ko'rsatadi k-kichik grafikalar yig'indisi qo'pol tuzilmani tavsiflaydi H- qachon bepul grafikalar H planar hisoblanadi. Qachon H rejadan tashqari, biz ham e'tiborga olishimiz kerak k- har biri sirtga o'rnatilgan grafikalar ro'yxatining klik-yig'indisi. Bilan quyidagi misol H = K₅ bu fikrni aks ettiradi. Grafik K₅ shardan tashqari har qanday yuzaga joylashadi. Ammo mavjud K₅- tekislikdan uzoq bo'lgan bepul grafikalar. Xususan, har qanday planar grafikalar ro'yxatining 3-klik-yig'indisi a ga olib keladi K₅- bepul grafik. Vagner (1937) ning aniq tuzilishini aniqladi K₅sifatida tanilgan natijalar klasterining bir qismi sifatida - bepul grafikalar Vagner teoremasi:

Teorema 2. Agar G bu K₅-bepul, keyin G planar grafikalar ro'yxatidan 3-klik-summa va 8 vertikalga ega bo'lgan bitta maxsus planar bo'lmagan grafika nusxalari orqali olish mumkin.

2-teorema an aniq tuzilish teoremasi chunki aniq tuzilishi K₅- bepul grafikalar aniqlanadi. Bunday natijalar grafika nazariyasida kam uchraydi. Grafik tuzilish teoremasi bu ma'noda aniq emas, chunki aksariyat grafikalar uchun H, ning tarkibiy tavsifi H-free grafikalar tarkibiga ba'zi bir grafikalar kiradi emas H-ozod.

Vortekslar (qo'pol tavsif)

Teorema 2-ning analogi grafikalar uchun gumon qilishni xohlashi mumkin H dan boshqa K₅. Ehtimol, bu to'g'ri: har qanday tekis bo'lmagan grafalar uchun H musbat butun son mavjud, chunki har bir H bo'lmagan grafani grafikalar ro'yxatidan k-klik-yig'indilar orqali olish mumkin, ularning har biri ko'pi bilan k vertikalga ega yoki ba'zi bir sirtga joylashtirilgan. H qo'shilmagan. Afsuski, ushbu bayonot haqiqatan ham etarlicha murakkab emas. Biz har bir o'rnatilgan grafikaga ruxsat berishimiz kerak G_men ikkita cheklangan yo'l bilan "aldash". Birinchidan, biz cheklangan tartibda bir-biridan o'tishga ruxsat berilgan ba'zi yangi tepaliklar va qirralarni qo'shishimiz mumkin bo'lgan cheklangan miqdordagi joylarga ruxsat berishimiz kerak. murakkablik. Bunday joylar deyiladi girdoblar. Girdobning "murakkabligi" uning nomi bilan cheklangan chuqurlikbilan chambarchas bog'liq yo'l kengligi. O'quvchi chuqurlik girdobining quyidagi aniq tavsifini o'qishni keyinga qoldirishni ma'qul ko'rishi mumkin k. Ikkinchidan, girdoblar bilan o'rnatilgan har bir grafikka cheklangan miqdordagi yangi tepaliklarni qo'shishga ruxsat berishimiz kerak.

Vortekslar (aniq ta'rif)

A yuz ko'milgan grafning yuzasi grafadan ajratilgan, lekin chegarasi ko'milgan grafning ba'zi qirralarining birlashishi bo'lgan sirtdagi ochiq 2 xujayradir. Ruxsat bering F o'rnatilgan grafikaning yuzi bo'ling G va ruxsat bering v₀, v₁, ..., v_n−1,v_n = v₀ chegarasida yotgan tepaliklar bo'ling F (shu doiraviy tartibda). A aylana oralig'i uchun F bu shakldagi tepaliklar to'plami {v_a, v_a+1, ..., v_a+s} qayerda a va s tamsayılar va bu erda obzorlar qisqartirilgan moduln. $ D $ uchun doiraviy intervallarning cheklangan ro'yxati bo'lsin F. Biz yangi grafikni quyidagicha quramiz. Har bir aylana oralig'i uchun L Λ da biz yangi vertex qo'shamiz v_L bu tepaliklarning nolga yoki undan ko'piga qo'shiladi L. Va nihoyat, har bir juftlik uchun {L, Minterv intervallarni}, biz chekka qo'shilishni qo'shishimiz mumkin v_L ga v_M sharti bilan L va M bo'sh bo'lmagan chorrahaga ega. Olingan grafikni olingan deyiladi G tomonidan ko'pi bilan chuqurlik girdobini qo'shish k(yuzgaF) chegarasida hech qanday tepalik bo'lmasligi sharti bilan F dan ko'proqda paydo bo'ladi k in dagi intervallarni

Grafika tuzilishi teoremasining bayoni

Grafik tuzilish teoremasi. Har qanday H grafasi uchun musbat tamsayı k mavjud, shunda har bir H bo'lmagan grafigini quyidagicha olish mumkin:

1. Biz grafikalar ro'yxatidan boshlaymiz, bu erda ro'yxatdagi har bir grafik H joylashtirilmaydigan yuzaga o'rnatiladi.
2. ro'yxatdagi har bir kiritilgan grafikaga biz ko'pi bilan k girdobini qo'shamiz, bu erda har bir girdob chuqurligi k ga teng
3. har bir olingan grafaga biz ko'pi bilan k tepalarni qo'shamiz (deyiladi tepaliklar ) va qirralarning istalgan sonini qo'shing, ularning har biri cho'qqilar orasida kamida bittasiga ega.
4. nihoyat, biz grafikalar ro'yxatini k-clique-sums orqali birlashtiramiz.

E'tibor bering, agar 1. va 2. qadamlar bo'sh grafikka olib keladi, agar H planar, lekin 3-bosqichga qo'shilgan tepaliklarning cheklangan soni bayonni 1-xulosaga mos keladi.

Aniqlashlar

To'plamga qarab grafik tuzilish teoremasining mustahkamlangan versiyalari mumkin H taqiqlangan voyaga etmaganlar. Masalan, grafikalardan biri qachon H bu planar, keyin har biri H- kichik grafada a daraxtlarning parchalanishi cheklangan kenglik; ekvivalent ravishda, u sifatida ifodalanishi mumkin klik-sum doimiy o'lchamdagi grafikalar^[1] Grafiklardan biri qachon H tekislikda faqat bitta bilan chizish mumkin kesib o'tish, keyin H- kichik grafalar parchalanishni doimiy o'lchamdagi grafika va chegaralangan jins grafika girdobisiz yig'indisi sifatida tan oladi.^[2]Agar grafikalardan biri bo'lsa, boshqacha mustahkamlash ham ma'lum H bu tepalik grafigi.^[3]

Shuningdek qarang

• Robertson-Seymur teoremasi

Izohlar

Adabiyotlar

• Demain, Erik D.; Hojiagayi, Muhammad Taghi; Kavarabayashi, Ken-ichi (2009), "Apex-minor-bepul grafikalar uchun strukturaviy natijalar orqali taxminiy algoritmlar", Proc. 36-Xalqaro Kollokvium avtomatika, tillar va dasturlash (ICALP '09) (PDF), Kompyuter fanidan ma'ruza matnlari, 5555, Springer-Verlag, 316–327 betlar, doi:10.1007/978-3-642-02927-1_27, JANOB  2544855.
• Demain, Erik D.; Hojiagayi, Muhammad Taghi; Thilikos, Dimitrios M. (2002), "1.5-Grafiklarning kengligi uchun yaqinlashish, kichik o'lchamda bitta o'tish joyi bo'lgan grafikdan tashqari", Proc. Kombinatorial optimallashtirish uchun taxminiy algoritmlar bo'yicha 5-Xalqaro seminar (APPROX 2002), Kompyuter fanidan ma'ruza matnlari, 2462, Springer-Verlag, 67-80 betlar, doi:10.1007/3-540-45753-4_8, JANOB  2091577.
• Kavarabayashi, Ken-ichi; Mohar, Bojan (2007), "Grafika kichik nazariyasidagi ba'zi so'nggi yutuqlar va qo'llanmalar", Grafika va kombinatorika, 23 (1): 1–46, doi:10.1007 / s00373-006-0684-x, JANOB  2292102.
• Lovash, Laslo (2006), "Grafika kichik nazariyasi", Amerika Matematik Jamiyati Axborotnomasi, 43 (1): 75–86, doi:10.1090 / S0273-0979-05-01088-8, JANOB  2188176.
• Robertson, Nil; Seymur, P. D. (1983), "Voyaga etmaganlar grafigi. I. O'rmon bundan mustasno", Kombinatoriya nazariyasi jurnali, B seriyasi, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5, JANOB  0723569.
• Robertson, Nil; Seymur, P. D. (1986), "Grafika kichiklari. II. Daraxt kengligining algoritmik tomonlari", Algoritmlar jurnali, 7 (3): 309–322, doi:10.1016/0196-6774(86)90023-4, JANOB  0855559.
• Robertson, Nil; Seymur, P. D. (1984), "Voyaga etmaganlar grafigi. III. Daraxtlarning kengligi tekisligi", Kombinatorial nazariya jurnali, B seriyasi, 36 (1): 49–64, doi:10.1016/0095-8956(84)90013-3, JANOB  0742386.
• Robertson, Nil; Seymur, P. D. (1990), "Voyaga etmaganlar grafigi. IV. Daraxtlar kengligi va yaxshi kvaziga buyurtma berish", Kombinatorial nazariya jurnali, B seriyasi, 48 (2): 227–254, doi:10.1016 / 0095-8956 (90) 90120-O, JANOB  1046757.
• Robertson, Nil; Seymur, P. D. (1986), "Grafika kichiklari. V. Planar grafikani hisobga olmaganda", Kombinatorial nazariya jurnali, B seriyasi, 41 (1): 92–114, doi:10.1016/0095-8956(86)90030-4, JANOB  0854606.
• Robertson, Nil; Seymur, P. D. (1986), "Grafika kichiklari. VI. Disk bo'ylab ajratilgan yo'llar", Kombinatorial nazariya jurnali, B seriyasi, 41 (1): 115–138, doi:10.1016/0095-8956(86)90031-6, JANOB  0854607.
• Robertson, Nil; Seymur, P. D. (1988), "Voyaga etmaganlar grafigi. VII. Yuzaki ajratilgan yo'llar", Kombinatorial nazariya jurnali, B seriyasi, 45 (2): 212–254, doi:10.1016/0095-8956(88)90070-6, JANOB  0961150.
• Robertson, Nil; Seymur, P. D. (1990), "Kichiklar grafigi. VIII. Umumiy sirt uchun Kuratovskiy teoremasi", Kombinatorial nazariya jurnali, B seriyasi, 48 (2): 255–288, doi:10.1016 / 0095-8956 (90) 90121-F, JANOB  1046758.
• Robertson, Nil; Seymur, P. D. (1990), "Voyaga etmaganlar grafigi. IX. Kesilgan yo'llar", Kombinatorial nazariya jurnali, B seriyasi, 49 (1): 40–77, doi:10.1016/0095-8956(90)90063-6, JANOB  1056819.
• Robertson, Nil; Seymur, P. D. (1991), "Voyaga etmaganlar grafigi. X. Daraxtlarning parchalanishiga to'siqlar", Kombinatorial nazariya jurnali, B seriyasi, 52 (2): 153–190, doi:10.1016 / 0095-8956 (91) 90061-N, JANOB  1110468.
• Robertson, Nil; Seymur, P. D. (1993), "Grafikni bitta o'tish joyidan tashqari", Robertsonda, Nilda; Seymur, Pol (tahr.), Grafika tuzilishi nazariyasi: Proc. AMS – IMS – SIAM Kichik grafikalar bo'yicha qo'shma yozgi tadqiqot konferentsiyasi, Zamonaviy matematika, 147, Amerika Matematik Jamiyati, 669-675 betlar, doi:10.1090 / conm / 147/01206, JANOB  1224738.
• Robertson, Nil; Seymur, P. D. (1994), "Grafika kichiklari. XI. Sirtdagi elektronlar", Kombinatorial nazariya jurnali, B seriyasi, 60 (1): 72–106, doi:10.1006 / jctb.1994.1007, JANOB  1256585.
• Robertson, Nil; Seymur, P. D. (1995), "Voyaga etmaganlar grafigi. XII. Sirtdagi masofa", Kombinatorial nazariya jurnali, B seriyasi, 64 (2): 240–272, doi:10.1006 / jctb.1995.1034, JANOB  1339851.
• Robertson, Nil; Seymur, P. D. (1995), "Voyaga etmaganlar grafigi. XIII. Bir-biridan ajratilgan yo'llar muammosi", Kombinatoriya nazariyasi jurnali, B seriyasi, 63 (1): 65–110, doi:10.1006 / jctb.1995.1006, JANOB  1309358.
• Robertson, Nil; Seymur, P. D. (1995), "Voyaga etmaganlarning grafigi. XIV. Joylashtirishni kengaytirish", Kombinatorial nazariya jurnali, B seriyasi, 65 (1): 23–50, doi:10.1006 / jctb.1995.1042, JANOB  1347339.
• Robertson, Nil; Seymur, P. D. (1996), "Voyaga etmaganlar grafigi. XV. Gigant qadamlar", Kombinatorial nazariya jurnali, B seriyasi, 68 (1): 112–148, doi:10.1006 / jctb.1996.0059, JANOB  1405708
• Robertson, Nil; Seymur, P. D. (2003), "Kichik graflar. XVI. Yassi bo'lmagan grafik bundan mustasno", Kombinatoriya nazariyasi jurnali, B seriyasi, 89 (1): 43–76, doi:10.1016 / S0095-8956 (03) 00042-X, JANOB  1999736.
• Robertson, Nil; Seymur, P. D. (1999), "Voyaga etmaganlar grafigi. XVII. Girdobni tamirlash", Kombinatorial nazariya jurnali, B seriyasi, 77 (1): 162–210, doi:10.1006 / jctb.1999.1919, JANOB  1710538.
• Robertson, Nil; Seymur, Pol (2003), "Voyaga etmaganlar grafigi. XVIII. Daraxtlar parchalanishi va yaxshi kvaziga tartib berish", Kombinatorial nazariya jurnali, B seriyasi, 89 (1): 77–108, doi:10.1016 / S0095-8956 (03) 00067-4, JANOB  1999737.
• Robertson, Nil; Seymur, P. D. (2004), "Voyaga etmaganlar grafigi. XIX. Er yuzasida yaxshi kvazi-tartiblash", Kombinatorial nazariya jurnali, B seriyasi, 90 (2): 325–385, doi:10.1016 / j.jctb.2003.08.005, JANOB  2034033.
• Robertson, Nil; Seymur, P. D. (2004), "Voyaga etmaganlar grafigi. XX. Vagnerning gumoni", Kombinatorial nazariya jurnali, B seriyasi, 92 (2): 325–357, doi:10.1016 / j.jctb.2004.08.001, JANOB  2099147.
• Robertson, Nil; Seymur, Pol (2009), "Grafika voyaga etmaganlar. XXI. Noyob bog'lanishli grafikalar", Kombinatoriya nazariyasi jurnali, B seriyasi, 99 (3): 583–616, doi:10.1016 / j.jctb.2008.08.003, JANOB  2507943.
• Robertson, Nil; Seymur, Pol (2012), "Voyaga etmaganlar grafigi. XXII. Bog'lanish muammolarida ahamiyatsiz tepalar", Kombinatoriya nazariyasi jurnali, B seriyasi, 102 (2): 530–563, doi:10.1016 / j.jctb.2007.12.007, JANOB  2885434.
• Robertson, Nil; Seymur, Pol (2010), "XXIII grafika. Nash-Uilyamsning immersion gipotezasi", Kombinatorial nazariya jurnali, B seriyasi, 100 (2): 181–205, doi:10.1016 / j.jctb.2009.07.003, JANOB  2595703.
• Vagner, Klaus (1937), "Über eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik, 2: 280–285.