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

(a, b) jufti uchun masofa (uni fl(a,b) bilan 
belgilaymiz) mos qo‘yilgan hamda o‘zaro 

---

bog‘lanmagan shaharlar orasidagi masofa 
cheksiz katta deb hisoblaymiz. Kommivoyajer 
uchun shunday Gamilton sikli to-pish kerakki, 5-shakl 
ifodaning qiymati minimal bo‘lsin, bu yerda at - tarmoqdagi z - shahar ( i = 0,n ). 
Boshqacha aytganda, 
kommivoyajeming biror shahardan chiqib va qolgan barcha shaharlardan 
faqat bir martadan o‘tib, yana dastlabki shaharga qaytishi imkonini 
beruvchi eng kichik umumiy uzunlikka ega bolgan yo‘lni topish kerak. 
Muammoli masala va topshiriqlar 
1. Yarim Eyler grafi bo‘lib, Eyler grafi bo‘la olmaydigan grafga 
misol keltiring. Sababini tushuntiring. 
2. 6- shaklda tasvirlangan uchta grafni (bu graflarda qirralarga 
kesmalar, kesmalaming kesishish nuqtalariga esa uchlar mos qo‘yilgan deb 
bisoblanadi) tekshirib, ulaming Eyler grafi bo‘lish yoki bo‘lmasligini 
aniqlang. Eyler grafi bo‘lganlarining har biridagi Eyler sikllaridan bir 
nechasini toping. Eyler grafi bo‘lmaganlarining yarim Eyler grafi bo‘lishi 
yoki bo‘lmasligini tekshiring. 
3. 3-, tasvirlangan graflar orasida 
qalamni qog‘ozdan коЧаппа- 
sdan har bir kesmani faqat bir 
6- shakl marta chizib (kesmalaming 
uchlari bundan mustasno) chiqish 
mumkin bo‘lganlarini aniqlang. 
4. Lotin alifbosi bosma harflaming har biriga graf sifatida qarab 
(masalan A harfiga mos graf 7- shaklda tasvirlangan), ular orasidan Eyler 
grafi bo‘la olmaydiganlarini aniqlang. 
К 
1 Kommivoyajer - sayohatchi reklamachi, gumashta. 
228 
www.ziyouz.com kutubxonasi 
5. K n grafning Eyler grafi bo‘lishi shartlarini toping. 
6. Berilgan n ta elementli to‘plam uchun tuzilgan barcha n\ ta o‘rin 
almashtirishlarning har biriga grafning uchi mos qo‘yilgan bo‘lsin. Agar 
biror o‘rin almashtirishdan undagi ikkita elementning o‘rinlarini 
almashtirib boshqa o‘rin almashtirishni hosil qilish mumkin bo‘lsa, u holda 
bu harakatga grafning qirrasini mos qo‘yamiz. Shunday usul bilan tuzilgan 
graf Gamilton grafi bo‘lishini isbotlang. 
7. Kn grafning Gamilton grafi bo‘lishi shartlarini aniqlang. 
8. 8- shaklda tasvirlangan to‘rtta grafning har biri Eyler grafi bo‘lishi 
yoki bo‘lmasligini tekshiring. 
9. 8- shaklda tasvirlangan to‘rtta grafning har biri Gamilton grafi Abo‘lishi yoki 
bo‘lmasligini tekshiring. 
Ш О И Ш 
7- shakl 8.