Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi kengayib
Download 141.24 Kb.
|
Hozirgi kunga kelib diskret matematikaning qo`llanish sohasi ken-fayllar.org
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\u)= K(G), agar u atsiklik qirra bo`lsa. O`z-o`zidan ravshanki, n(G\u)=n(G), m(G\u)= (G)-1,
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.
0
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;
bog`langan; 32
Download 141.24 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling