Yoshligimda, 4-5 sinflar paytimda bir tipdagi masalalar juda qiziqtirgan.
Turli xil shakllar berilgan, shulardan qaysilarini qoʻlni uzmasdan, bir chiziq ustidan faqat bir martagina yurib chizish mumkin? *
Barcha chizmalarni qoʻlda chizishga harakat qilardik, ammo ba'zi chizmalarni bu shartlar bilan chizib boʻlmasdi.
Oʻylantirardi, aynan qanday shakllarni bu shartlar bilan chizib boʻlmaydi?
Shunda ustozim bir faktni aytgandi: Agar shaklning har bir uchidagi nuqtasidan juft sondagi qirralar chiqqan boʻlsa, bu shaklni (*) shartlar bilan chizib boʻladi. **
Agar toq sondagi qirralar chiqqan uchlar soni koʻpi bilan ikkita boʻlsa ham, bu shartni qanoatlantiradi. ***
Ha, bu fakt tushunarli. Lekin isbotini bilmasdim. (U davrda isbot nima ekanligini ham tushunmasdim)
Bu mening "Graflar nazariyasi"ga endi kirib kelishim edi.
Keyinchalik Universitetda 1-kurs paytimda Dr.Rustam Turdibaev ni " Graflar nazariyasi" boʻyicha videodarslarini koʻrib chiqdim. IMO-2019 ni 5-masalasi (tangalar haqidagi masala) ni graflar boʻyicha n-oʻlchamli kubdan foydalanib ajoyib
yechim ulashgan. Bu meni qiziqishimni yanada oshirdi.
Yaqindagina diskret matematika fanidan Graflar nazariyasini boshladik.
Bunda (
) Eyler grafi, (*) esa yarim Eyler grafi boʻladi ekan.
Th1: Bogʻlamli graf Eyler grafi boʻlishi uchun undagi barcha uchlarning darajalari juft boʻlishi zarur va yetarlidir.
Th2: Bogʻlamli graf yarim Eyler grafi boʻlishi uchun undagi ikkitadan koʻp boʻlmagan uchning darajari toq boʻlishi zarur va yetarlidir.
Men oʻrgangan ma'lumotlarim Eyler graflari haqida edi. Eyler graflari juda koʻp oʻrganilgan va bu haqida teoremalar anchagina.
Bundan tashqari
Gamilton grafi tushunchasi mavjud.
Grafning har bir uchidan faqat bir marta oʻtadigan zanjir
Gamilton zanjiri deb ataladi. Yopiq Gamilton zanjiriga (ya’ni Gamilton sikliga) ega graf
Gamilton grafi deb ataladi. Agar grafda yopiq boʻlmagan Gamilton zanjiri topilsa, u holda bunday graf
yarim Gamilton grafi deb ataladi.
Gamilton graflari boʻyicha zarur va yetarlilik teoremalari hali topilmagan, faqat bir tomonlama teoremalar mavjud.
1. Dirak teoremasi
Uchlari soni uchtadan kam boʻlmagan
grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam boʻlmasa, bu graf Gamilton graft boʻladi.
2. Ore teoremasi
Agar uchlari soni m ga (m >2) teng boʻlgan grafdagi qoʻshni boʻlmagan ixtiyoriy uchlar darajalari yigʻindisi
m dan kam boʻImasa, u holda bu graf
Gamilton grafi boʻladi.
Koʻrib turganingizdek bu teoremalar bir taraflama, teskarisi oʻrinli emas. Demak Gamilton graflari uchun ikki taraflama teorema oʻylab topishni ham hali yechimi topilmagan qiyin masalalar qatoriga qoʻshishimiz mumkin.
Izlanuvchilar uchun ilmiy ish qilishda shu soha ham ancha qiziqarli hisoblanadi.
Kamchiliklar uchun uzur© Shukurullo Turdiboyev@Turdiboevs
