Sikl. Eyler zanjiri. Eyler sikli. Eyler graft. Yarim Eyler graft

= m + 2k sondan kichik emas, ya’ni m ------V к2 2- shakl m + k > m + 2k. Oxirgi 
tengsizlik faqat к = 0 bo‘lgandagina to‘g‘ridir.
Bu esa к > 0 shartiga ziddir. ■ Dirak teoremasi shartlari berilgan grafning 
Gamilton graft bo‘lishi uchun yetarli, lekin ular zaruriy emas. Bu tasdiq to‘g‘ri 
ekanligini 2-shakida tasvirlangan graf misolida ko‘ramiz. Bu grafda sakkizta uch 
bo‘lib (m = 8 > 3 ), har bir v ( v = 1, 8) uchning darajasi 3ga teng: p(v) = 3. 
Dirak teoremasidagi p ( v ) >— 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. Ore1 quyidagi teoremani isbotladi. 
\ X X I \ 3 - t e o r em a ( O r e ) . Agar uchlari soni I I \ / / m ga (m > 2 ) teng 
bo‘Igan grafdagi qo ‘shni y r 4 \ / / bo'lmagan ixtiyoriy uchlar darajalari 
* * yig'indisi m dan kam bo ‘Imasa, и holda bu 
graf Gamilton 3- shakl graft bo ‘ladi. 

---

2- m i s o l . 3- shaklda tasvirlangan graflar Gamilton graflariga misol 
bo‘la oladi. 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. ■ 
3- m i s o l . Shaxmat o ‘yinidagi otning yurishi haqidagi Eyler 
masalasi deb ataluvchi quyidagi masalani qaraymiz. Shaxmat taxtasidagi 
istalgan katakda turgan shaxmat oti uchun yurishlarning shunday ketmaketligini 
tuzingki, u barcha kataklardan faqat bir martadan o ‘tsin va yurish 
boshlangan katakka qaytib kelsin. Bu masalani hal qilish maqsadida 
tuzilgan graf (shaxmat taxtasidagi kataklarga grafning uchlari, otning 
yurishlariga esa uning qirralari mos qo‘yilishi nazarda tutilmoqda) ham 
Gamilton grafiga misol bo‘la oladi. Bu masalaning yechimlaridan biri 4- 
shaklda keltirilgan. ■ 
4- m i s o l . 5- shaklda tasvirlangan grafda Gamilton zanjiri mavjud 
emas. ■ 
Berilgan grafda Gamilton 
zanjirining mavjudligi shartlami 
o‘rganish bo‘yicha 
izlanishlar davom etayotganligi 
va bu sohadagi ishlar 
bugungi kunda ham dolzarbligini 
yo‘qotmaganligi 
yuqorida qayd etilgan edi. 
Grafdagi uchlar soni m ning 
qiymatiga nisbatan ko‘phad 
bilan chegaralangan sondagi 
qadam ishlatib istalgan 
grafda Gamilton zanjiri mavjudligini 
tekshiradigan algoritm 
hozirgacha topilmagan. 
Shuning uchun ham Gamilton 
zanjirini topish masalasi graflar nazariyasida markaziy 
masalalardan biri bo'lib qolmoqda, Albatta, grafdagi m ta uchlarning m\ta 
turli ketma-ketliklarini (aniqrog‘i, takrorlanmaydigan o‘rin almashtirishlarini) 
tuzib grafda Hamilton zanjiri mavjudligi masalasini hal qilish 
mumkin. Shunday boMishiga qaramasdan, barcha m!ta o'rin almashtirishlarini 
bajarmasdan qadamlar sonini jiddiy qisqartiradigan umumiy 
algoritm bor. 
4- shakl 
Grafda Gamilton zanjirini topish masalasi quyidagi kommivoyajer' 
masalasi deb ataluvchi masalada oshkora namoyon bo'ladi. Bir-birlari 
bilan yo‘llar (graf qirralari) vositasida bog‘langan shaharlar (graf uchlari) 
tarmog‘i berilgan bo‘lib, shaharlarning har bir