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 grafning har bir uchidan
faqat bir marta o'tuvchi oriyentirlangan sikllarni qarash
mumkin.
Eyler va Gamilton graflari bir-birlariga o'xshash ta'riflansa-
da, grafning Gamilton 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
1
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.
Isboti
2
.
Uchlari soni
m >
3 bo'lgan graf berilgan bo'lsin. Bu
m
grafning istalgan v uchi uchun p(v)>—
shart bajarilsa-da, u
Gamilton graft 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
v
w,v
2
,...,v^)
ketma-ketlikbiron Gamilton sikli bo'lsin,
bunda v,,v
2
— berilgan grafning uchlari,
w
esa qo'shib olingan uchlardan biri.
Tushunarliki, v
2
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
l
uch bilan qo'shni, v
2
uch esa v
2
uch bilan qo'shni bo'lsa, v
2
uch siklda Vj uchdan bevosita keyingi
uch bo'la olmaydi, chunki bu holda (v
1
,w,v
2
,...,v
1
,v
2
,..., v
x
) siklni
(v,,v
:
,...,v
2
,v
2
,...,Vj) siklga almashtirish mumkin. Natijada hosil bo'lgan grafning v
2
uchga qo'shni bo'lmagan uchlari soni
v
x
uchga qo'shni uchlari sonidan kichik
emasligi, ya'ni bu son kamida
ga teng ekanligi) ravshan. Boshqa tomondan esa hosilbo'lgan grafning v
2
uchga
qo'shni uchlari soni kamida
tengligi ko'rinib turibdi. Hosil bo'lgan grafning har bir uchi bir vaqtning
o'zida v
2
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'ni
m+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:
|
