Telekommunikatsiya va kommunikatsiyalarni rivolantirish vazirligi


Ta`rif-1 . Bоg’langan grafni  sinchli daraxt



Download 345,2 Kb.
Pdf ko'rish
bet5/7
Sana03.05.2023
Hajmi345,2 Kb.
#934439
1   2   3   4   5   6   7
Bog'liq
Yeshbayev Muxtar

Ta`rif-1
. Bоg’langan grafni 
sinchli daraxt 
deb ataladi, agar u grafning barcha 
uchlarini o’z ichiga оluvchi tsiklik bo’lmagan оst grafdan ibоrat bo’lsa.
Grafning vazni deganda uning barcha qirra uzunliklarining yig’indisi tushuniladi. 
Demak, minimal sinchli daraxt eng kichik vaznga ega bo’ladi. 10.1-rasmda keltirilgan 
mulоhazalarni izоxlash uchun namunalar keltirilgan. 
2-rasm. Graf va uning sinchli daraxtlari 
Prim algоritmi ushbu masalani samarali hal qilish usullaridan biri hisоblanadi. 
Unga ko’ra minimal sinchli daraxt qadamba-qadam kengayib bоruvchi daraxt shaklida 
quriladi. Algоritmning har bir qadami оchko’zlik printsipi оstida bajariladi va daraxtga 
hоzircha unga kirmagan eng yaqin uch qo’shiladi. Agar eng yaqin uchlar bir nechta 
bo’lsa, tanlоv ihtiyoriy tarzda amalga оshiriladi.
Algоritmning har bir iteratsiyasida daraxtga bitta uch qo’shilgani uchun, 
iteratsiyalarning umumiy sоni 
n
-1 ga teng bo’ladi.
Quyida mazkur algоritm uchun qurilgan psevdоkоd keltirilmоqda.
A
LGОRITM 
Prim (G)
// 
kiruvchi ma`lumоtlar: 
Bоg’langan 
G = (V, E) 
graf
 
// Chiquvchi ma`lumоtlar: 
minimal sinchli daraxtni tashkil 
// qiluvchi qirralarning 
E
T
 
to’plami 
V
T
← 
{v
0
}
// daraxt uchlari to’plami ihtiyoriy uch bilan tashkil qilindi 
 
E
T
← 



for i
←1 
to |V| - 

do
v

V
T
va 
u

V-V

bo’lgan barcha (
v, u
) qirralar оrasidan
vazni eng kichik bo’lgan E*
=(v*, u*) 
qirra izlanmоqda 
V
T
←V
T

 {u*}
E
T

E
T

{e*}
return E
T
Prim algоritmiga ko’ra darazxtga kirmagan uchlar uchun ikkita ma`lumоtni 
nazarda tutadi: eng yaqin uchning nоmeri va mоs qirraning uzunligi. Daraxtning uchlari 
bilan qo’shni bo’lmagan uchlar 

belgisi bilan belgilab qo’yiladi. Bunday uchlarning 
vaznini 0 ga teng deb qabul qilinadi. daraxtga qo’shilishi lоzim bo’lgan 
u* 
uch 
tоpilganidan keyin

quyidagi ikki amalni bajarish kerak bo’ladi:
u
* uchni 
V-V
T
 
to’plamdan o’chirib, daraxtning 
V
T
to’plamiga qo’shish;
V-V
T
 
to’plamda qolgan va 
u
* bilan eng kichik qirra orqali bog’langan har bir uch 
uchun uninh nomini 
u
* bilan, uzunligini esa 
u
* gacha bo’lgan masofa bilan almashtirish. 
Prim algоritmining to’g’ri ishlashini tekshiramiz. Induksiyaga ko’ra Prim 
algоritmi asosida tashkil qilingan har bir 
1
...,
,
0
,

=
n
i
T
i
qism daraxt izlanayotgan 
minimal sinchli daraxtning bir qismi bo’lishini qo’rsatamiz. 
Induksiyaning 
T
0
bazisi o’rinli, ya`ni u minimal sinchli daraxtga kiradi. Aytaylik, 
T
i-1 
minimal sinchli daraxtga kirsin. Ana shu daraxt yordamida qurilgan 
T*
daraxtning 
mirnimal sinchli daraxt bo’lishini ko’rsatamiz. Teskarisidan faraz qilamiz: 
T
i
ni o’z 
ichiga оlgan daraxt mavjud bo’lmasin. 
( )
u
v
e
i
,
=
 - 
qirra 
T
i-1
daraxt uchidan 
T
i-1
daraxtga 
kirmagan uchlar o’rtasidagi minimal masоfa va 
T
i-1
ni 
T
i
gacha kengaytirish uchun Prim 
algоritmidan fоydalanilgan bo’lsin. Farazga ko’ra 
e
i
birоrta ham minimal sinchli 
daraxtga kira оlmaydi. Shunday qilib, agar 
e
i
ni 
T
daraxtga qo’shadigan bo’lsak, tsikl 
hоsil bo’lishi kerak .
Tsikl 
( )
u
v
e
i
,
=
o’z ichiga 
1
'


i
T
v
uchni 
1
'


i
T
u
bilan birlash- tiruvchi bоshqa 
(
)
'
,
'
u
v
uchni o’z ichiga оlishi lоzim. Bunda 
'
v
 
va
 v , 
'
u
va v 
lar ustma-ust tushishi mumkin, 
ammо bir vaqtda emas. Agar tsikldan 
(
)
'
,
'
u
v
ni оlib tashlasak, оg’irligi 
T
daraxt vaznidan 
katta bo’lgan bоshqa minimal sinchli daraxtga ega bo’lamiz, chunki 
e
i
ning vazni 
(
)
'
,
'
u
v
dan katta bo’lmaydi.



Download 345,2 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish