Santa Claus — 2022-04-14 14:22 (266 days ago) — edit — reply
Vzhledem k tomu, že z hran incidentních vrcholu z $U$ bude v kostře od každého vrcholu jen jedna, můžeme k problému přisoupit takto: Nejdříve z grafu všechny vrcholy $U$ odebereme, pokud vytvořený graf není souvislý, daná kostra nejde sestrojit. Na zbylém grafu pak spustíme standartní algoritmus. K nalezené kostře přilepíme vrcholy $U$, a to tak, že pro každý $u \in U$ vybereme hranu incidentní s $u$ a s jedním vrcholem, který není v $U$, a sice z těchto hran tu s minimálním ohodnocením. Pokud taková hrana neexistuje, kostra s danými listy nejde sestrojit. Jako standartní algoritmus můžeme použít například Jarníkův algoritmus. Veškeré průchody včetně případného ověření souvislosti grafu se nám schovají do asymptotické složitosti standartního algoritmu: při přilepování vrcholů projdeme všechny vrcholy z $U$ jednou a každou hranu maxímálně dvakrát.