gamilton grafi
deyiladi.
37-
rasm
38-
rasm
Misol 38- rasmda tasvirlangan graflarning har biri oltita uch va yettita qirralarga
ega bo`lib, ular izomorf emas.
Hammasi bo`lib beshta qavariq muntazam ko‘pyoqli mavjudligi qadimdan
ma’lum (Evklid isbotlagan): tetraedr, kub, oktaedr, dodekaedr va ikosaedr. Bu
ko‘pyoqlilarning umumiy nomi ham bor – Platon jismlari. Barcha Platon
jismlariga mos graflar tekislikda geometrik ifodalanadi. Masalan, tetraedr va
kubga mos graflarning geometrik ifodalanishi 39- rasmda tasvirlangan.
Eyler va Gamilton graflari
Graf, uch, qirra, sikl, Eyler zanjiri, Eyler sikli, Eyler graft, yarim Eyler graft,
oriyentirlangan Eyler yo 4i, oriyentirlangan Eyler graft, Flyori algoritmi,
Gamilton zanjiri, Gamilton sikli, Gamilton graft, yarim Gamilton graft,
kommivoyajer masalasi.
Eyler graflari.
Graflar nazariyasining shakllanishi Kyonig-sberg ko'priklari haqidagi masala
bilan bog'liq ekanligi yaxshi malum. L. Eyler 1736-yilda bu masalaning yechimga
ega emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan
quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda, bog'lamli grafda
barcha qirralardan faqat bir marta o'tadigan sikl mavjud bo'ladi?
Grafning har bir qirrasidan faqat bir marta o'tadigan zanjir
Eyler zanjiri,
deb
ataladi. Yopiq Eyler zanjiriga (ya'ni
Eyler sik~ liga)
ega graf
Eyler graft,
deb
ataladi. Agar grafda yopiq bo'lmagan Eyler zanjiri topilsa, u holda bunday graf
yarim Eyler graft,
deb ataladi.
1-teorema. Bog'lamli graf Eyler graft bo'lishi uchun undagi barcha uchlarning
darajalari juft bo 'lishi zarur va yetarlidir.
Isboti.
Zarurligi.
G
Eyler grafida C—Eyler sikli bo'lsin. U holda Сsikl bo'ylab
harakatlanganda grafning har bir uchidan o'tish uchun bir juft qirradan
foydalaniladi — bu qirralardan bin uchga kirish uchun, ikkinchisi esa uchdan
chiqish uchun zarur bo'ladi. Bu yerda har bir uch darajasining juftligi
С
sikldagi
har bir qirraning bir marta uchrashi mumkinligidan kelib chiqadi.
Yetarliligi.
Endi
G
grafning har bir uchi darajasi juft bo'lsin, deb faraz
qilamiz.
G
graf bog'lamli bo'lgani uchun undagi har bir uchning darajasi ikkidan
kichik emas.Ma'lumki, agar grafda har bir uchning darajasi ikkidan kichik
bo'lmasa, u holda bunday graf tarkibida sikl mavjud (ushbu bobning 4-paragrafidagi
1-teore-maga qarang).
Demak,
G
grafning qirralaridan tashkil etilgan qandaydir C
2
sikl bor. Bu siklni
uning ixtiyoriy v, uchidan boshlab quramiz.Dastlab v, uchga insident bo'lgan
ixtiyoriy bir qirrani tanlab, bu qirra bo'ylab harakatlanamiz va uning boshqa
uchiga o'tamiz. Har safar, imkoniyati boricha, yangi qirra tanlab va bu qirradan
o'tib, uning boshqa uchiga boramiz. Shuni ta'kidlash zarurki, bunday o'tishlar
jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa
istalgancha takrorlanishi mumkin.
Har bir uchga insident qirralar soni juft bo'lgani uchun
C
x
siklni qurish jarayoni
faqat
v
x
uchga borgandagina tugaydi. Bu yerda ikki hoi bo'lishi mumkin:
1)
C
x
sikl
G
grafning barcha qirralaridan o'tadi yoki
2)
C
x
sikl
G
grafnir.p barcha qirralaridan o'tmaydi.
, Birinchi holda teorema isbotlandi deyish mumkin. Ikkinchi holda
G
grafdan
C
x
siklga tegishli barcha qirralarni olib tashlaymiz vanatijada hosil bo'lgan grafni
C
x
deb belgilaymiz. Bu yerda yakkalanib qolgan uchlarni olib tashlash yoki olib
tashlamaslik muhim emas.Agar yakkalanib qolgan uchlar olib tashlanmasa, natijada
bog'lamli bo'lmagan
G
x
grafni hosil qilishimiz ham mumkin.Grafdan qirralarni
bunday olib tashlash amali, tabiiyki, grafning qirralari sonini kamaytiradi, lekin
grafdagi uchlarning darajalari juftligi xossasini o'zgartirmaydi.
G grafning bog'lamliligiga ko'ra,
C
x
sikl va
G
x
graf hech bo'lmasa, bitta umumiy
uchga ega bo'lishlari kerak. Shu sababli, C, siklda
G
x
grafning qirralariga ham
insident bo'lgan qandaydir v
2
uch bor. Bu
v
uchdan boshlab faqat
G
x
grafning
qirralaridan tashkil topgan yangi
С
siklni qurish mumkin.Сsiklni qurish jarayoni
faqat v
2
uchga kelib tugashi mumkin.
Oldin qurilgan
C
x
siklni ikki qismga ajratamiz:
1)
Cj siklning Vj uchidan boshlanib v
2
uchida tugovchi qismi (bu oddiy zanjirni
C,(Vj,v
2
) bilan belgilaymiz) va
2)
Cj siklning v
2
uchidan boshlanib, v
}
uchida tugovchi qolgan qismi
(CfavJ).
Agar C
2
sikl Eyler sikli bo'lsa, teoremaning tasdig'i isbotlandi desa bo'ladi.Aks
holda yuqorida bayon etilgan jarayonni takrorlaymiz.
Berilgan
G
grafdagi qirralar soni chekli bo'lganligidan, bu jarayon chekli
jarayondir.Bu jarayonni yetarlicha takrorlagandan so'ng, albatta, u Eyler siklini
qurish bilan yakunlanadi.■
1-natija. Bog'lamli graf yarim Eyler graft bo'lishi uchun undagi ikkitadan ко'p bo
'Imagan uchning darajalari toq bo lishi zarur va yetarlidir.
Isboti
1-teoremaning isbotidan ba'zi o'zgartirishlar natijasida hosil qilinishi
mumkin.■
1-teorema asosida Kyonigsberg ko'priklari haqidagi masalaning (ushbu bobning
1-paragrafiga qarang) yechimi mayjud emas, degan xulosaga kelamiz, ya'ni
Kyonigsberg shahrining ixtiyoriy qismida joylashgan uydan chiqib, Pregel daryosi
ustiga qurilgan yetti ko'prikdan faqat bir martadan o'tgan holda yana o'sha uyga
qaytib kelish mumkin emas.
Oriyentirlangan
graflarda oriyentirlangan
Eyler
yo'lini
izlash bilan
shug'ullanish mumkin. Har bir yoydan faqat bir marta o'tadigan yo'l
|
