5- §. Eyler va Gamilton1 graflari

Muammoli topshiriq va masalalar

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, kesmalarning kesishish nuqtalariga esa uchlar mos qo‘yilgan deb hisoblanadi) tekshirib, ularning 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-, 5- va 6- shaklda tasvirlangan graflar orasida qalamni qog‘ozdan ko‘tarmasdan har bir kesmani faqat bir marta chizib (kesmalarning uchlari bundan mustasno) chiqish mumkin bo‘lganlarini aniqlang.
   
4. 
   Lotin alifbosi bosma harflarning har biriga graf sifatida qarab (masalan A harfiga mos graf 7- shaklda tasvirlangan), ular orasidan Eyler grafi bo‘la olmaydiganlarini aniqlang.
   
5. 
   grafning Eyler grafi bo‘lishi sartlarini toping.
   
6. 
   Berilgan ta elementli to‘plam uchun tuzilgan barcha 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. 
   grafning Gamilton grafi bo‘lishi sartlarini 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 bo‘lishi yoki bo‘lmasligini tekshiring.
   
10. 
    D
    irak teoremasini qo‘llab grafning Gamilton grafi bo‘lishini isbotlang.
    
11. 
    Ore teoremasining isbotini o‘rganing (masalan, [9] kitobga qarang).