slozitost NM pro acyklicke neorientovane grafy

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

slozitost NM pro acyklicke neorientovane grafy

Příspěvek od Him »

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?
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
JiriD
Matfyz(ák|ačka) level I
Příspěvky: 44
Registrován: 2. 2. 2008 09:35
Typ studia: Informatika Bc.

Re: slozitost NM pro acyklicke neorientovane grafy

Příspěvek od JiriD »

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.
Wenn ich morgen meinem Gott gegenüberstehe, kann ich sagen:
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.

Und das wird er mir wohl verzeihen!
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: slozitost NM pro acyklicke neorientovane grafy

Příspěvek od Him »

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.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Germoe
Matfyz(ák|ačka) level I
Příspěvky: 34
Registrován: 28. 5. 2008 15:40
Typ studia: Informatika Ph.D.

Re: slozitost NM pro acyklicke neorientovane grafy

Příspěvek od Germoe »

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.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: slozitost NM pro acyklicke neorientovane grafy

Příspěvek od Him »

Jasne, skoda, ze jsem nad tim nepremyslel o chvili dele :) Diky oboum!
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Odpovědět

Zpět na „TIN062 Složitost I“