Zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini

Psevdograf. Multigraf 

 

 Shunday  graflar  mavjudki,  ularning  uchlari  bir  nechta  qirralar  bilan 

bog`langan bo`ladi. Bunday qirralar karrali qirralar deyiladi. Biror uchini o`zi bilan 

bog`laydigan qirraga ilmoq (tugun) deyiladi. 

Agar  uchdan  hech  qanday  qirra  chiqmasa,  bunday  uch  yakkalangan  uch 

deyiladi  yoki  hech  qanday  qirra  (yoy)  bilan  bog‘lanmagan  uch  yakkalangan  uch 

deb ataladi. 

        Faqat  yakkalangan uchlardan tashkil topgan graf nolgraf  yoki bo‘sh graf deb 

ataladi yoki bitta ham qirrasi bo`lmagan graf nol deyiladi.  

Uchlari  soni 

m

ga  teng  bo‘lgan  bo‘sh  grafni 

m

O

  yoki 

m

N

  kabi  belgilash  qabul 

qilingan. 

 

        Ham ilmoq, ham karrali qirraga ega bo`lgan grafga psevdograf deyiladi 

 (2-rasm) 

 

 

 

 

 

 

                                                        2-rasm 

 

Yuqorida keltirilgan grafda 1 uch 2 ta qirrali ilmoqqa, 2 uch 1 ta ilmoqqa 

ega, 2 va 3 uchlar 2 ta karrali qirralar bilan bog’langan. 

Ilmoqlarsiz psevdograf multigraf deyiladi. 

Multigrafga misol 3-rasmda keltirilgan. 

 

 

 

---

3-rasm 

Agar  grafning  uchlari  va  qirralari  to`plamida  refleksivlik  va  simmetriklik 

хossalarini  qanoatlantiruvchi  binar  munosabat    mavjud  bo`lsa,  bunday  graf  

tolerant graf deyiladi. 

 

 

 

             

4- rasm 

 Tolerant graf                                   Oriyentirlanmagan graf 

 

       

 

 

5- rasm 

 Tolerant graf                                        Oriyentirlanmagan graf