Minimal qamrovchi daraxt

---

Minimal qamrovchi daraxt masalasi

Minimal qamrovchi daraxt (MST) — yo‘naltirilmagan grafdagi barcha cho‘qqilarni eng kichik umumiy qirra vazni bilan bog‘lash uchun zarur bo‘lgan qirralar to‘plami.

Yuqoridagi animatsiya MST’ni topish uchun Prim algoritmini ishga tushiradi. MST’ni topishning bog‘lamli bo‘lmagan graflar uchun ham ishlaydigan boshqa usuli — Kruskal algoritmini ishga tushirish.

U minimal qamrovchi daraxt deb ataladi, chunki u bog‘lamli, siklsiz, yo‘naltirilmagan graf bo‘lib, bu daraxt ma’lumotlar tuzilmasining ta’rifiga mos keladi.

Real hayotda minimal qamrovchi daraxtni topish uylarni internetga yoki elektr tarmog‘iga ulashning eng samarali usulini topishga yoki posilkalarni yetkazib berishning eng tez marshrutini topishga yordam beradi.

---

---

MST bo‘yicha fikriy tajriba

Tasavvur qilaylik, yuqoridagi animatsiyadagi doiralar elektr energiyasi bo‘lmagan qishloqlar va siz ularni elektr tarmog‘iga ulamoqchisiz. Bitta qishloqqa elektr energiyasi berilgach, elektr kabellari shu qishloqdan boshqalariga tortilishi kerak. Qishloqlarni juda ko‘p turli usullarda ulash mumkin va har bir marshrutning narxi turlicha.

Elektr kabellari qimmat, kabellar uchun ariq qazish yoki kabellarni havo orqali tortish ham qimmatga tushadi. Joy relyefi ham, albatta, qiyinchilik tug‘dirishi mumkin, bundan tashqari, kelajakda texnik xizmat ko‘rsatish xarajatlari ham bo‘lishi mumkin va ular kabellar qayerdan o‘tishiga qarab turlicha bo‘ladi.

Bu marshrut xarajatlarining barchasini grafdagi qirra vaznlari sifatida hisobga olish mumkin. Har bir cho‘qqi qishloqni, har bir qirra esa ikki qishloq orasidagi elektr kabeli uchun mumkin bo‘lgan marshrutni ifodalaydi.

Bunday graf yaratilgach, minimal qamrovchi daraxtni (MST) topish mumkin va bu ushbu qishloqlarni elektr tarmog‘iga ulashning eng samarali usuli bo‘ladi.

Aslida birinchi MST algoritmi (Borůvka algoritmi) 1926-yilda aynan shu maqsadda yaratilgan: Chexiyadagi tarixiy Moraviya hududini elektr tarmog‘iga ulashning eng yaxshi usulini topish uchun.

---

MST algoritmlari

Ushbu darslikning keyingi ikki sahifasida grafda minimal qamrovchi daraxtni topadigan ikkita algoritm tushuntiriladi: Prim algoritmi va Kruskal algoritmi.

---