Turáns g'isht zavodi muammosi - Turáns brick factory problem - Wikipedia

Savol, Veb Fundamentals.svgMatematikada hal qilinmagan muammo:
Zarankievich tomonidan berilgan sondan kamroq o'tish joylari bilan har qanday to'liq ikki tomonlama grafik chizish mumkinmi?
(matematikada ko'proq hal qilinmagan muammolar)
Ning optimal chizmasi K4,7, 18 ta o'tish joyi bilan (qizil nuqta)

In matematika ning grafik rasm, Turan g'isht zavodi muammosi deb so'raydi o'tish joylarining minimal soni a rasmida to'liq ikki tomonlama grafik. Muammo nomi bilan nomlangan Pal Turan, Ikkinchi Jahon urushi paytida g'isht zavodida ishlashga majbur bo'lganda uni kim tuzgan.[1]

Tomonidan topilgan rasm usuli Kazimyerz Zarankievich har bir to'liq ikki tomonlama grafik uchun to'g'ri javobni berish uchun taxmin qilingan va bu haqiqat degan ibora " Zarankievich o'tish gipotezasi. Gumon ochiq bo'lib qolmoqda, faqat ba'zi bir maxsus holatlar hal qilindi.[2]

Kelib chiqishi va formulasi

Davomida Ikkinchi jahon urushi, Vengriyalik matematik Pal Turan g'isht zavodida ishlashga majbur bo'ldi, vagonli g'ishtlarni pechlardan saqlash joylariga surib qo'ydi. Zavodda har bir pechdan har bir saqlash joyiga yo'llar bor edi va vagonlarni yo'llar bir-biri bilan kesib o'tgan joylarga surish qiyinroq edi. Turan ushbu vaziyatdan ilhomlanib, ushbu yo'llar orasidagi o'tish joylarini minimallashtirish uchun zavodni qanday qilib qayta qurish mumkinligini so'radi.[1]

Matematik jihatdan bu muammoni a so'rab rasmiylashtirilishi mumkin grafik rasm a to'liq ikki tomonlama grafik, vertikallari pechlarni va saqlash joylarini va qirralari har bir pechdan har bir saqlash joyiga qadar bo'lgan yo'llarni aks ettiradi.Grafik tekislikda har bir tepalik nuqta bilan, har bir chekka uning ikkita so'nggi nuqtasini bog'laydigan egri chiziq sifatida chizilgan bo'lishi kerak va yo'q tepalik, unga tegishli bo'lmagan chetga joylashtirilgan. Grafada ajratilgan ikkita qirralarning tekislikda bo'sh bo'lmagan kesishishi bo'lganida kesishish hisoblanadi. Shunday ekan, savol tug'iladi, bunday chizilgan o'tish joylarining minimal soni qancha?[2][3]

Turan ushbu muammoni shakllantirishni ko'pincha birinchi tadqiqotlardan biri sifatida tan oladi grafikalar sonlarini kesib o'tish.[4](Xuddi shu kontseptsiyaning yana bir mustaqil formulasi sotsiologiyada, rasm chizish usullarida yuz berdi sotsiogrammalar,[5] va ancha eski jumboq uchta kommunal xizmat muammosi, uchta o'choq va uchta omborxona bilan bog'liq g'isht zavodi muammosining maxsus hodisasi sifatida qaralishi mumkin.[6]) So'ngra raqamlarni kesish markaziy o'rganish ob'ekti sifatida katta ahamiyatga ega bo'ldi grafik rasm[7]va muhim vosita sifatida VLSI dizayn[8]va diskret geometriya.[9]

Yuqori chegara

Ham Zarankievich va ham Kazimierz Urbanik Turan 1952 yilda Polshada bo'lib o'tgan turli muzokaralarda g'isht zavodi muammosi haqida gapirganini ko'rgan,[3]va mustaqil ravishda nashr etilgan muammoning echimlari, o'tish joylari sonining teng formulalari bilan.[10][11]Ularning ikkalasi ham ko'rsatganidek, har doim to'liq ikki tomonlama grafikni chizish mumkin Km, n (bilan grafik m bir tomondan tepaliklar, n boshqa tomondan tepaliklar va mn ikki tomonni bir-biriga bog'laydigan qirralar) ga teng bo'lgan o'tish joylari bilan

Qurilish oddiy: joy m tepaliklar x- samolyotning eksagi, oldini olish kelib chiqishi, chapga va o'ngga nuqtalarning teng yoki deyarli teng sonlari bilan y-aksis. Xuddi shunday joy n tepaliklar y-tekislikning boshlanishidan qochib, teng yoki deyarli teng sonli nuqtalari bilan yuqorida va pastda x- keyin har bir nuqtani ulang x-aksisning har bir nuqtasiga to'g'ri chiziq segmenti bo'yicha eksa y-aksis.[3]

Biroq, ushbu formulaning eng maqbul ekanligi, ya'ni kamroq o'tish joyi bo'lgan chizmalar bo'lishi mumkin emasligi haqidagi ularning dalillari noto'g'ri edi. Bu bo'shliq nashr etilganidan o'n bir yil o'tgach, deyarli bir vaqtning o'zida aniqlanmadi Gerxard Ringel va Pol Kainen.[12]Shunga qaramay, Zarankievich va Urbanik formulasi maqbul ekanligi taxmin qilinmoqda. Bu Zarankievichning o'tish raqamlari gipotezasi sifatida tanilgan. Garchi ba'zi bir maxsus holatlar haqiqat ekanligi ma'lum bo'lsa-da, umumiy ish ochiq qolmoqda.[2]

Pastki chegaralar

Beri Km, n va Kn, m izomorfikdir, bu erda vaziyatni ko'rib chiqish kifoya m ≤ n. Bundan tashqari, uchun m ≤ 2 Zarankievich qurilishida hech qanday o'tish joyi yo'q, albatta buni amalga oshirish mumkin emas. Shunday qilib, faqatgina nodavlat holatlar - ular uchun m va n ikkalasi ham ≥ 3.

Zarankievichning taxminini isbotlashga urinish, garchi umumiy holat uchun yaroqsiz bo'lsa ham Km,n, ish uchun ishlaydi m = 3.U keyinchalik boshqa kichik qiymatlarga kengaytirildi mVa Zarankievich gipotezasi to'liq ikki tomonlama grafikalar uchun to'g'ri ekanligi ma'lum Km, n bilan m ≤ 6.[13]Gumon ham haqiqat ekanligi ma'lum K7,7, K7,8va K7,9.[14]Agar qarshi misol mavjud bo'lsa, ya'ni grafik Km, n Zarankievich bog'lovchisidan kamroq o'tishni talab qiladi, so'ngra eng kichik qarshi misolda m va n g'alati bo'lishi kerak[13]

Har bir aniq tanlov uchun m, hamma uchun taxminning haqiqati Km, n ni faqat sonli tanlovlarni sinab ko'rish orqali tekshirish mumkin n.[15]Umuman olganda, har bir to'liq bipartitli grafika bir nechta o'tish joylarini talab etishi isbotlangan (etarlicha katta grafikalar uchun) Zarankievich tomonidan berilgan sonning kamida 83%. Bular orasidagi bo'shliqni yopish pastki chegara va yuqori chegara ochiq muammo bo'lib qolmoqda.[16]

To'rtburchak kesishgan raqamlar

Agar chekkalarni o'zboshimchalik bilan egri chiziqlarga emas, balki to'g'ri chiziqli segmentlar sifatida chizish kerak bo'lsa, unda ba'zi bir grafikalar egri qirralar bilan chizilganidan ko'ra ko'proq o'tish joylariga ehtiyoj seziladi, ammo to'liq ikki tomonlama grafiklarning kesishish soni uchun Zarankievich tomonidan belgilangan yuqori chegara bo'lishi mumkin. faqat tekis qirralar yordamida erishildi. Shuning uchun, agar Zarankievichning gumoni to'g'ri bo'lsa, unda to'liq bipartitli grafikalar o'zlarining kesishgan raqamlariga teng bo'lgan to'rtburchak kesishgan raqamlarga ega.[17]

Adabiyotlar

  1. ^ a b Turan, P. (1977), "Xush kelibsiz degan yozuv", Grafika nazariyasi jurnali, 1: 7–9, doi:10.1002 / jgt.3190010105.
  2. ^ a b v Pach, Xanos; Sharir, Micha (2009), "5.1 o'tish joylari - g'isht zavodi muammosi", Kombinatorial geometriya va uning algoritmik qo'llanilishi: Alkala ma'ruzalari, Matematik tadqiqotlar va monografiyalar, 152, Amerika matematik jamiyati, 126–127 betlar.
  3. ^ a b v Beineke, Louell; Uilson, Robin (2010), "G'isht zavodi muammosining dastlabki tarixi", Matematik razvedka, 32 (2): 41–48, doi:10.1007 / s00283-009-9120-4, JANOB  2657999.
  4. ^ Fulds, L. R. (1992), Grafika nazariyasining qo'llanilishi, Universitext, Springer, p. 71, ISBN  9781461209331.
  5. ^ Bronfenbrenner, Uri (1944), "Sotsiometrik ma'lumotlarning grafik taqdimoti", Sotsiometriya, 7 (3): 283–289, doi:10.2307/2785096, JSTOR  2785096, Diagrammadagi mavzularning joylashuvi, qisman tartibsiz bo'lsa-da, asosan kesishgan chiziqlar sonini kamaytirish maqsadida sinov va xatolar bilan aniqlanadi.
  6. ^ Bona, Miklos (2011), Kombinatorika bo'ylab yurish: sanab chiqish va grafikalar nazariyasiga kirish, World Scientific, 275–277 betlar, ISBN  9789814335232. Bona jumboqni (uchta quduqqa ulanadigan uchta uy shaklida) p. 275 va p. 277, bu "rasm chizish muammosiga teng K3,3 o'tish joylari bo'lmagan tekislik yuzasida ".
  7. ^ Schaefer, Marcus (2014), "Grafalarni kesib o'tish raqami va uning variantlari: so'rovnoma", Kombinatorika elektron jurnali: # DS21CS1 maint: ref = harv (havola)
  8. ^ Leyton, T. (1983), VLSI-dagi murakkablik masalalari, Hisoblash seriyasining asoslari, Kembrij, MA: MIT Press
  9. ^ Sekeli, L. A. (1997), "Diskret geometriyadagi sonlarni kesish va Erdo'ning qattiq muammolari", Kombinatorika, ehtimollik va hisoblash, 6 (3): 353–358, doi:10.1017 / S0963548397002976, JANOB  1464571
  10. ^ Zarankievich, K. (1954), "P. Turonning grafikalar bilan bog'liq muammosi to'g'risida", Fundamenta Mathematicae, 41: 137–145, JANOB  0063641.
  11. ^ Urbanik, K. (1955), "Solution du problème posé par P. Turan", Kolloq. Matematika., 3: 200–201. Iqtibos sifatida Sekeli, Laszló A. (2001) [1994], "Zarankievich kesishgan gipotezasi", Matematika entsiklopediyasi, EMS Press
  12. ^ Yigit, Richard K. (1969), "Zarankievich teoremasining pasayishi va qulashi", Grafika nazariyasidagi isbotlash texnikasi (Prok. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, Nyu-York, 63-69 betlar, JANOB  0253931.
  13. ^ a b Kleitman, Daniel J. (1970), "ning o'tish raqami K5,n", Kombinatorial nazariya jurnali, 9: 315–323, doi:10.1016 / s0021-9800 (70) 80087-4, JANOB  0280403.
  14. ^ Vudoll, D. R. (1993), "Tsiklik tartibli grafikalar va Zarankievichning kesishgan raqam gumoni", Grafika nazariyasi jurnali, 17 (6): 657–671, doi:10.1002 / jgt.3190170602, JANOB  1244681.
  15. ^ Kristian, Robin; Rixter, R. Bryus; Salazar, Gelasio (2013), "Zarankievichning taxminlari har bir aniq uchun cheklangan m", Kombinatorial nazariya jurnali, B seriyasi, 103 (2): 237–247, doi:10.1016 / j.jctb.2012.11.001, JANOB  3018068.
  16. ^ de Klerk, E .; Maharri, J .; Pasechnik, D. V .; Rixter, R. B .; Salazar, G. (2006), "ning kesishish chegaralari yaxshilandi Km, n va Kn", Diskret matematika bo'yicha SIAM jurnali, 20 (1): 189–202, arXiv:matematik / 0404142, doi:10.1137 / S0895480104442741, JANOB  2257255.
  17. ^ Kainen, Pol S. (1968), "P. Erdos muammosi to'g'risida", Kombinatorial nazariya jurnali, 5: 374–377, doi:10.1016 / s0021-9800 (68) 80013-4, JANOB  0231744

Tashqi havolalar