Eyler va Gamilton graflari

Gamilton graflari.


Graflar nazariyasining natijalari muayyan shartlarni qanoatlantiravchi marshratlarni topish masalasiga kelti-riluvchi bir qator muammolarni hal etishda qo'llanilishi mumkin. Shunday muammolardan biri sifatida Uilyam Gamilton nomi bilan bog'Uq masalani keltiramiz. U. Gamilton dodekaedrni tekshirib, uning har bir uchidan faqat bir marta o'tadigan siklni izlab topgan va shu asosda 1859-yilda «Olam bo'ylab sayohat» nomli o'yirmi topgan.
Grafning har bir uchidan faqat bir marta o'tadigan zanjir Gamilton zanjiri, deb ataladi. Yopiq Gamilton zanjiriga (ya'ni Gamilton sikliga) ega graf Gamilton graft, deb ataladi. Agar grafda

yopiq bo'lmagan Gamilton zanjiri to-pilsa, u holda bunday graf yarim Gamilton graft, deb ataladi.
Oriyentirlangan graflarda ham graf­ning har bir uchidan faqat bir marta o'tuvchi oriyentirlangan sikllarni qarash mumkin.
Eyler va Gamilton graflari bir-birlariga o'xshash ta'riflansa-da, grafning Gamil­ton grafi ekanligini tasdiqlaydigan alomat (mezon) topish masalasi ancha murak-kab hisoblanadi. Hozirgi vaqtgacha graflar nazariyasida grafning Gamilton grafi ekanligini tasdiqlovchi shartlarni o'rganish bo'yicha izlanishlar davom etib, bu sohadagi ishlar hanuzgacha dolzarbligini yo'qotmasdan kelmoqda.
Qandaydir shartlarga bo'ysunuvchi graflarda Gamilton sikli mavjudligi haqida bir necha tasdiqlar mavjud. Qator hollarda bu tasdiqlarning isbotlari konstraktiv bo'lganligidan, Gamilton siklini tuzishga doir samarali algoritmlar ham yaratilgan.1952-yilda G. E. Dirak¹ quyidagi teoremani isbotladi.
2-teorema (Dirak). Uchlari soni uchtadan kam bo'lmagan grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam bo 'Imasa, bu graf Gamilton grafi bo 'ladi.
Isbot. Uchlari soni m >3 bo'lgan graf berilgan bo'lsin. Bu grafning istalgan v uchi uchun p(v)>— shart bajarilsa-da, u
Gamilton graf bo'lmasin, deb faraz qilamiz.
Tabiiyki, istalgan grafga yetarlicha sondagi yangi uchlarni qo'shib olib, bu uchlarning har birini grafdagi har bir uch bilan qirra orqali tutashtirsak, berilgan grafdan Gamilton grafini hosil qilish mumkin. Bu usul bilan berilgan grafdan Gamilton grafini hosil qilish uchun qo'shilayotgan zarur uchlarning minimal sonini к>0 bilan belgilaymiz.
Yuqorida bayon qilingan usulni qo'llash natijasida hosil bo'lgan grafdagi uchlardan tashkil topgan (v_vw,v₂,...,v^) ketma-ketlikbiron Gamilton sikli bo'lsin, bunda v,,v₂— berilgan grafning uchlari, w esa qo'shib olingan uchlardan biri. Tushunarliki, v₂ uch Vj uchga qo'shni emas, aks holda siklni tuzishda w uchni ishlatmasUgimiz mumkin bo'lar edi. Bu esa кsonining minimalligiga ziddir.
Agar grafdagi Vj uch v_luch bilan qo'shni, v₂ uch esa v₂
uch bilan qo'shni bo'lsa, v₂ uch siklda Vj uchdan bevosita keyingi
uch bo'la olmaydi, chunki bu holda (v₁,w,v₂,...,v₁ ,v₂,..., v_x) siklni
(v,,v_: ,...,v₂,v₂,...,Vj) siklga almashtirish mumkin. Natijada hosil bo'lgan grafning v₂ uchga qo'shni bo'lmagan uchlari soni v_xuchga qo'shni uchlari sonidan kichik emasligi, ya'ni bu son kamida

g a teng ekanligi) ravshan. Boshqa tomondan esa hosilbo'lgan grafning v₂ uchga qo'shni uchlari soni kamida

tengligi ko'rinib turibdi. Hosil bo'lgan grafning har bir uchi bir vaqtning o'zida v₂ uchga qo'shni ham, qo'shnimas ham bo'lishi mumkin emasligidan hosil bo'lgan graf uchlarining umumiy soni(m+k) ushbu 2 у^+/с 1= т+2к sondan kichik emas, ya'nim+k > m +2k. Oxirgi tengsizlik faqat k=0 bo'lgandagina to'g'ridir.
Bu esa k>0 shartiga ziddir. ■

Dirak teoremasi shartlari berilgan grafning Gamilton grafi bo'lishi uchun yetarli, lekin ular zaruriy emas. Bu tasdiq to'g'ri ekanligini 2-shaklda tasvirlangan graf misolida ko'ramiz. Bu grafda sakkizta uch bo'lib (/и=8>3), har bir v (v = l,8) uchning darajasi 3 ga teng: p (v)=3. Dirak
mteoremasidagi p(v)>y shart grafdagi
hech qaysi uch uchun bajarilmasa ham, bu grafda (1,2,3,4,5,6, 7,8,1) ko'rinishdagi Gamilton sikli bor bo'lgani uchun u Gamilton grafidir.
1960-yilda O. Ore quyidagi teoremani isbotladi.
3-teorema (Ore). Agar uchlari soni mga (m>2) teng bo'lgan grafdagi qo'shni bo'lmagan ixtiyoriy uchlar darajalari yig'ndisi m dan kam bo 'Imasa, иholda bu graf Gamilton graft bo 'ladi. Isboti o'quvchiga topshiriq sifatida beriladi.

2-misol.3-shaklda tasvirlangan graflar Gamilton graflariga misol bo'la oladilar.Bir qarashdayoq sezish mumkinki, bu graflarning har birida bir nechtadan Gamilton sikllari mavjud.Mumkin bo'lgan ba'zi Gamilton sikllari shaklda qalin chiziqlar bilan ifodalangan.