Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib

 

 

 

 

 

 

 

---

3

 

 

2.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.1 -rasm 

 

Yuqorida keltirilgan grafda 1 uch 2 ta karra ilmoqqa, 2 uch 1 ta ilmoqqa ega, 

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

Ilmoqlarsiz psevdograf multigraf deyiladi. 

Multigrafga misol 2.2-rasmda keltirilgan. 

 

 

 

                                           

 

 

 

                                                       2.2-rasm 

---

4

 

 

Agar  grafning  uchlari  va  qirralari  to`plamida  refleksivlik  va  simmetriklik 

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

tolerant graf deyiladi. 

 

 

 

             

2.3- rasm 

 Tolerant graf                                   Oriyentirlanmagan graf 

 

       

 

 

2.3- rasm 

 Tolerant graf                                        Oriyentirlanmagan graf