Vpeto drevo

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Vpeto drevo (modre debelejše povezave) grafa rešetke na 16-tih točkah

Vpeto drevo T povezanega neusmerjenega grafa G je v teoriji grafov drevo, ki ga sestavljajo vse točke in nekatere (ali morda vse) povezave G. Vpeto drevo je izbira povezav G, ki tvorijo drevo prek vseh točk. To pomeni, da vsaka točka leži na drevesu, pri tem pa ne nastane noben cikel (ali zanka). Na drugi strani mora vsak most G pripadati T.

Vpeto drevo povezanega grafa G lahko definiramo tudi kot maksimalno množico povezav G, ki ne vsebuje ciklov, ali kot minimalno množico povezav, ki povezuje vse točke.