Thrackle - Thrackle - Wikipedia

A qoqish bu ko'mish a grafik tekislikda, shunday qilib har bir qirrasi a Iordaniya yoyi va har bir chekka jufti bir marta to'g'ri keladi. Yon tomonlar umumiy uch nuqtada uchrashishi mumkin, yoki umumiy nuqta yo'q bo'lsa, ichki qismlarining bir nuqtasida uchrashishi mumkin. Ikkinchi holatda, o'tish joyi bo'lishi kerak ko'ndalang.[1]

Lineer tirgaklar

A chiziqli tirnoq uning qirralari to'g'ri chiziq bo'laklari bo'ladigan tarzda chizilgan qisqich. Har qanday chiziqli tirgakning tepaliklari qadar ko'p qirralari bor, buni kuzatgan narsa Pol Erdos. Erdo's, agar vertex bo'lsa, buni kuzatdi v uch yoki undan ortiq qirralarga ulangan vw, vxva vy chiziqli tirgakda, u holda bu qirralarning kamida bittasi ikkita boshqa qirralarni ajratib turadigan chiziqda yotadi; umumiylikni yo'qotmasdan, deb o'ylayman vw bilan shunday chekka x va y chiziq bilan chegaralangan qarama-qarshi yopiq yarim bo'shliqlarda yotish vw. Keyin, w bo'lishi shart daraja bittasi, chunki undan boshqa chekka yo'q vw ikkalasiga ham tegishi mumkin vx va vy. Olib tashlash w qirg'oqlar va tepalar sonlari orasidagi farqni o'zgartirmasdan kichikroq tirgak hosil qiladi. Boshqa tomondan, agar har bir tepada ko'pi bilan ikkita qo'shni bo'lsa, u holda qo'l siqish lemmasi qirralarning soni ko'pi bilan tepalar soni.[2] Erdo'sning dalillariga asoslanib, har bir chiziqli tirgak a pseudoforest. Toq uzunlikdagi har bir tsikl chiziqli tirgakni hosil qilish uchun tartibga solinishi mumkin, ammo bu juft uzunlikdagi tsikl uchun mumkin emas, chunki agar tsiklning bir chekkasi o'zboshimchalik bilan tanlansa, boshqa tsikl uchlari chiziqning qarama-qarshi tomonlarida o'zgarib turishi kerak bu chekka orqali.

Micha Perles chiziqli tirgaklar ko'pi bilan yana bir oddiy dalilni taqdim etdi n chiziqlar, har bir chekkaning chekka qismi maksimal 180 ° burchakka teng bo'lgan so'nggi nuqtaga ega bo'lishiga va shu oraliq ichida soat yo'nalishi bo'yicha eng chekka bo'lishiga asoslanadi. Agar yo'q bo'lsa, qirralarning qarama-qarshi so'nggi nuqtalariga tushgan va chiziqning bir-biridan o'tolmaydigan qarama-qarshi tomonlarida yotadigan ikkita qirralar bo'lar edi. Ammo har bir tepalik bu xususiyatga faqat bitta qirraga nisbatan ega bo'lishi mumkin, shuning uchun qirralarning soni ko'pi bilan tepalar soniga teng bo'ladi.[3]

Erdos ham kuzatganidek, juftlikni amalga oshiruvchi nuqtalar to'plami diametri nuqta to'plami chiziqli tirgakni hosil qilishi kerak: har ikkala diametrni bir-biridan ajratish mumkin emas, chunki agar ular bo'lsa, ularning to'rtta so'nggi nuqtalari ikkala ajratilgan qirralardan uzoqroq masofada juftlikka ega bo'lar edi. Shu sababli, har bir to'plam n tekislikdagi nuqtalar eng ko'p bo'lishi mumkin n diametral juftliklar, tomonidan 1934 yilda berilgan savolga javob beradi Xaynts Xopf va Erika Pannvits.[4] Endryu Vazsonyi diametri juftlari sonini kattaroq o'lchamlarda taxmin qiladigan chegaralar, bu muammoni umumlashtirmoqda.[2]

Yilda hisoblash geometriyasi, usuli aylanadigan kalibrlar ning har qanday nuqtalaridan chiziqli tirgak hosil qilish uchun foydalanish mumkin qavariq holat ga teng bo'lgan parallel chiziqlarni qo'llab-quvvatlaydigan juft juftlarni ulash orqali qavariq korpus ochkolar.[5] Ushbu grafada subgraf sifatida diametrli juftlik uchburchagi mavjud.[6]

Qarorni echish uchun chiziqli tirgaklar ro'yxati qo'llanilishi mumkin eng katta kichik ko'pburchak muammoni topish n-gon, uning diametriga nisbatan maksimal maydoni.[7]

Thrackle gipotezasi

Savol, Veb Fundamentals.svgMatematikada hal qilinmagan muammo:
Qo'rg'oshin tepaliklardan ko'ra ko'proq qirralarga ega bo'lishi mumkinmi?
(matematikada ko'proq hal qilinmagan muammolar)
6 tsikli grafigini joylashtirish.

John H. Conway har qanday tirgakda qirralarning soni ko'pi bilan vertikallar soniga teng bo'ladi deb taxmin qildilar. Konveyning o'zi terminologiyadan foydalangan yo'llar va dog'lar (uchun qirralar va tepaliklar mos ravishda), shuning uchun Konveyning taktik gumoni dastlab shaklda ko'rsatilgan edi har bir tirnoq kamida yo'llar kabi ko'p joylarga ega. Konvey ushbu gipotezani isbotlagani yoki inkor qilgani uchun 1000 AQSh dollari miqdoridagi mukofotni taqdim etdi, shuningdek, mukofot muammolari to'plamining bir qismi sifatida Konveyning 99-grafigi muammosi, minimal masofa Danzer setni amalga oshirmoqda va g'olib Sylver tanga harakatdan keyin 16.[8]

Bunga teng ravishda, gumbaz gumoni quyidagicha ifodalanishi mumkin har bir tirnoq a pseudoforest. Aniqroq aytadigan bo'lsak, agar tirnoq gumoni rost bo'lsa, tirgaklar Vudollning natijasi bilan aniq tavsiflanishi mumkin: ular to'rtta uzunlikdagi tsikl va ko'pi bilan bitta g'alati tsikl bo'lmagan yolg'on o'rmonlardir.[1][9]

C dan boshqa har qanday tsikl grafigi ekanligi isbotlangan4 giperturkaga ega, bu gumonning ekanligini ko'rsatadi o'tkir. Ya'ni, yo'llar bilan bir xil miqdordagi dog'larga ega bo'lgan tirgaklar mavjud. Boshqa tomondan, eng yomon stsenariy - bu dog'lar soni yo'llarning sonidan ikki baravar ko'p; bunga erishish mumkin.

G'ildirak gipotezasi har bir qirrasi an bo'ladigan tarzda chizilgan tirgaklar uchun to'g'ri ekanligi ma'lum x- har bir vertikal chiziq bilan ko'pi bilan bir marta kesib o'tgan monoton egri.[3]

Ma'lum bo'lgan chegaralar

Lovásh, Pach & Szegedy (1997) buni har kim isbotladi ikki tomonlama tirnoq a planar grafik, lekin tekislik bilan chizilmagan bo'lsa ham.[1] Natijada, ular har bir grafika n tepaliklar maksimal 2 ga egan - 3 chekka. O'shandan beri ushbu bog'lash bir necha bor yaxshilandi. Birinchidan, u 3 ga yaxshilandi (n − 1)/2,[10] va yana bir yaxshilanish taxminan 1.428 chegarasiga olib keldin.[11] Bundan tashqari, natijani isbotlash uchun ishlatiladigan usul har qanday ε> 0 uchun (1 + ε) chegarasini yaxshilaydigan cheklangan algoritmni beradi.n yoki taxminni rad etadi. Hozirgi rekord tufayli Fulek & Pach (2017), 1.3984 chegarasini isbotlagann.[12]

Agar gumon yolg'on bo'lsa, minimal qarshi misol vertexni bo'lishadigan ikkita juft tsiklga ega bo'ladi.[9] Shuning uchun gumonni isbotlash uchun ushbu turdagi grafikalarni tirgak sifatida chizish mumkin emasligini isbotlash kifoya.

Adabiyotlar

  1. ^ a b v Lovasz, L.; Pach, J.; Szegdi, M. (1997), "Konveyning taklit gipotezasida", Diskret va hisoblash geometriyasi, 18 (4): 369–376, doi:10.1007 / PL00009322, JANOB  1476318. Ushbu natijalarning dastlabki versiyasi ko'rib chiqildi O'Rourke, J. (1995), "Hisoblash geometriya ustuni 26", ACM SIGACT yangiliklari, 26 (2): 15–17, arXiv:cs / 9908007, doi:10.1145/202840.202842.
  2. ^ a b Erdos, P. (1946), "Masofalar to'plamlari to'g'risida n ochkolar " (PDF), Amerika matematik oyligi, 53: 248–250, doi:10.2307/2305092.
  3. ^ a b Pach, Xanos; Sterling, Etan (2011), "Konveyning monoton tirgaklar uchun gumoni", Amerika matematik oyligi, 118 (6): 544–548, doi:10.4169 / amer.math.monthly.118.06.544, JANOB  2812285.
  4. ^ Hopf, H.; Pannvits, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114.
  5. ^ Eppshteyn, Devid (1995 yil may), "Aylanadigan kaliper grafigi", Geometriya
  6. ^ Aylanadigan kalibrli grafada barcha diametrli juftliklar borligi uchun qarang Shamos, Maykl (1978), Hisoblash geometriyasi (PDF), Doktorlik dissertatsiyasi, Yel universiteti. Diametr juftliklari siqishni hosil qilishi uchun, masalan, qarang. Pach va Sterling (2011).
  7. ^ Grem, R. L. (1975), "Eng katta olti burchak" (PDF), Kombinatorial nazariya jurnali, A seriyasi, 18: 165–170, doi:10.1016/0097-3165(75)90004-7.
  8. ^ Konvey, Jon H., 1000 dollarlik beshta muammo (2017 yil yangilanish) (PDF), Butun sonlar ketma-ketligining onlayn entsiklopediyasi, olingan 2019-02-12
  9. ^ a b Vudoll, D. R. (1969), "Tugmachalar va boshi berk", Uelsda, D. J. A. (tahr.), Kombinatorial matematika va uning qo'llanilishi, Academic Press, 335–348 betlar, JANOB  0277421.
  10. ^ Keyns, G .; Nikolayevskiy, Y. (2000), "Umumlashtiriladigan tirgaklar chegaralari", Diskret va hisoblash geometriyasi, 23 (2): 191–206, doi:10.1007 / PL00009495, JANOB  1739605.
  11. ^ Fulek, R .; Pach, J. (2011), "Konveyning taklit gipotezasiga hisoblash yondashuvi", Hisoblash geometriyasi, 44 (6–7): 345–355, arXiv:1002.3904, doi:10.1007/978-3-642-18469-7_21, JANOB  2785903.
  12. ^ Fulek, R .; Pach, J. (2017), Thrackles: yaxshilangan yuqori chegara, Xalqaro grafika chizish va tarmoqni vizualizatsiya qilish bo'yicha simpozium, 160–166 betlar, arXiv:1708.08037, doi:10.1007/978-3-319-73915-1_14.

Tashqi havolalar