4 5 bb 3 c a 1
2
10 -shakl Shu usulda davom etish mumkin bo’lgan eyler sikllaridan biri quyidagi siklni
hosil qilamiz. { (2,3), (3,5), (5,1), (1,3), (3,4) , (4,5), (5,2) } (10-shakl) Eyler grafi bo’laadi. 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
deyiladi.
Agar grafda yopiq bo’lmagan Gamilton zanjiri topilsa, u holda bunday graf
yarim Gamilton grafi deb ataladi. Gamilton siklini tuzishga doir samarali
algoritmlar ham yaratilgan. 1952 yilda G.E.Dirak quyidagi teoremani isbotladi.
Teorema. (Dirak). Uchlari soni uchtadan kam bo’lmagan grafdagi istalgan
uchning darajasi uchlar sonining yarmidan kam bo’lmasa, bu graf Gamilton grafi
bo’ladi.
Teo’rema (Ore). Agar uchlari soni m ga (m>2) teng bo’lgan grafdagi qo’shni
bo’lmagan ixtiyoriy uchlar darajalari yig’indisi m dan kam bo’lmasa, bu graf
Gamilton grafi bo’ladi.
Misol. 1 Shaxmat oyinidagi otning yurishi haqidagi Eyler masalasi deb
ataluvchi quyidagi masala Gamilton grafiga misol bo’ladi. Shaxmat taxtasining
istalgan katagida turgan shaxmat oti uchun yurushlarning shunday ketma-ketligini
tuzingki, u barcha kataklardan faqat bir martadan o’tsin va yurish boshlangan
b
d
e
k
l
1-rasm
katakka qaytib kelsin. Bunda shaxmat kataklari grafning uchlari otning yurish
yo’liga esa grafning qirralari mos qo’yilgan.
11-shakl Bu masalaning yechimlaridan biri 11- shaklda keltirilgan.
