Petersens teoremasi - Petersens theorem - Wikipedia

A mukammal moslik (qizil qirralar), ichida Petersen grafigi. Petersen grafigi kub va ko'priksiz, u Petersen teoremasi shartlariga javob beradi.
Bir-biriga mukammal mos kelmaydigan kubik (lekin ko'priksiz) grafika, bu Petersen teoremasidagi ko'priksiz holatni chiqarib bo'lmaydi

In matematik intizomi grafik nazariyasi, Petersen teoremasinomi bilan nomlangan Yulius Petersen, graf nazariyasining dastlabki natijalaridan biridir va quyidagicha ifodalanishi mumkin:

Petersen teoremasi. Har bir kub, ko'priksiz grafada a mavjud mukammal moslik.[1]

Boshqacha qilib aytadigan bo'lsak, agar grafik har bir tepada to'liq uchta qirraga ega bo'lsa va har bir chekka tsiklga tegishli bo'lsa, unda u har bir tepaga to'liq bir marta tegadigan qirralarning to'plamiga ega.

Isbot

Biz har bir kubik, ko'priksiz grafikalar uchun buni ko'rsatamiz G = (V, E) Bizda har bir to'plam uchun bu bor UV grafadagi ulangan komponentlar soni induktsiya qilingan tomonidan V − U tepaliklarning toq soni bilan eng ko'p kardinallik U. Keyin Tutte teoremasi G mukammal moslikni o'z ichiga oladi.

Ruxsat bering Gmen tepaliklar to'plami tomonidan indikatsiya qilingan grafikada toq sonli tepalikka ega bo'lgan komponent bo'ling V − U. Ruxsat bering Vmen ning tepaliklarini bildiring Gmen va ruxsat bering mmen qirralarining sonini belgilang G bitta tepalik bilan Vmen va bitta tepalik U. Oddiy er-xotin hisoblash argumenti bilan biz bunga egamiz

qayerda Emen ning qirralarning to'plamidir Gmen ikkala tepalik bilan Vmen. Beri

toq son va 2|Emen| bu juft son mmen toq son bo‘lishi kerak. Bundan tashqari, beri G bizda bu beg'ubor mmen ≥ 3.

Ruxsat bering m ichida qirralarning soni bo'lsin G bitta tepalik bilan U va grafadagi bitta tepalik V − U. Toq soni tepalikka ega bo'lgan har bir komponent kamida 3 qirraga yordam beradi mva bu noyobdir, shuning uchun bunday komponentlarning soni ko'pi bilan m/3. Eng yomon holatda, bitta vertex bilan har bir chekka U hissa qo'shadi mva shuning uchun m ≤ 3|U|. Biz olamiz

holatini ko'rsatib beradi Tutte teoremasi ushlab turadi.

Tarix

Teorema bog'liqdir Yulius Petersen, daniyalik matematik. Buni birinchi natijalardan biri deb hisoblash mumkin grafik nazariyasi. Teorema birinchi bo'lib 1891 yilgi maqolada paydo bo'ladi "Die Theorie der regulären grafikalari".[1] Hozirgi me'yorlar bo'yicha Petersen teoremasini isbotlashi juda murakkab. Isbotning bir qator soddalashtirilishi tomonidan tasdiqlangan Frink (1926) va König (1936).

Zamonaviy darsliklarda Petersen teoremasi dastur sifatida keltirilgan Tutte teoremasi.

Ilovalar

  • To'liq mos keladigan kubik grafikada, mukammal mos bo'lmagan qirralar a hosil qiladi 2-omil. By yo'naltirish 2-faktor, mukammal mos keladigan qirralarning kengaytirilishi mumkin yo'llar uzunlikning uchini, masalan, tashqi tomonga yo'naltirilgan qirralarni olish bilan. Bu shuni ko'rsatadiki, har bir kubik va ko'priksiz grafika uch uzunlikdagi chekka-ajratilgan yo'llarga ajraladi.[2]
  • Buni har bir narsani ko'rsatish uchun Petersen teoremasini ham qo'llash mumkin maksimal planar grafik uzunlikdagi uchdan ajratilgan yo'llar to'plamiga ajralishi mumkin. Bu holda ikki tomonlama grafik kubik va ko'priksizdir, shuning uchun Petersen teoremasi bo'yicha unga mos keladigan moslama mavjud, bu asl grafada qo'shni uchburchak yuzlari juftligiga to'g'ri keladi. Har bir uchburchak juftligi uchburchakni qolgan to'rtburchak qirralarining ikkitasi bilan birlashtirgan qirrani o'z ichiga olgan uch uzunlikdagi yo'lni beradi.[3]
  • Petersen teoremasini a ning ikki tomonlama grafikasiga qo'llash orqali uchburchak mesh va bir-biriga mos kelmaydigan uchburchak juftlarini bog'lab, meshni tsiklikka ajratish mumkin uchburchaklar chiziqlari. Keyinchalik ba'zi bir transformatsiyalar bilan u bitta chiziqqa aylantirilishi mumkin va shuning uchun uchburchak to'rini o'zgartirishi mumkin, shunda uning er-xotin grafigi aylanadi hamiltoniyalik.[4]

Kengaytmalar

Ko'priksiz kubikli grafikalardagi mukammal mosliklar soni

Bu taxmin qilingan Lovasz va Plummer soni mukammal mosliklar tarkibida a kub, ko'priksiz grafasi grafika tepalari sonida eksponent hisoblanadi n.[5]Gumon birinchi marta isbotlangan ikki tomonlama, kubik, ko'priksiz grafikalar Voorxoev (1979), keyinroq planar, kubik, ko'priksiz grafikalar Chudnovskiy va Seymur (2012). Umumiy ish bo'yicha qaror qabul qilindi Esperet va boshq. (2011), bu erda har bir kubik, ko'priksiz grafika kamida o'z ichiga olishi ko'rsatilgan mukammal mosliklar.

Algoritmik versiyalar

Biedl va boshq. (2001) Petersen teoremasining samarali variantlarini muhokama qilish. Frinkning isboti asosida[6] ular olishadi O(n jurnal4 n) bilan kubikli, ko'priksiz grafada mukammal moslikni hisoblash algoritmi n tepaliklar. Agar grafik bundan tashqari bo'lsa planar xuddi shu qog'oz an O(n) algoritm. Ularning O(n jurnal4 n) ko'priklar to'plamini dinamik grafikada saqlash vaqtini keyingi takomillashtirish asosida vaqt chegarasi yaxshilanishi mumkin.[7] Vaqtni qisqartirishni yanada takomillashtirish O(n jurnal2 n) yoki (qo'shimcha bilan) tasodifiy ma'lumotlar tuzilmalari ) O(n jurnal n (log log n)3)tomonidan berilgan Diks va Stankzik (2010).

Oliy daraja

Agar G darajaning muntazam grafigi d kimning chekka ulanish hech bo'lmaganda d - 1 va G tepaliklarning juft soniga ega, keyin u mukammal mos keladi. Keyinchalik kuchli, har bir chekkasi G kamida bitta mukammal mos kelishga tegishli. Darajalar g'alati bo'lsa, natijada tepaliklar sonining sharti qoldirilishi mumkin, chunki u holda ( qo'l siqish lemmasi ) tepalar soni har doim ham teng.[8]

Izohlar

  1. ^ a b Petersen (1891).
  2. ^ Masalan, qarang Bouchet & Fouquet (1983).
  3. ^ Xaggkvist va Yoxansson (2004).
  4. ^ Meenakshisundaram & Eppstein (2004).
  5. ^ Lovash, Laslo; Plummer, M. D. (1986), Moslik nazariyasi, Diskret matematika yilnomalari, 29, Shimoliy Gollandiya, ISBN  0-444-87916-1, JANOB  0859549.
  6. ^ Frink (1926).
  7. ^ Thorup (2000).
  8. ^ Naddf va Pulleyblank (1981), Teorema 4, p. 285.

Adabiyotlar