3.
Xesh funksiyalarning yana qanday turlarini bilasiz
4.
Kalit hosil qiluvchi xesh funksiyalarni keltiring
15-§. Graflarda eng kichik uzunlikdagi daraxtlarni qurish
algoritmlari
Eng kichik uzunlikdagi daraxt
– berilgan grafning eng kam
darajaga ega boʻlgan daraxti, bu yerda daraxtning darajasi uning qirralari
daajalari yigʻindisi sifatida tushuniladi.
Misol.
Minimal uzunlikdagi daraxtni topish muammosi ko'pincha
xuddi shunday sharoitda uchraydi: masalan, har qanday shahardan
boshqasiga (to'gʻridan-to'gʻri yoki boshqa shaharlar orqali) o'tish uchun
n ta
shaharlarni yo'llar bilan bogʻlash kerak. Berilgan juft shaharlar
o'rtasida yo'llar qurishga ruxsat beriladi va har bir bunday yo'lni qurish
qiymati ma'lum. Qurilishning umumiy narxini minimallashtirish uchun
qaysi yo'llarni qurish kerakligini hal qilish talab qilinadi.
Ushbu
muammoni
grafika
nazariyasi
nuqtai
nazaridan
shakllantirish mumkin. Bu yerda berilgan grafnin uchlari shaharlarni,
qirralari esa to'gʻri yo'l qurilishi mumkin bo'lgan va qirralarning
ogʻirliklari teng bo'lgan shaharlarni ifodalaydigan minimal daraxtini
topish muammosidir.
Minimal uzunlikdagi daraxtni topish uchun bir nechta algoritmlar
mavjud. Eng mashhurlari quyida keltirilgan:
1)
Prima algoritmi;
2)
Kruskal algoritmi;
175
3)
Boruvka algoritmi,
4)
Orqadan o'chirish algoritmi
Quyida ushbu algoritmlarni koʻrib chiqamiz.
59-rasm. Eng kichik uzunlikka ega boʻlgan daraxt
15.1. Kruskal algoritmi
Kruskal algoritmida qirralarning butun birlashtirilgan ro'yxati
kamaymaydigan uch darajalariga muvofiq tartiblangan. Bundan tashqari,
qirralar darajalari kichikroq bo'lgan qirralardan yuqori tomonga siljiydi
va keyingi uch ilgari tanlangan qirralar bilan sikl hosil qilmasa, karkasga
qo'shiladi. Xususan, grafdagi minimal darajadagi qirralaridan biri har
doim birinchi bo'lib tanlanadi.
Tanlangan qirralarning sikl hosil qilmasligini tekshirish uchun biz
grafni bir nechta bogʻlangan komponentlarning birlashishi sifatida
namoyish etamiz. Eng boshida, grafning chekkalari tanlanmaganida, har
bir uch alohida bogʻlangan komponent hisoblanadi. Yangi qirralar
qo'shilganda, ulanish komponentlari bitta umumiy ulanish komponenti
bo'lguncha
birlashadi.
Barcha
bogʻlangan
tarkibiy
qismlarni
raqamlaymiz va har bir uch uchun uning ulangan qismlarini sonini
saqlaymiz, shuning uchun har bir uch uchun boshida uning bogʻlangan
komponentlari soni uchning o'zi soniga teng bo'ladi va oxirgi barcha
176
uchlar bir-biriga bogʻlangan komponentning bir xil raqamlariga tegishli
bo'ladi.
Keyingi qirrani ko'rib chiqayotganda, ushbu qirraning uchlariga
to'gʻri keladigan ulangan komponentlarning raqamlarini ko'rib chiqamiz.
Agar bu raqamlar bir xil bo'lsa, unda qirra allaqachon bir xil bogʻlangan
komponentda joylashgan ikkita uchni birlashtiradi, shuning uchun bu
qirrani qo'shish siklni tashkil qiladi. Agar qirra ikki xil bogʻlangan
komponentni, masalan,
va
raqamlari bilan bogʻlasa, u holda qirra
asosiy daraxtning bir qismiga qo'shiladi va bu ikkita bogʻlangan
komponentlar birlashtiriladi. Buning uchun, masalan, ilgari
komponentida bo'lgan barcha uchlar uchun komponent raqamini
ga
o'zgartirish kerak.
Kruskal algoritmini amalga oshirish bosqichlari quyidagicha:
1) Barcha qirralarni quyidan yuqorigacha saralash.
2) Vazni eng kichik qirrasini oling va uni daraxtga qo'shing. Agar qirra
qoʻshilganda, sikl hosil boʻlsa, u holda bu qirrani olib tashlang.
3) Barcha uchlarga yetguncha qirralarni qo'shishni davom eting.
Quyidagi rasmda minimal uzunlikka kiritilgan qirralar qizil rang
bilan, qora rang bilan esa nomzodlar ulardan eng kam darajadagi qirra
tanlangan.
1-qadam
2-qadam
177
3-qadam
4-qadam. (Soʻnggi natija)
|
