Spanning Tree and Minimum Spanning Tree

Qoplovchi daraxt (spanning tree) haqida o'rganishdan oldin, biz ikkita turdagi grafni tushunib olishimiz kerak: yo'naltirilmagan graflar (undirected graphs) va bog'langan graflar (connected graphs).

Yo'naltirilmagan graf (Undirected graph) — bu qirralari biron-bir aniq yo'nalishga ega bo'lmagan (ya'ni qirralar ikki tomonlama / ikki yo'nalishli bo'lgan) grafdir.

Yo'naltirilmagan graf (Undirected Graph)

Bog'langan graf (Connected graph) — bu har qanday cho'qqidan boshqa ixtiyoriy cho'qqiga olib boruvchi yo'l har doim mavjud bo'lgan grafdir.

Bog'langan graf (Connected Graph)

---

Qoplovchi daraxt

Qoplovchi daraxt (Spanning tree) — bu yo'naltirilmagan bog'langan grafning qism-grafi (sub-graph) bo'lib, u grafning barcha cho'qqilarini mumkin bo'lgan eng kam sonli qirralar bilan o'z ichiga oladi. Agar birorta ham cho'qqi tushib qolsa, u qoplovchi daraxt bo'la olmaydi.

Qirralar o'z og'irliklariga (weights) ega bo'lishi ham, bo'lmasligi ham mumkin.

[!NOTE] To'liq grafdan (complete graph) hosil qilinishi mumkin bo'lgan n ta cho'qqili qoplovchi daraxtlarning umumiy soni n^(n-2) ga teng (Keyli formulasi / Cayley's formula).

Agar bizda n = 4 bo'lsa, mumkin bo'lgan qoplovchi daraxtlarning maksimal soni 4^(4-2) = 4^2 = 16 ga teng bo'ladi. Demak, 4 ta cho'qqiga ega to'liq grafdan 16 ta turli qoplovchi daraxt hosil qilish mumkin.

---

Qoplovchi daraxtga misol

Keling, qoplovchi daraxtni quyidagi misollar orqali tushunib olaylik:

Dastlabki asl graf quyidagicha bo'lsin:

Oddiy graf (Normal graph)

Yuqoridagi grafdan hosil qilinishi mumkin bo'lgan qoplovchi daraxtlarning ba'zilari:

Qoplovchi daraxt — 1

Qoplovchi daraxt — 2

Qoplovchi daraxt — 3

Qoplovchi daraxt — 4

Qoplovchi daraxt — 5

Qoplovchi daraxt — 6

---

Minimal qoplovchi daraxt

Minimal qoplovchi daraxt (Minimum Spanning Tree - MST) — bu qirralarining og'irliklari yig'indisi mumkin qadar eng kichik (minimal) bo'lgan qoplovchi daraxtdir.

---

Minimal qoplovchi daraxtga misol

Keling, yuqoridagi ta'rifni quyidagi misol yordamida tahlil qilaylik.

Dastlabki og'irlikli graf:

Og'irlikli graf (Weighted graph)

Ushbu grafdan hosil bo'lishi mumkin bo'lgan qoplovchi daraxtlar:

Qoplovchi daraxt — 1 (Og'irliklar yig'indisi: masalan, 1+4+3 = 8)

Qoplovchi daraxt — 2 (Og'irliklar yig'indisi: masalan, 1+2+4 = 7)

Qoplovchi daraxt — 3 (Og'irliklar yig'indisi: masalan, 2+4+3 = 9)

Qoplovchi daraxt — 4 (Og'irliklar yig'indisi: masalan, 1+2+3 = 6)

Yuqoridagi barcha mumkin bo'lgan qoplovchi daraxtlar orasidan eng kichik umumiy vaznga ega bo'lgan minimal qoplovchi daraxt (MST) quyidagicha:

Minimal qoplovchi daraxt (Minimum Spanning Tree)

Grafdan minimal qoplovchi daraxtni topish uchun quyidagi mashhur algoritmlardan foydalaniladi:

1. Prim algoritmi (Prim's Algorithm)
2. Kruskal algoritmi (Kruskal's Algorithm)

---

Qoplovchi daraxtning qo'llanilishi

• Kompyuter tarmoqlarida marshrutlash protokollari (Computer Network Routing Protocol): Tarmoqlarda halqalanish (loop) hosil bo'lishining oldini olish uchun (masalan, STP — Spanning Tree Protocol).
• Klaster tahlili (Cluster Analysis): Ma'lumotlar nuqtalarini klasterlarga ajratishda.
• Fuqarolik infratuzilmasi tarmoqlarini rejalashtirish (Civil Network Planning): Yo'llar, aloqa va taqsimlash tarmoqlarini loyihalashda.

---

Minimal qoplovchi daraxtning qo'llanilishi

• Xaritalarda eng qulay yo'llarni topish: Geografik yo'nalishlar va logistika tizimlarida.
• Tarmoqlarni optimal loyihalash: Telekommunikatsiya tarmoqlari, suv ta'minoti quvurlari va elektr tarmoqlarini eng kam xarajat bilan barcha nuqtalarga yetkazish uchun loyihalashda.