(Ohjaamattoman) yhdistetyn painotetun graafin pienin virittävä puu (tai pienin virittävä puu ) on tämän graafin virittävä puu , jolla on pienin mahdollinen paino, jossa puun paino on sen reunojen painojen summa.
Vähimmäisvirittävän puun löytämisen ongelma esiintyy usein samanlaisessa ympäristössä: oletetaan, että on n kaupunkia, jotka on yhdistettävä teiden kautta, jotta mistä tahansa kaupungista pääsee toiseen (suoraan tai muiden kaupunkien kautta). Tiettyjen kaupunkiparien välille saa rakentaa teitä ja kunkin tällaisen tien rakentamiskustannukset tunnetaan. Rakentamisen kokonaiskustannusten minimoimiseksi on päätettävä, mitkä tiet rakennetaan.
Tämä ongelma voidaan muotoilla graafiteorian kannalta ongelmana löytää pienin virittävä puu graafista, jonka kärjet edustavat kaupunkeja, reunat ovat kaupunkipareja, joiden välille voidaan muodostaa suora tie ja reunan paino on yhtä suuri. vastaavan tien rakentamiskustannuksiin.
Vähimmäisvirittävän puun löytämiseksi on useita algoritmeja. Jotkut tunnetuimmista on lueteltu alla:
Steiner-puun ongelma on samanlainen kuin minimivirittävän puun ongelma . Se sisältää useita tasossa olevia pisteitä, ja niiden väliin on asetettava kaavio polkuista siten, että polun pituuksien summa minimoidaan. Suurin ero tässä tapauksessa pienimmän virittävän puun ongelmaan on se, että on sallittua lisätä ylimääräisiä haarapisteitä reunojen pituuksien summan pienentämiseksi entisestään. Steiner-puuongelma on NP-täydellinen .
| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| Muut | ||