Minimal va maksimal qamrovchi daraxtlar

Minimal va maksimal qamrovchi daraxtlar

Qamrab oluvchi daraxt bog‘langan yo‘naltirilmagan grafning — bu grafning barcha cho‘qqilarini o‘z ichiga oladigan daraxt.
Minimal qamrab oluvchi daraxt (MST) — qirralar og‘irliklari yig‘indisi imkon qadar minimal bo‘lgan qamrab oluvchi daraxt.
Xuddi shunday, maksimal qamrab oluvchi daraxt — qirralar og‘irliklari yig‘indisi imkon qadar maksimal bo‘lgan qamrab oluvchi daraxt.

Minimal qamrab oluvchi daraxtning xossalari

• Yagonalik
  Agar grafning barcha qirralari turli og‘irliklarga ega bo‘lsa, minimal qamrab oluvchi daraxt yagona bo‘ladi.
  Agar esa ayrim qirralar bir xil og‘irliklarga ega bo‘lsa, unda bir nechta turli MST mavjud bo‘lishi mumkin.

• Og‘irliklar ko‘paytmasini minimallashtirish
  Minimal qamrab oluvchi daraxt nafaqat yig‘indini, balki o‘z qirralari og‘irliklarining ko‘paytmasini ham minimallashtiradi.
  Buni og‘irliklarning logarifmlariga o‘tish orqali tushunish mumkin: logarifmlar yig‘indisini minimallashtirish ko‘paytmaning logarifmini minimallashtirishga ekvivalent.

• Maksimal qamrab oluvchi daraxt
  Maksimal qamrab oluvchi daraxtni MSTga o‘xshash tarzda topish mumkin. Buning uchun barcha qirralar og‘irliklarining ishorasini o‘zgartirish va minimal qamrab oluvchi daraxtni topishning istalgan algoritmini (masalan, Kruskal algoritmini) qo‘llash kifoya.