20-mavzu. O„rmon. Daraxtlarning xossalari. Daraxtlar haqidagi teoremalar. Rеja

1 2 3 4 5 6 7

Bog'liq
20-mavzu. O„rmon. Daraxtlarning xossalari. Daraxtlar haqidagi te-fayllar.org

Muammoli topshiriq va masalalar

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

^6.^K4,5
grafning sinch daraxtlaridan bir nechasini toping.

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.
Insidentlik matrisalari quyida berilgan graflarning siklomatik sonlarini toping:

^{1 1}



_0 1

^1 0
0 0 0
1 1 0
1 0 1

^{0 0}

0 0_

0 0^

 ^{1 1}


_1 0

^0 0

^{1 0}

0 0_

0 1^

 ^{, b)   .}

 ^{0 0}








^{0 1 1 1 1}
0 0 0 1 ^
0


0 0 0 0 ^


 ^{0 0 1 0}

_{ 0}
0





_{ 0}
0



Uchlari qo„shniligi matrisalari quyida berilgan graflarning sinch daraxtlaridan bir nechasini toping:

 ^{0 1 1 1}

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


1 _

₁

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

^1 0 0 1^




_1 1 _
1

0




 ^{1 1}






^{1 0 1}

1 1 _

Daraxtdan biror qirra olib tashlansa natijada qanday xossalarga ega bo„lgan graf hosil bo„ladi?
Daraxtning har bir qirrasi haqida nima deyish mumkin?
Daraxtdagi o„zaro ustma-ust tushmaydigan istalgan ikkita uchini nechta oddiy zanjir bilan tutahtirish mumkin?
O„rmondagi o„zaro ustma-ust tushmaydigan istalgan ikkita uch oddiy zanjir bilan tutahtirilsa natijada qanday graf hosil bo„lishi mumkin?
Daraxtning qo„shni bo„lmagan ikkita uchini qirra bilan tutashtirilsa, natijada qanday graf hosil bo„ladi?
O„rmondagi qo„shni bo„lmagan ikkita uchni qirra bilan tutashtirilsa, natijada qanday graf hosil bo„ladi?
Bittadan ko„p uchga ega bo„lgan istalgan daraxtda qancha darajasi birga teng uchlar bor?
^m^{ta uch va}k ^{ta bog„lamli komponentasi bo„lgan o„rmonda qancha qirra}bor?
Istalgan daraxtning markazi haqida nima deyish mumkin?
Grafning sinch daraxti deganda nimani tushunasiz?
Petersen grafidan bog„lamlilikni buzmasdan nechta qirrani olib tashlash mumkin?
Oktaedrga mos grafdan bog„lamlilikni buzmasdan nechta qirrani olib tashlash mumkin?
Grafning siklomatik soni qanday aniqlanadi?
Berilgan graf o„rmon bo„lishining zaruriy va yetarli sharti siklomatik son orqali qanday ifodalanadi?
Graf yagona siklga ega bo„lishining siklomatik son tushunchasi yordamida ifodalanuvchi qanday zaruriy va yetarli shartini bilasiz?

http://fayllar.org

Download 32,13 Kb.

1 2 3 4 5 6 7

Download 32,13 Kb.