15-mavzu. O’rmon. Daraxtlarning xossalari. Ostov daraxti

iteratsiya.

R  {1, 2, 3, 5} ,
R  {4, 6}
bo‘lgani uchun

(R, R )  {(1, 4), (3, 4), (3, 6), (5, 6)} va
h₁₄  13 ,
h₃₄  13 ,
h₃₆  17 ,
h₅₆  18
hamda

min{ h₁₄ , h₃₄ , h₃₆ , h₅₆}  h₁₄  h₃₄  13
bo‘ladi. Demak,
(1, 4)
^va (3, 4)
yoylarni ajratamiz

hamda 4 belgili uchga
₄ 13
qiymatni mos qo‘yamiz. Natijada
R  {1, 2, 3, 5, 4} ^,

R  {6} to‘plamlarga ega bo‘lamiz.

_i  c_ij   _j
munosabatning to‘g‘riligi
(1, 3) ,
(1, 4) ^,
(2, 3) ,
(3, 5) ,
(5, 3)
va (3, 4)

yoylar uchun tekshirilib ko‘rilganda, uning barcha yoylar uchun bajarilishi ma’lum

bo‘ladi.

2. 
   iteratsiya. Endi
   

(R, R )  {(3, 6), (4, 6), (5, 6)}

bo‘lgani uchun

h₃₆  17 , h₄₆  14 ,

h₅₆  18 va
min{ h₃₆, h₄₆ , h₅₆}  h₄₆  14
bo‘ladi. Bu yerda minimum
(4, 6)
yoyda

^{erishilgani uchun uni ajratib, orgrafning oxirgi} 6 ^{belgili uchiga} mos qo‘yamiz.
₆  14
qiymatni

Oxirgi qadam. Berilgan orgrafda 1 belgili uchdan 6 belgili uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topish maqsadida, algoritmga asosan, grafning oxirgi 6 ^{belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak.} 6 ^{belgili uchga kiruvchi uchta}

yoydan faqat bittasi ( (4, 6)
yoy) ajratilgan bo‘lgani uchun
(4, 6)
yoy yo‘nalishiga

^{qarama-qarshi yo‘nalishda harakat qilib,} 6 ^{belgili uchdan 4 belgili uchga kelamiz.
4} belgili uchga kiruvchi ikkala ( (1, 4) va (3, 4) ) yoylar ham ajratilgan bo‘lgani uchun
biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yo‘l yagona emas.

Agar harakatni
(1, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak, u

holda ⁴ belgili uchdan ¹ belgili uchga kelib, eng qisqa uzunlikka ega yo‘llardan biri

bo‘lgan
₁  (1, 4, 6)
marshrutni topamiz.

Agarda harakatni
(3, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak,

u holda ⁴ belgili uchdan 3 belgili uchga kelamiz. 3 belgili uchga kiruvchi ikkita
yoydan faqat bittasi ( (5, 3) yoy) ajratilgan bo‘lgani uchun 3 belgili uchdan 5 belgili
uchga kelamiz. Shu usulda davom etsak, oldin ² belgili, keyin esa ¹ belgili uchga

₂  (1, 2, 5, 3, 4, 6)
marshrutni aniqlaymiz.

Shunday qilib, 2- shaklda tasvirlangan grafda eng qisqa uzunlikka ega
₁ ^va

₂ yo‘llar borligini aniqladik. Bu yo‘llarning har biri minimal ₆  14
uzunlikka ega.

Muammoli topshiriq va masalalar

1. 
   Bir-biriga izomorf bo‘lmagan
   
   1. 
      oltita, b) yettita, d) sakkizta, e) to‘qqizta uchga ega barcha daraxtlarni geometrik ifodalang.
      
2. 
   1- shaklda tasvirlangan o‘rmondagi daraxtlarning har biri uchun markaz(lar) bo‘luvchi uchlarni toping.
   
3. 
   Keli teoremasining isbotini o‘rganing (masalan, [10] kitobga qarang).
   
4. 
   Uchlari uchta va to‘rtta bo‘lgan barcha belgilangan daraxtlarni geometrik ifodalang.
   
5. 
   Petersen grafining sinch daraxtlaridan birini aniqlang.
   

^{6. K}4,5
grafning sinch daraxtlaridan bir nechasini toping.

7. 
   12ta uchi, 10ta qirrasi va 3ta bog‘lamli komponentasi bo‘lgan, sirtmoqsiz, karrali qirralari bo‘lmagan grafning sinch o‘rmonini hosil qilish uchun uning nechta qirrasini olib tashlash kerakligini aniqlang.
   
8. 
   

    1 	1	1	0 
   1	0	0	0
    0	0	0	1 
    0	0	1	0

   
   
   
   Insidentlik matrisalari quyida berilgan graflarning siklomatik sonlarini toping:
   

1	0	0	0	0	0 
1	1	1	0	0	0
0	1	0	1	0	0 
0	0	1	1	1	1
0	0	0	0	1	0 
0	0	0	0	0	1 

 ¹


_ 0

1


1. 
   
   

 ⁰

0



0



, b) ^





.

0

1





0

0
1 0 _
0 0 _

7. 
   Uchlari qo‘shniligi matrisalari quyida berilgan graflarning sinch daraxtlaridan bir nechasini toping:
   

 ^{0 1}

^{1 1}

 ^{0 1 1 1 0}
 
1 0 0 1 1

1. 
   ^{ 1}
   

0 0 1_{ , b)} ^{ } _.

1

1



0




^ 1 0

1
_ 1
0 1^

0

1


 _{0 1} 


 ^{1 1 1 0 1}

0

0

1


_ 1 1 ^