Haven (grafika nazariyasi) - Haven (graph theory)

Yilda grafik nazariyasi, a jannat to'plamlari bo'yicha ma'lum bir funktsiya turi tepaliklar ichida yo'naltirilmagan grafik. Agar panoh mavjud bo'lsa, uni evader yutib olish uchun ishlatishi mumkin ta'qib qilishdan qochish o'yinning har bir bosqichida funktsiyaga murojaat qilib, xavfsiz tepaliklar to'plamini aniqlash uchun harakat qiling. Havenlar birinchi tomonidan taqdim etilgan Seymur va Tomas (1993) xarakterlash vositasi sifatida kenglik grafikalar.[1] Ularning boshqa dasturlari mavjudligini isbotlashni o'z ichiga oladi kichik ajratgichlar kuni kichik-yopiq grafikalar oilalari,[2] va xarakterlovchi tugaydi va klik voyaga etmaganlar ning cheksiz grafikalar.[3][4]

Ta'rif

Agar G bu yo'naltirilmagan grafik va X bu tepaliklar to'plami, keyin an X-flap bo'sh emas ulangan komponent subgrafasining G o'chirish orqali hosil bo'lgan X. A jannat tartib k yilda G funktsiya β tayinlaydi X-flap β(X) har bir to'plamga X kamroq k tepaliklar. Ushbu funktsiya, shuningdek, turli xil mualliflar tomonidan turli xil berilgan qo'shimcha cheklovlarni qondirishi kerak k deyiladi buyurtma jannat.[5]

Seymur va Tomasning asl ta'rifida,[1] har ikki qopqoqni qondirish uchun jannat kerak β(X) va β(Y) bir-biriga tegishi kerak: yoki ular umumiy tepalikka ega yoki har bir qopqoqda bitta so'nggi nuqta bo'lgan chekka mavjud. Keyinchalik Alon, Seymur va Tomas tomonidan qo'llanilgan ta'rifda,[2] Buning o'rniga zaif odamni qondirish uchun jannatmakon joylar talab qilinadi monotonlik mulk: agar X ⊆ Yva ikkalasi ham X va Y dan kamrog'iga ega k tepaliklar, keyin β(Y) ⊆ β(X). Teginish xususiyati monotonlik xususiyatini nazarda tutadi, lekin aksincha emas. Biroq, bu Seymur va Tomas natijalaridan kelib chiqadi[1] cheklangan grafikalarda, agar monotonlik xususiyatiga ega jannat mavjud bo'lsa, unda bir xil tartibda va tegish xususiyatiga ega bo'lgan kishi ham mavjud.

To'rtta buyurtma. Ushbu janjal har xil to'plamni xaritada aks ettiradi X ning noyob bog'langan komponentiga uchta yoki undan kam tepaliklarning G  X brambordan kamida bitta subgrafani o'z ichiga oladi.

Ta'sirchan ta'rifga ega bo'lgan makonlar bilan chambarchas bog'liq toshlar, barchasi bir-biriga tegib turadigan, berilgan grafikaning bog'langan subgrafalari oilalari. Bramble tartibi - bu oiladagi barcha subgrafalarni uradigan tepalar to'plamida zarur bo'lgan eng kam tepalar soni. Qopqoqlarning to'plami β(X) buyurtma panohi uchun k (ta'sirchan ta'rifi bilan) hech bo'lmaganda tartibsizliklarni shakllantiradi k, chunki har qanday to'plam Y kamroq k tepaliklar subgrafani urolmayapti β(Y). Aksincha, har qanday tartibsizliklardan k, belgilash orqali bir xil tartibdagi jannat qurish mumkin β(X) (har bir tanlov uchun X) bo'lish X- buzilib ketgan barcha subgrafalarni o'z ichiga olgan flapX. Brambldagi subgrafalarning barchasi bir-biriga tegishi kerakligi shuni ko'rsatishi mumkin X-flap mavjud va barcha qopqoqlar β(X) shu tarzda tanlanganlar bir-biriga tegadi. Shunday qilib, grafika tartibsizliklarga ega k agar u faqat buyurtma panohiga ega bo'lsak.

Misol

Misol tariqasida, ruxsat bering G to'qqiz vertex bo'ling panjara grafigi. 4 dyuymli buyurtma jannatini aniqlang G, har bir to'plamni xaritalash X uchta yoki undan kam tepaliklarning an X-flap β(X), quyidagicha:

  • Agar noyob narsa bo'lsa X- har qandayidan kattaroq qopqoq X-flaps, ruxsat bering β(X) unchalik katta bo'lmasin X-flap.
  • Aks holda, tanlang β(X) o'zboshimchalik bilan har qanday bo'lish X-flap.

A tomonidan tasdiqlash to'g'ridan-to'g'ri ishni tahlil qilish bu funktsiya β jannatning zarur monotonlik xususiyatini qondiradi. Agar X ⊆ Y va X ikkitadan kam tepalikka ega yoki X panjaraning burchak tepaligining ikkita qo'shnisi bo'lmagan ikkita tepalikka ega, keyin bitta bittasi bor X-flap va u har birini o'z ichiga oladi Y-flap. Qolgan holatda, X burchak vertexining ikkita qo'shnisidan iborat va ikkitasiga ega X-flaps: biri burchak burchagidan iborat, ikkinchisi (sifatida tanlangan) β(X)) qolgan oltita tepalikdan iborat. Qaysi tepalikka qo'shilishidan qat'iy nazar X shakllantirmoq Y, bo'ladi Y- kamida to'rtta tepalikka ega bo'lgan flap, bu eng katta qopqoq bo'lishi kerak, chunki unda vertikallarning yarmidan ko'pi mavjud Y. Bu katta Y-flap quyidagicha tanlanadi β(Y) ning pastki qismi bo'ladi β(X). Shunday qilib, har holda monotonlik saqlanib qoladi.

Izlashdan qochish

Havens a evader uchun strategiyalarning ma'lum bir sinfini modellashtiradi ta'qib qilishdan qochish kamroq bo'lgan o'yin k ta'qibchilar bitta evaderni qo'lga olishga urinadilar, ta'qib qiluvchilar va qochganlar ikkalasi ham berilgan yo'naltirilgan grafaning tepalari bilan cheklangan va ta'qibchilar va evaderlarning pozitsiyalari ikkala o'yinchiga ma'lum. O'yinning har bir harakatida grafning o'zboshimchalik bilan vertikaliga yangi ta'qibchi qo'shilishi mumkin (agar kamroq bo'lsa) k ta'qibchilar istalgan vaqtda grafikka joylashtiriladi) yoki allaqachon qo'shib qo'yilgan ta'qibchilardan biri grafikadan olib tashlanishi mumkin. Biroq, yangi ta'qibchi qo'shilishidan oldin, qochib ketgan odamga avval yangi joyi to'g'risida xabar beriladi va grafaning chekkalari bo'ylab har qanday egasiz tepaga o'tishi mumkin. Harakatlanayotganda evader ta'qibchilarning birortasi egallab olgan tepalikdan o'tmasligi mumkin.

Agar a k- haven (monotonlik xususiyati bilan) mavjud bo'lsa, u holda evader abadiy qo'lga tushishdan saqlanib qolishi va o'yinni har doim bir tepalikka o'tib yutishi mumkin. β(X) qayerda X - harakat oxirida ta'qibchilar egallab oladigan tepaliklar to'plami. Jannatning monotonlik xususiyati grafaning tepasiga yangi ta'qibchi qo'shilganda, tepaliklar β(X) har doim evaderning hozirgi holatidan erishish mumkin.[1]

Masalan, qochib ketgan kishi ushbu o'yinda uchta ta'qibchiga qarshi g'alaba qozonishi mumkin 3 × 3 misolda tasvirlangan 4-tartibli jannat bilan ushbu strategiyani bajarish orqali panjara. Shu bilan birga, xuddi shu grafada to'rtta ta'qibchilar har doim qochib ketuvchini qo'lga olishlari mumkin, birinchi navbatda panjarani ikkita uchta vertikal yo'lga bo'linadigan uchta tepalikka o'tib, keyin evaderni o'z ichiga olgan yo'lning markaziga o'tib, evaderni biriga majbur qilishadi. burchak cho'qqilari va nihoyat bu burchakka yaqin bo'lmagan ta'qibchilardan birini olib tashlab, evaderga qo'ydi. Shuning uchun 3 × 3 panjara 5-buyurtma jannatiga ega bo'lishi mumkin emas.

Ta'sirchan xususiyatga ega panjurlar evaderga bir vaqtning o'zida egallab olingan tepaliklarning ikkinchisiga ikkinchisiga sakrashi mumkin bo'lgan yanada kuchli ta'qibchilarga qarshi o'yinda g'alaba qozonishiga imkon beradi.[1]

Kenglik, ajratgichlar va voyaga etmaganlarga ulanish

Havenlarni xarakterlash uchun ishlatilishi mumkin kenglik grafikalar: grafada tartib bor k agar u faqat kamida kengligi bo'lsa k − 1. Daraxt dekompozitsiyasi xuddi shu ta'qibdan qochish o'yinida ta'qibchilar uchun g'alaba qozonish strategiyasini tavsiflash uchun ishlatilishi mumkin, shuning uchun grafada tartib borligi haqiqatdir k agar faqat evader eng kam o'yinda eng yaxshi o'yinda g'alaba qozonsa k ta'qib qiluvchilar. Evader g'alaba qozongan o'yinlarda har doim jannat tomonidan ta'riflangan shaklda eng maqbul strategiya mavjud va ta'qib qiluvchi tomonidan yutilgan o'yinlarda har doim daraxtlarning parchalanishi bilan tavsiflangan shaklda optimal strategiya mavjud.[1] Masalan, chunki 3 × 3 panjara 4-tartibli jannatga ega, ammo 5-darajali jannatga ega emas, uning aniq kengligi 3 ga teng bo'lishi kerak. Xuddi shu min-max teoremasini quyidagicha umumlashtirish mumkin cheksiz grafikalar cheklangan kenglik, pastki daraxtning nursiz bo'lishi talab qilinadigan kenglik ta'rifi bilan (ya'ni, yo'q tugaydi ).[1]

Havens, shuningdek, mavjudligi bilan chambarchas bog'liq ajratgichlar, kichik to'plamlar X tepaliklarning an n-vertex grafigi shundayki, har biri X-flap maksimal 2 ga egan/ 3 tepalik. Agar grafik G yo'q k-vertex ajratgich, keyin har bir to'plam X ko'pi bilan k tepaliklar (noyob) X-flap 2 dan ortiqn/ 3 tepalik. Ushbu holatda, G tartib bor k + 1, unda β(X) bu noyob kattaligi aniqlangan X-flap. Ya'ni, har bir grafikda kichik ajratuvchi yoki yuqori darajadagi jannat mavjud.[2]

Agar grafik G tartib bor k, bilan k ≥ h3/2n1/2 butun son uchun h, keyin G ham bo'lishi kerak to'liq grafik Kh kabi voyaga etmagan. Boshqacha qilib aytganda Xadviger raqami ning n- tartibli jannatga ega vertex grafigi k hech bo'lmaganda k2/3n−1/3. Natijada, Kh-minoratsiz grafikalar kengligi kamroq h3/2n1/2 va undan kichik o'lchamdagi ajratgichlar h3/2n1/2. Umuman olganda O (√n) tavsiflanishi mumkin bo'lgan har qanday noan'anaviy grafikalar oilasi uchun kenglik va ajratuvchi kattalikka bog'liq taqiqlangan voyaga etmaganlar, chunki har qanday bunday oila uchun doimiy mavjud h oilani o'z ichiga olmaydi Kh.[2]

Cheksiz grafikalarda

Agar grafik G nurni o'z ichiga oladi, boshi tepalikka ega, ammo oxiri uchi bo'lmagan yarim cheksiz oddiy yo'l, unda tartib panohi bor ℵ0: ya'ni funktsiya β har bir cheklangan to'plamni xaritada aks ettiradi X tepaliklarning an Xjannatlarning mustahkamlik holatini qondiradigan qopqoq. Ya'ni, aniqlang β(X) noyob bo'lish X- nurning cheksiz ko'p uchlarini o'z ichiga olgan qopqoq. Shunday qilib, cheksiz grafikalar holatida, kenglik va panohlar orasidagi aloqa buziladi: bitta nur, o'zi daraxt bo'lishiga qaramay, barcha cheklangan buyurtmalarning panohlariga ega va hatto kuchliroq tartib panohiga ega.0. Agar cheksiz tepaliklar to'plami bo'lmasa, cheksiz grafikaning ikkita nurlari teng deb hisoblanadi ajratadi bir nurning cheksiz ko'p uchlari boshqa nurning cheksiz ko'p uchlaridan; bu ekvivalentlik munosabati va uning ekvivalentlik darslari deyiladi tugaydi grafikning

Har qanday grafaning uchlari uning tartib tartiblari with bilan bittadan yozishmada0. Chunki har bir nur jannatni belgilaydi va har ikki teng keladigan nur bir xil panohni belgilaydi.[3] Aksincha, har bir jannat shu tarzda nur bilan aniqlanadi, buni quyidagi holatlar tahlili ko'rsatishi mumkin:

  • Agar jannatda kesishgan xususiyat mavjud bo'lsa (bu erda kesishish barcha cheklangan to'plamlar bo'ylab joylashgan X) o'zi cheksiz to'plamdir S, keyin vertex bilan tugaydigan har bir cheklangan oddiy yo'l S ning qo'shimcha vertikaliga erishish uchun kengaytirilishi mumkin S, va ushbu kengayish jarayonini takrorlash cheksiz ko'p tepaliklardan o'tuvchi nur hosil qiladi S. Ushbu nur berilgan jannatni aniqlaydi.
  • Boshqa tomondan, agar S cheklangan, keyin (subgrafada ishlash orqali) G  S) bo'sh deb taxmin qilish mumkin. Bunday holda, har bir cheklangan to'plam uchun Xmen tepaliklarning cheklangan to'plami mavjud Xmen + 1 mulk bilan Xmen dan ajratilgan . Agar qaroqchi jannat tomonidan belgilangan qochish strategiyasiga rioya qilsa va politsiya ushbu to'plamlar ketma-ketligi bilan berilgan strategiyaga amal qilsa, u holda qaroqchi tomonidan ta'qib qilingan yo'l jannatni belgilaydigan nurni hosil qiladi.[4]

Shunday qilib, nurlarning har bir ekvivalentlik sinfi noyob panohni belgilaydi va har bir jannat nurlarning ekvivalentlik sinfi bilan belgilanadi.

Har qanday kishi uchun asosiy raqam , cheksiz grafik G a tartibli jannatga ega va agar u bo'lsa klik voyaga etmagan buyurtma κ. Ya'ni, hisoblanmaydigan kardinalliklar uchun jannatning eng katta tartibi G bo'ladi Xadviger raqami ning G.[3]

Adabiyotlar

  1. ^ a b v d e f g Seymur, Pol D.; Tomas, Robin (1993), "Grafik izlash va daraxt kengligi uchun min-maks teoremasi", Kombinatoriya nazariyasi jurnali, B seriyasi, 58 (1): 22–33, doi:10.1006 / jctb.1993.1027.
  2. ^ a b v d Alon, Noga; Seymur, Pol; Tomas, Robin (1990), "Planar bo'lmagan grafikalar uchun ajratuvchi teorema", J. Amer. Matematika. Soc., 3 (4): 801–808, doi:10.1090 / S0894-0347-1990-1065053-0.
  3. ^ a b v Robertson, Nil; Seymur, Pol; Tomas, Robin (1991), "Cheksiz voyaga etmaganlar bundan mustasno", Diskret matematika, 95 (1–3): 303–319, doi:10.1016 / 0012-365X (91) 90343-Z, JANOB  1141945.
  4. ^ a b Diestel, Reynxard; Kuh, Daniela (2003), "Grafik-nazariy va grafiklarning topologik uchlari", Kombinatorial nazariya jurnali, B seriyasi, 87 (1): 197–206, doi:10.1016 / S0095-8956 (02) 00034-5, JANOB  1967888.
  5. ^ Jonson, Thor.; Robertson, Nil.; Seymor, P.D.; Tomas, Robin (2001), "Daraxtning kengligi", Kombinatoriya nazariyasi jurnali, B seriyasi, 82 (1): 138–155, doi:10.1006 / jctb.2000.2031.