Koukam na tento priklad a v reseni je napsano:Jaka je slozitost NM pro acyklicke neorientovane grafy?
Navrhnete polynomialni algoritmus, nebo dokazte ze je NPU.
Co rici, ze vezmu ten graf a pomoci DFS ho obarvim dvema barvami. Protoze mam v obecnem pripade les, tak kazdy strom obarvuji jednoduse tak, ze zacnu s prvni barvou a vsem jeho sousedum dam druhou barvu a takto to stridam dal. Vznikne mi obarveny les a nyni pouze sectu pro jednotlive stromy cisla max(#pocet_vrcholu_s_barvou_1, #pocet_vrcholu_s_barvou_2) a dostavam velikost maximalni nezavisle mnoziny.lze v O(n+m) pomoci DFS...v maximalni nezavisle mnozine jsou listy a nejsou jejich rodice...induktivne se da dopocitat jeji velikost. (ale chtelo to trochu prodokazovat)
Algoritmus je polynomialni: O(n+m)
Je to tak?