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.