Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib

 

 

 

 

 

 

 

---

28

 

 

12.Graflarni хarakterlovchi sonlar 

 Grafning bog`liqlik komponentlari deb uchlari berilgan grafdagi bog`liqlik 

munosabatlari  ekvivalentlik  sinfi  hisoblangan  berilgan  grafning  qism  graflariga 

aytiladi. 

 Grafning  siklomatik  soni  deb  bog`liqlik  komponentalariga    qirralar  sonini 

qo`shib undan uchlar sonini ayirganda 

hosil  bo`ladigan  songa  aytiladi.  Boshqacha    ta’rif  beradigan  bo`lsak,  grafning 

siklomatik soni deb,  N+p-n songa aytiladi, bu yerda N- grafning qirralari soni, n 

– grafning uchlari soni, P – bog`liqlik komponenti soni. Bog`liq graf uchun N +1-

n.  

Grafning siklomatik soni erkli sikllarning eng katta miqdoriga teng. 

Misol. 

Quyidagi chizmada tasvirlangan grafning siklomatik soni 3 ga teng. 

 

 

 

 

12.1- rasm 

 Agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita qism 

to‘plamlarga  (bo‘laklarga) ajratish  mumkin  bo‘lsaki,  grafning ixtiyoriy  qirrasi  bu 

to‘plamlarning biridan olingan qandaydir uchni ikkinchi to‘plamdan olingan biror 

uch  bilan  tutashtiradigan  bo‘lsa,  u  holda  bunday  graf  ikki  bo‘lakli  graf