Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib

13.Daraxtlar 

   Agar  G  grafning  u  qirrasi  kamida  bitta  siklga  tegishli  bo`lsa,  u  siklik  qirra,  aks 

holda atsiklik qirra deb ataladi. 

 G graf uchun  

       

G

k

G

n

G

m

G









 

Ifoda  uning  siklomatik  soni  hisoblanadi,  bu  yerda  m(G)  G  grafning  qirralar  soni.  

n(G)- uchlari soni, k(G)- komponental soni.  

Osongina ko`rish mumkinki,  

                 K(G), agar u siklik qirra bo`lsa, 

 K(G\u)=  

                   K(G)+1, u  atsiklik qirra bo`lsa; 

 

                   



(G)-1, agar u siklik qirra bo`lsa, 



(G\u)= 

                    K(G), agar u atsiklik qirra bo`lsa. 

      O`z-o`zidan  ravshanki,  n(G\u)=n(G),  m(G\u)= 



  (G)-1, 



(G)



0  va  faqat 

sikllari bo`lmagan graf uchun 



(G)=0. 

Ta’rif.  Barcha qirralari atsiklik bo`lgan bog`liq graf daraхt deb ataladi.  

---

31

 

 

Bir necha daraxtlardan tashkil topgan bog`liqmas graf o`rmon deyiladi. 

Daraхtning  istalgan  2  uchi  yagona  zanjir  bilan  bog`langandir.  Daraхtning 

istalgan х

0

 uchini tanlab olib, uni ildiz yoki nolinchi pog`onali uch deb ataymiz. х

0

 

ga qo`shni bo`lgan barcha uchlarni birinchi pog`ona uchlari deymiz va hokazo.   

 

 

 

 

 

 

 

 

13.1- rasm 

Daraхtning  bunday  tasvirlanishidan  kelib  chiqadiki  u  chetki,  faqat  bitta  qirraga 

insident bo`lgan uchlarga ega.  

         Bog`liq  G  grafning  ketma-ket  barcha  siklik  qirralarni  olib  tashlaymiz.  

Natijada hamma qirralar atsiklik bo`lgan bo`g`liq N grafni –daraхtni hosil qilamiz. Bu 

daraхt  G  grafning  asosi  deyiladi.  N  asosga  nisbatan  G  N  bo`lakning  barcha  qirralari 

vatarlar deb ataladi.  

Chekli  bog`liq    G  graf  daraхt  bo`lishi uchun    uning  qirralari soni  uchlari  sonidan 

bittaga kam bo`lishi zarur va yetarli.  

Teorema (Keli) Uchlar soni tartiblangan n ta bo`lgan daraхtlar soni   n

n-2

  teng. (n 

ta elemenlardan n-2 tadan tuzilgan barcha takrorish o`rinlashtirishlar soni). 

Agar  G  graf  daraхt  bo`lsa,  u  holda  uning  qirralari  soni  m  va  uchlari  soni  n    

т = п – 1 munosabat bilan bog`langan. 

Quyidagi 4 ta shart teng kuchli: 



  G graf daraxt hisoblanadi; 



  Grafning  qirralari  soni  m  va  uchlari  soni    n        т = п – 1  munosabat  bilan 

bog`langan; 

 

---

32

 

 



  Grafning ixtiyoriy ikki uchi oddiy yo`l bilan bog`langan bo`lishi mumkin va 

bu yo`l yagonadir. 



 

G graf bog`langan va konturlarga ega emas.