narx
funksiyasi bilan berilgan
(
)
,
G
V E
=
bog‘langan graf bo‘lsin. Kruskal
algoritmida
G
graf uchun minimal narxli daraxtlar skeletini qurish
G
grafning faqat
n
ta tugunlaridan tashkil topgan va qirralari bo‘lmagan
(
)
,
T
V ø
=
grafdan
boshlanadi. Shunday qilib, har bir tugun bog‘langan (o‘zi-o‘zi bilan)
komponent
hisoblanadi. Algoritm bajarilishi vaqtida bog‘langan komponentlar naboriga ega
bo‘lamiz,
asta-sekin
birlashtirib
daraxtlar
skeletini
tashkillashtiramiz.
Asta-sekin o‘suvchi bog‘langan
komponentlarni qurishda
E
to‘plamdan qirralar
ularning narxi o‘sishi tartibida navbatma-navbat tekshiriladi. Agar navbatdagi qirra
turli komponentlardagi
ikkita tugunni birlashtirsa, u holda bu qirra
T
grafga
qo‘shiladi. Agar bu qirra bitta komponentning ikkita tugunini birlashtirsa, u tashlab
yuboriladi, chunki uning bog‘langan komponentga qo‘shilishi sikl hosil bo‘lishiga
olib keladi.
G
grafning barcha tugunlari bitta komponentga tegishli bo‘lsa,
T
minimal narxli daraxtlar skeletini qurish bu graf uchun tugaydi.
Primo algoritmi
Ushbu algoritm dastlab 1930 yilda chesh
matematigi Voysex Yarnik
tomonidan taklif etilgan. Keyin Robert Primo tomonidan 1957 yilda qayta ko’rib
chiqilgan va ulardan tashqari E. Deykstra tomonidan 1959 yilda ishlab chiqilgan.
Kruskal algoritm "ochko'z" algoritm anglatadi. o'sha mohiyati - har qadamda eng
yuqori g'alaba. Har doim emas, "ochko'z" algoritmlarni muammo uchun eng yaxshi
yechim beradi. a
nazariyasi aniq vazifalar, ularning qo'llash ular optimal yechim
berish, deb ko'rsatib, bor. Bu matroids nazariyasi hisoblanadi.
Kruskal algoritmi shu kabi muammolari bilan bog'liq.
Algoritm kirishiga
yo’naltirilmagan og’irlikka ega bo’lgan graf uzatiladi.
Boshida istalgan tugun olinadi va unga tegishli bo’lgan eng kam vaznga ega
insident yoy topiladi. Topilgan yoy va unga tegishli tugunlar daraxtni shakllantira
boshlaydi.
Keyin bir uchi bilan daraxtga tegishli bo’lgan tugunlariga tutashgan va ikkinchi
uchi esa tutashmagan boshqa yoylar xam tekshiriladi. Ulardan og’irligi kami
tanlanadi.
5
Xar bir qadamdagi yoy daraxtga qo’shilib boraveradi. Daraxtning balandligi
xam 1 taga oshib boraveradi. Grafning barcha tugunlari ko’rib chiqilmaguncha
algoritm davom etaveradi.
Algoritm natijasi bo’lib minimal narxli daraxt skeleti xisoblanadi.
E’tibor qaratish lozimki, minimal narxli daraxtlarni
hosil qilishda xalqa paydo
bo’lishiga yo’l qo’ymaslik kerak.
Amaliy topshiriqlari va ish davomida ishlab chiqiladigan dasturning to‘liq
namunasi.
