Virittävä puu

Wikipediasta
Siirry navigaatioon Siirry hakuun
Esimerkki pienimmästä virittävästä puusta graafissa G. Virittävä puu T on yhtenäinen (korostetut osat) ja sen kaarien painoarvo on pienin mahdollinen.
Kolme esimerkkiä neliön ruudukkokuviossa 8x8.

Virittävä puu (engl. Spanning Tree) on graafiteoriassa sellainen aligraafi T graafissa G, joka on yhtenäinen syklitön aligraafi, joka sisältää kaikki G:n solmut.

Pienin ja suurin virittävä puu

[muokkaa | muokkaa wikitekstiä]

Virittävien puiden yhteydessä puhutaan usein pienimmästä ja suurimmasta virittävästä puusta (joskus myös minimi ja maksimi), joiden määritelmänä on virittävän puun määritelmä, mutta siten, että painotettujen (suunnattujen tai suuntaamattomien) kaarien paino on pienin tai suurin mahdollinen. Graafilla voi olla useita virittäviä puita.

Pienimmän virittävän puun löytämiseksi on esitetty useita algoritmeja, joista tunnetuimpia ovat