Barnettlarning gumoni - Barnettes conjecture

Savol, Veb Fundamentals.svgMatematikada hal qilinmagan muammo:
Har bir ikki tomonlama oddiy ko'p qirrali Hamiltoniyalikmi?
(matematikada ko'proq hal qilinmagan muammolar)

Barnettning taxminlari bu hal qilinmagan muammo yilda grafik nazariyasi, filiali matematika haqida Gamilton davrlari grafiklarda. Uning nomi berilgan Devid V. Barnette, a professor emeritus da Kaliforniya universiteti, Devis; har birida ikki tomonlama ko'p qirrali grafik bilan har bir tepada uchta chekka Gamilton tsikliga ega.

Ta'riflar

A planar grafik bu yo'naltirilmagan grafik bo'lishi mumkin ko'milgan ichiga Evklid samolyoti hech kimsiz o'tish joylari. Planar grafik deyiladi ko'p qirrali agar va faqat shunday bo'lsa 3-vertex bilan bog'langan, ya'ni ikkita tepalik bo'lmasa, ularni olib tashlash grafikning qolgan qismini uzib qo'yadi. Grafik ikki tomonlama agar uning tepalari bo'lishi mumkin bo'lsa rangli ikki xil rang bilan, har bir qirrada har bir rangning bitta so'nggi nuqtasi bo'lishi kerak. Grafik kub (yoki 3 muntazam ) agar har bir tepalik to'liq uchta qirraning so'nggi nuqtasi bo'lsa. Nihoyat, grafik Hamiltoniyalik agar uning har bir tepaligidan aniq bir marta o'tadigan tsikl mavjud bo'lsa. Barnettning gumoni shuni ko'rsatadiki, har ikki kubik bipartitli ko'p qirrali grafil Hamiltonian.

By Shtaynits teoremasi, tekislik grafigi a ning qirralari va tepalarini aks ettiradi qavariq ko'pburchak agar va ko'p qirrali bo'lsa. Uch o'lchovli ko'pburchak kubik grafikka ega, agar u a bo'lsa oddiy ko'pburchak.Va tekislik grafigi ikki tomonlama bo'ladi, agar grafika tekis joylashtirilsa, barcha yuz tsikllari teng uzunlikka ega bo'ladi. Shuning uchun Barnettning gumoni ekvivalent shaklda bayon etilishi mumkin: masalan, uch o'lchovli oddiy qavariq ko'pburchak har bir yuzida teng sonli qirralar mavjud. Keyinchalik, taxminlarga ko'ra, ko'pburchak grafigi Gamilton tsikliga ega.

Tarix

P. G. Tait  (1884 ) har bir kubik ko'pburchak grafil Gamiltonian deb taxmin qilgan; bu kabi tanilgan Taitning taxminlari. Bu tomonidan rad etildi V. T. Tutte  (1946 ) kim qurgan qarshi misol 46 ta tepalik bilan; keyinchalik boshqa tadqiqotchilar undan ham kichikroq qarshi misollarni topdilar. Biroq, ushbu ma'lum qarshi misollarning hech biri ikki tomonlama emas. Tutte o'zi har bir kubik 3 ga ulangan bipartitli grafil Hamiltonian deb taxmin qildi, ammo bu qarshi misolni topib, yolg'on ekanligini ko'rsatdi Horton grafigi.[1] Devid V. Barnette (1969 ) Tait va Tutte gipotezalarining zaiflashgan kombinatsiyasini taklif qildi, bunda har bir bipartit kubikli polidron Hamiltonian ekanligi yoki shunga teng ravishda Tait gumoniga qarshi har qanday qarshi misol ikki tomonlama bo'lmaganligi aytilgan.

Ekvivalent shakllar

Kelmans (1994)[2] Barnettning gumoni har ikki chekka uchun yuzaki kuchli bayonotga teng ekanligini ko'rsatdi e va f bipartit kubikli poliedronning xuddi shu yuzida o'z ichiga olgan Hamilton tsikli mavjud e lekin o'z ichiga olmaydi f. Shubhasiz, agar bu so'z to'g'ri bo'lsa, unda har ikki bipartitli kubikli polidrada Hamilton tsikli mavjud: shunchaki tanlang e va f o'zboshimchalik bilan. Boshqa yo'nalishlarda Kelmans qarshi namunani asl Barnette gipotezasiga qarshi namunaga aylantirish mumkinligini ko'rsatdi.

Barnettning gumoni, shuningdek, har bir kubik bipartitli ko'p qirrali grafika dualining tepalari ikkita kichik to'plamga bo'linishi mumkin degan gapga tengdir. induktsiya qilingan subgraflar daraxtlar. Ikkala grafada bunday bo'linish natijasida hosil bo'lgan kesma, boshlang'ich grafadagi Hamilton tsikliga to'g'ri keladi.[3]

Qisman natijalar

Barnett gumonining haqiqati noma'lum bo'lib qolsa-da, hisoblash tajribalari shuni ko'rsatdiki, 86 tepadan kam bo'lmagan tepalikka misol yo'q.[4]

Agar Barnettning gumoni yolg'on bo'lib chiqsa, u holda uni ko'rsatish mumkin To'liq emas bipartit kubik poliedrning gamiltonlik ekanligini tekshirish.[5] Agar tekislik grafigi ikki tomonlama va kubik bo'lsa-yu, faqat 2-ulanishdan iborat bo'lsa, u hamiltoniyalik bo'lmagan bo'lishi mumkin va bu grafikalar uchun Hamiltoniklikni sinab ko'rish uchun NP to'liq hisoblanadi.[6] Yana bir natija Alt va boshq. (2016): agar har ikkala qizil-yashil tsiklda 4-darajali tepalik bo'lishi uchun ikki tomonlama grafik vertikal rangda ko'k, qizil va yashil ranglarda bo'lishi mumkin bo'lsa, u holda boshlang'ich grafik Hamiltonian bo'ladi.

Bilan bog'liq muammolar

Barnettning tegishli gumoni shuni ko'rsatadiki, barcha yuzlari olti yoki undan kam qirralarga ega bo'lgan har bir kubik ko'p qirrali grafil Hamiltonian. Hisoblash tajribalari shuni ko'rsatdiki, agar qarshi misol mavjud bo'lsa, u 177 dan ortiq tepalikka ega bo'lishi kerak edi.[7]

Ushbu ikkita taxminning kesishishi shundaki, barcha yuzlar to'rt yoki oltita qirralarga ega bo'lgan har ikki bipartitli kubikli ko'p qirrali grafil Hamiltonian bo'ladi. Bu haqiqat ekanligi isbotlandi Gudi (1975).

Izohlar

  1. ^ Tutte (1971); Xorton (1982).
  2. ^ Qarang Alt va boshq. (2016) dalillar uchun
  3. ^ Florek (2010).
  4. ^ Xolton, Manvel va MakKey (1985); Hertel (2005).
  5. ^ Feder & Subi (2006).
  6. ^ Akiyama, Nishizeki va Saito (1980).
  7. ^ Aldred va boshq. (2000).

Adabiyotlar

  • Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980), "Ikki tomonlama grafikalar uchun Hamilton davri muammosining to'liqligi", Axborotni qayta ishlash jurnali, 3 (2): 73–76, JANOB  0596313
  • Alt, Helmut; Peyn, Maykl S.; Shmidt, Jens M.; Vud, Devid R. (2016), "Barnett gumoni haqidagi fikrlar" (PDF), Australasian Journal of Combinatorics, 64 (2): 354–365, JANOB  3442496
  • Aldred, R. E. L.; Bau, S .; Xolton, D. A .; Makkay, Brendan D. (2000), "Nonhamiltonian 3 ga bog'langan kubik planar grafikalar", Diskret matematika bo'yicha SIAM jurnali, 13 (1): 25–32, doi:10.1137 / S0895480198348665, JANOB  1737931
  • Barnette, Devid V. (1969), "Gumon 5", yilda Tutte, V. T. (tahr.), Kombinatorikadagi so'nggi yutuqlar: Kombinatorika bo'yicha uchinchi Vaterlo konferentsiyasi materiallari, 1968 yil may, Nyu-York: Academic Press, JANOB  0250896
  • Feder, Tomas; Subi, Karlos (2006), Barnettning taxminiga ko'ra, ECCC  TR06-015
  • Florek, Jan (2010), "Barnettning taxminlari to'g'risida", Diskret matematika, 310 (10–11): 1531–1535, doi:10.1016 / j.disc.2010.01.018, JANOB  2601261
  • Goodey, P. R. (1975), "Yuzlari bir tekis bo'lgan politoplarda gamilton sxemalari", Isroil matematika jurnali, 22 (1): 52–56, doi:10.1007 / BF02757273, JANOB  0410565
  • Hertel, Aleksandr (2005), Barnettning taxminlarini o'rganish va mustahkamlash (PDF)
  • Xolton, D. A .; Manvel, B .; McKay, B. D. (1985), "Hamiltonian tsikllari kubik 3 ga ulangan ikki tomonlama planar grafikalar", Kombinatorial nazariya jurnali, B seriyasi, 38 (3): 279–297, doi:10.1016/0095-8956(85)90072-3, JANOB  0796604
  • Horton, J. D. (1982), "Ikki tomonlama muntazam grafiklarning ikki omili to'g'risida", Diskret matematika, 41 (1): 35–41, doi:10.1016 / 0012-365X (82) 90079-6, JANOB  0676860
  • Kelmans, A. K. (1994), "Hamilton tsikllarsiz kubik bipartitli 3 ta bog'langan grafiklarning konstruktsiyalari", Kelmansda, A. K. (tahr.), Diskret matematikaning tanlangan mavzulari: Moskva diskret matematika seminarining materiallari 1972-1990, Amerika matematik jamiyati tarjimalari, 2-seriya, 158, 127-140-betlar
  • Tayt, P. G. (1884), "Listing's Topologiya", Falsafiy jurnal, 5-seriya, 17: 30–46; Qayta nashr etilgan Ilmiy ishlar, Jild II, 85-98 betlar
  • Tutte, V. T. (1946), "Gamilton sxemalarida", London Matematik Jamiyati jurnali, 21 (2): 98–101, doi:10.1112 / jlms / s1-21.2.98
  • Tutte, V. T. (1971), "Ikki tomonlama grafiklarning 2-omillari to'g'risida", Diskret matematika, 1 (2): 203–208, doi:10.1016 / 0012-365X (71) 90027-6, JANOB  0291010

Tashqi havolalar