Navzu: Bog`langan graflar. Marshrut, zanjir, sikllar. Eyler va Gamilton graflari Bog`langan graflar. Marshrut, zanjir, sikllar

zanjir

 

deyiladi. Boshqacha ta’riflansa, takroriy qirralarga ega bo`lmagan marshrut 

zanjir

 

deyiladi.  Yopiq zanjir esa 

sikl 

deyiladi.  

 

 

Eyler grafi. Gamilton grafi. Sodda zanjirlarni aniqlash 

 

Yo'naltirilmagan  G  graf  berilgan  bo`lsin.  Eyler  sikli  shunday  siklki,  unda 

grafning  ma'lum bir  uchidan chiqib, barcha qirralardan faqat bir marta o'tib, yana 

shu uchga qaytib kelishi kerak.  

  

Grafda Eyler sikli mavjud bo`lishi uchun:  

a) Graf bog`langan bo`lishi; 

b) Grafning barcha uchlarining darajalari juft bo`lishi kerak;   

          Grafda Eyler zanjiri mavjud bo`lishi uchun:  

a) Graf boglangan bo`lishi; 

b) Grafning 2 ta uchi darajalari toq bo`lib, qolgan barcha uchlarining darajalari juft  

bo`lishi kerak.   

Grafning barcha qirralaridan bir martadan o`tgan zanjir 

eyler zanjiri

 

deyiladi 

---

           Agar  G    yo`naltirilmagan  grafda  Eyler  sikli  mavjud  bo`lsa, bunday  grafga 

eyler grafi deyiladi. Boshqacha aytganda,grafning barcha uchlaridan o`tuvchi karrali 

qirralar va ilmoqlarga ega bo`lmagan graf 

eyler grafi

 deyiladi. 

   Agar bog`liqli grafda barcha uchlar juft bo`lsa, bu graf eyler sikliga ega bo`ladi. 

      Teskari tasdiq ham  o`rinli:  agar  graf  eyler  sikliga  ega bo`lsa, uning barcha 

uchlari darajalari juft bo`ladi. 

 

 

Misol.                                         

          

 

 

                  

 

36- rasm 

Agar grafda oddiy cikl mavjud bo`lib, bu ciklda grafning barcha uchlari qatnashsa, 

bunday  sikl  Gamilton  sikli deyiladi. Oddiy  zanjir  Gamilton  zanjiri   deyiladi, agar 

bunday grafda uchlarning hammasi ishtirok etsa. Boshqacha aytganda,  agar zanjir 

grafning  barcha  uchlaridan  bir  martadan  o`tsa,  bunday  zanjirga