To‘rt bo‘yoq muammosi Abulov Mo‘min Orziqulovich Axborot texnologiyalari va menejment universiteti dotsenti, abulov1959@mail.ru Qurbonova Zarnigor Hamza qizi Axborot texnologiyalari va menejment universiteti magistranti, zarnigorqurbonova74@gmail.com Ann

Аннотация

Ma’lumki, kibernetikaning bir qator masalalari borki, ular graflarni bo‘yash haqidagi masalalarga keladi masalan, xizmat ko‘rsatish, harakat hamda dars jadvallarini tuzish, geografik xaritalarni bo‘yash vaboshqalar [1].Maqolada xaritani bo‘yash masalasi qaralgan. Kalit so‘zlar. Graf, graflarni bo‘yash, tekis graf, to‘g‘ri 4-bo‘yash, uchlar to‘plami, qirralar to‘plami, geortagik xarita. Tushunarliki, geografik xaritani bo‘yashda iloji boricha kamroq ranglardan foydalanish maqsadga muvofiq, ammo chegaraning turli ikki tomoni bo‘lgan ikki mamlakat turli xil rangda bo‘lishi kerak. 1852-yilda Frensis Gutri Angliya grafligining xaritasini tuzar ekan, bunday maqsad uchun to‘rtta rang yetarli ekanligini payqadi, uning ukasi Fredirik bu kuzatishni mashhur matematik De Morganga, u esa matematiklar jamoasiga ma’lum qildi. Gipotezaning aniq ta’riflanishi A. Keli (Cayley,1878) tomonidan nashretilgan. Birinchi isbot bir yil o‘tgach paydo bo‘ldi va u V.Kempega tegishli edi. Oradan 11 yil o‘tgach P. Xivud isbotda xato borligini aniqladi. Ammo, P. Xivud (Heawood) ushbu isbotdan 5 ta rang haqiqatdan ham yetarli ekanligini tushundi. Birinchi noto‘g‘ri isbotdan so‘ng yana boshqa ko‘plab xato isbotlar ham kuzatildi. Masala mashhurligi jihatdan 4 rang masalasi Fermaning mashhur masalasidan keyin ikkinchi o‘rinda turardi. XX asrning o‘rtalariga qadar garchi 4 ta rang muammosi ko‘plab taniqli matematiklar tomonidan o‘rgatilgan bo‘lsada, isbotlash bilan bog‘liq vaziyat sezilarli darajada o‘zgarmadi, ya’ni isbot topilmadi. J.D.Brikgofnng g‘oyalari P.Franklinga 1913-yilda 25 dan ortiq bo‘lmagan mamlakatlardan iborat xarita uchun gipotezani (tahminni) isbotlashga imkon berdi. Keyinchalik buraqam 38taga ko‘tarildi. 1977-yilda to`rt rang haqidagi gipotezaning isboti nihoyat K. Appel va U.Xakenlar (Appel, Xaken) tomonidan topildi va u 2 ta maqolada chop etildi [2]. Bu asosiy islanishlarning (tekshiruvlarning) muhim qismi kompyuter tomonidan amalga oshirildi va u sof matematikada deduktiv fikrlashning amaliyotidagi inqilobiy yangiligi edi. Kompyuterdan foydalanish bugungi kungacha ushbu isbotga nisbatan shubhalar bo`lishi uchunasos bo‘libxizmat qiladi. Muammoningqo‘yilishi Xaritalarni globus va tekislikda bo‘yash muammolari ekvivalentdir. Haqiqatdan ham, sferadagi xaritadan (globusdan) har qanday mamlakatning ichki qismini kesib olish mumkin; xarita yupqa rezinadan qilingan deb tasavvur qilsak, teshilgan sferani deformatsiyalash (cho‘zish) orqali tekis soha shakliga keltirish mumkin. Tekis xaritada esa teshik “okean”ga aylanadi va bitta mamlakatni to‘liq ifoda etadi. Albatta cho‘zish jarayonida chegaralarning uzunligi, shakli va mamlakatlarning joylashuvi sezilarli darajada o‘zgaradi, lekin chegaralar chizig‘i saqlanib qoladi, faqat kesilgan teshikning cho‘zilgan chegarasi qo‘shiladi. Mamlakatlar va ularning chegaralaridagi bunday deformatsiyalar, tabiiyki, bo‘yash masalasini o‘zgartirmaydi. Quyida tekislikdagi xaritani, ya’ni tekisxaritani ko‘rib chiqamiz. Avvalo tekis xaritada bo‘yash masalasini unga ekvivalent bo‘lgan tekis graflardagi bo‘yash muammosiga almashtiramiz. Har bir mamlakat uchun poytaxt tanlaymiz (ya’ni, har bir mamlakatda bitta ichki nuqtasini belgilaymiz) va chegaradosh mamlakatlarning poyraxtlarini yoylar bilan tutashtiramiz.Natijada tekis graf hosilbo`ladi [1]. 1-ta’rif. G graf deb chekli V(G) uchlar to‘plami va chekli R(G) qirralar to‘plami tushuniladi,bunda, har birqirra oxirida2taturli uchlarbo‘ladi. 184 RAQAMLI TRANSFORMATSIYA SHAROITIDA SUN’IY INTELLEKTNI RIVOJLANTIRISH VA ZAMONAVIY MATEMATIKANI O‘QITISH MUAMMOLARI VA YECHIMLARI 2-ta’rif. Graf tekis graf deb ataladi, agarda uning uchlari tekislikdagi nuqtalar, qirralari esa ushbu tekislikda joylashgan uzluksiz chiziqlar (kesmalardan tashkil topgan siniq chiziqlar) bo‘lsa hamda bu qirralar bir-biri bilan kesishmaydigan va o‘z uchlaridan boshqa uchlarni ichiga olmaydigan bo‘lsa( ya’ni ularni kesibo‘tmasa). Shuni ta’kidlash kerakki, tekis graf tugunlar (ya’ni boshlanish va oxirgi nuqtasi bitta bo‘lgan qirralar) ga ega emas. Tekis graf tekislikni D(G) kesishmaydigan ko‘pburchaklardan iborat sohalarga (yoqlarga) ajratadi, busohalarni chekli bo‘lishi shart emas (1-rasm). 1-rasm. Tekis grafni 4-bo`yash Agar ishlatiladigan bo‘yoqlarni 1,2,...,n sonlar bilan nomerlab chiqsak va xaritani bo`yasak, u holda xaritaga mos tekis grafning uchlari (ya’ni xaritadagi poytaxtlar) nomerlangan bo`ladi. 3-ta’rif.Tekis grafni to‘g‘ri n -bo‘yash deganda j:V(G)®{ 1,2,...n } moslik tushiniladi, bunda agar grafdagi har bir r R(G) qirraning ikkita v va v uchlari bo‘lsa, u holda 1 2 j(v ) j(v ). 1 2 Nihoyat to‘rt rang muammosiniquyidagi teorema shaklidaifodalash mumkin. Teorema. Har qanday tekis grafni to‘g‘ri 4-bo‘yash mumkin. Bu muammoning yechilishi bir asrdan ortiq vaqtni oldi. Bu to‘rt rang teoremasi Appel va Xakenlar tomonidan isbotlandi. Bu isbot umumiy holda matematika jamoatchiligi tomonidan qabul qilingan bo‘lsada, hali-hanuzgacha ma’lum darajadagi shubha va tanqidni keltirib chiqara