Fórum studentů MFF UK

Jasne, skoda, ze jsem nad tim nepremyslel o chvili dele Diky oboum!

Him píše:Díky!

Jen moc nevidím, proč ten můj algoritmus by neměl fungovat, přijde mi, že ty dva algoritmy jsou vlastně stejné, zvlášť když se to odehrává na stromech.

Nebyl by protipříkladem graf >-< ? V případě obarvení dvěma barvami budeš mít obě komponenty velikosti 3, ale MNM je velikosti 4.

Díky!

Jen moc nevidím, proč ten můj algoritmus by neměl fungovat, přijde mi, že ty dva algoritmy jsou vlastně stejné, zvlášť když se to odehrává na stromech.

Neodvážím se tady napsat, že tento algoritmus nefunguje a protože mám zkoušku za sebou, napíšu jen to, co bych napsal já.

Řešení problému maximální nezávislé množiny je duální k řešení maximálního vrcholového pokrytí - bylo na cvičení.
Jinými slovy, doplněk minimálního VP jsou právě vrcholy maximální NM.
(dokazuje se to jednoduchými argumenty, jako kdyby doplněk minVP nebyla nezávislá množina, existovala by nepokrytá hrana a kdyby NM nebyla maximální, existoval by ve VP pokrytí vrchol, který můžu odebrat a stále to bude VP - spor s minimalitou)

No a pro strom umíme najít minVP následujícím algoritmem:

Pomocí DFS procházím strom (nejlépe z vrcholu stupně alespoň 2) a dělám následující:
-pokud jsem v listu, neoznačím se
-pokud jsem ve vnitřním vrcholu a mám neoznačeného syna, označím se (nebol-li, pokud backtrackuju z neoznačeného syna, označím se, jinak nic)

Označené vrcholy potom tvoří minVP. Jejich doplněk potom maxNM. A jestli DFS prochází strom nebo les je v podstatě jedno.

Jaka je slozitost NM pro acyklicke neorientovane grafy?
Navrhnete polynomialni algoritmus, nebo dokazte ze je NPU.

Koukam na tento priklad a v reseni je napsano:

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)

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.

Algoritmus je polynomialni: O(n+m)

Je to tak?