Mti unaoenea kwa kiwango cha chini zaidi au mti unaopanuka kwa uzito wa chini zaidi ni kitengo kidogo cha kingo za grafu isiyoelekezwa iliyounganishwa, yenye uzito wa ukingo ambayo inaunganisha wima zote pamoja, bila mizunguko yoyote na yenye uzito wa chini kabisa unaowezekana wa ukingo. Yaani ni mti unaotambaa ambao jumla ya uzani wake wa makali ni ndogo iwezekanavyo.
Mti wa chini kabisa unaozunguka ni upi kwa mfano?
Mti wa chini kabisa unaosambaa ni aina maalum ya mti ambao hupunguza urefu (au "uzito") wa kingo za mti. Mfano ni kampuni ya kebo inayotaka kuweka laini kwenye vitongoji vingi; kwa kupunguza kiasi cha cable iliyowekwa, kampuni ya cable itaokoa pesa. Mti una njia moja inayounganisha wima zozote mbili.
Je, unapataje mti wa chini kabisa unaozunguka?
Tafuta jirani ya karibu isiyo na rangi kwenye grafu ndogo nyekundu (yaani, kipeo kilicho karibu zaidi na kipeo chochote chekundu). Weka alama na ukingo unaounganisha kipeo kwenye sehemu ndogo nyekundu kwa rangi nyekundu. Rudia Hatua ya 2 hadi wima zote ziweke alama nyekundu. Sehemu ndogo nyekundu ni mti wa kiwango cha chini kabisa unaozunguka.
Unamaanisha nini unapotanisha mti na mti unaosambaa kwa kiwango cha chini zaidi?
Mti unaozunguka wa grafu ni mkusanyiko wa kingo zilizounganishwa zinazojumuisha kila kipeo kwenye grafu, lakini ambazo hazifanyi mzunguko. … The Minimum Spanning Tree ni ule ambao uzito wake limbikizi una thamani ndogo zaidi, hata hivyo.
Kuna tofauti gani kati ya mti unaopeperuka na mti unaotambaa kwa uchache zaidi?
Kama grafu nikwa uzani, tunaweza kufafanua uzito ya mti unaotambaa kama jumla ya uzani wa kingo zake zote. Kima cha chini zaidi cha mti unaosambaa ni mti unaotambaa ambao uzani wake ni mdogo kuliko miti yote inayoweza kutambaa.
