RAQAMLI TRANSFORMATSIYA SHAROITIDA SUN’IY INTELLEKTNI RIVOJLANTIRISH VA
ZAMONAVIY MATEMATIKANI O‘QITISH MUAMMOLARI VA YECHIMLARI
184
TO‘RT BO‘YOQ MUAMMOSI
ABULOV MO‘MIN ORZIQULOVICH
Axborot texnologiyalari va menejment universiteti dotsenti,
QURBONOVA ZARNIGOR HAMZA QIZI
Axborot texnologiyalari va menejment universiteti magistranti,
zarnigorqurbonova74@gmail.com
Annotatsiya.
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 va boshqalar [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 nashr etilgan.
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 bu raqam 38 taga 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 uchun asos bo‘lib xizmat qiladi.
Muammoning qo‘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 tekis xaritani 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 hosil bo`ladi [1].
1-ta’rif.
G
graf deb chekli
( )
V G
uchlar to‘plami va chekli
( )
R G
qirralar to‘plami
tushuniladi, bunda, har bir qirra oxirida 2 ta turli uchlar bo‘ladi.
RAQAMLI TRANSFORMATSIYA SHAROITIDA SUN’IY INTELLEKTNI RIVOJLANTIRISH VA
ZAMONAVIY MATEMATIKANI O‘QITISH MUAMMOLARI VA YECHIMLARI
185
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 kesib o‘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, bu sohalarni 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
{
}
: ( )
1,2,...
V G
n
j
®
moslik tushiniladi,
bunda agar grafdagi har bir
( )
r R G
qirraning ikkita
1
v
va
2
v
uchlari bo‘lsa, u holda
1
2
( )
( )
v
v
j
j
.
Nihoyat to‘rt rang muammosini quyidagi teorema shaklida ifodalash 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 chiqaradi.
Matematika bilan yuzaki tanish bo‘lgan o‘quvchi uchun bu holat hayratlanarli: axir matematikada
odatda uchinchi holni istisno qilish tamoyili amal qiladi, ya’ni biror mulohaza ikkita holatda to‘g‘ri
yoki noto‘g‘ri bo‘lishi mumkin, boshqacha bo‘lishi mumkin emas. Biroq bu yerda ish bunchalik
sodda emas. Mana isbot qilgan mualliflarining o‘zlari nima deb yozishgan.” O‘quvchi 50 sahifalik
matn va diagrammalar, tahminan 2500 ta diagrammalar keltirilgan 85 sahifalik qo‘shimcha
material, yana diagrammalarni o‘z ichiga olgan 400 sahifalik mikroafisha, hamda asosiy matndagi
24 ta lemmaga asoslangan minglab alohida tasdiqlarni tahlil qilishi losim bo‘ladi. Bundan tashqari,
o‘quvchi bilishi lozimki ba’zi faktlarni tekshirish uchun1200 soatlik kompyuter vaqti sarflangan, bu
faktlarni qo‘lda tekshirilsa u yanada ko‘proq vaqt talab qilgan bo‘lardi. Ushbu maqolalar uslub va
hajm jihatidan hayratga soladi va juda kam sonli matematiklar ularni yetarlicha batafsil o‘qigan” [3].
Shunday qilib, isbotning kompyuter orqali bajarilgan qismini qo‘lda tekshirish mumkin emas,
RAQAMLI TRANSFORMATSIYA SHAROITIDA SUN’IY INTELLEKTNI RIVOJLANTIRISH VA
ZAMONAVIY MATEMATIKANI O‘QITISH MUAMMOLARI VA YECHIMLARI
186
an’anaviy(qo‘lyozma) qismi esa shunchalik uzun va murakkabki, hech kim uni to‘liq tekshirib
chiqqani yo‘q. Holbuki, tekshirib bo‘lmaydigan isbot bu mantiqsizlikdir. Bunday isbotni qabul
qilish, bu shunchaki mualliflarga ishonish bilan teng [3].
Ushbu maqolani tayyorlash jarayonida quyidagi muhim xulosalarga kelindi.
1. Graflar nazariyasi ko`plab muhim va amaliy tatbiqlarga ega.
2. Ushbu muammoni “vaqt-soati kelib” sodda va ajayib isboti topiladi.
Adabiyotlar
1. Домин Л. Н. Элементы теории графов. Пенза. Пензенского ГУ. 2007. 144 с.
2. Appel K., Haken W. Every Planar Map Is Four Colorable. Contemporary Mathematics.
Providence (R.I.): Amer. Math Soc., 1989. Vol. 98.
3. Самохин А. В. Проблема четырех красок: неоконченная история доказательства.
Соросовский образовательный журнал, том 6, № 7, 2000 г. 91 -96 с.
