od pasky » 13. 6. 2011 19:35
Tahle pisemka byla snadna, pokud jste meli jeden napad, nebo se aspon chytli a stihli zuzitkovat Cepkuv hint ve 2/3 zkousky ("uvedomte si, ze takovehle grafove veci se casto dokuzuji nejdriv zvlast pro SS komponenty, pak pro acyklicke grafy, pak pro obecne grafy (ty dva pripady dohromady)"). Jinak to bylo neprijemne, protoze oba priklady byly skoro to same. Kazdopadne jednomu cloveku rikal, ze se s nim da domluvit na dalsim opravnem terminu, bude tu do konce cervna...
O co slo:
1. Je dan orientovany graf G=(V,E). Jeho tranzitivni redukce se definuje jako graf G'=(V,E'), aby G a G' mely shodny tranzitivni uzaver a E' byla minimalni. Navrhnete a dokazte polynomialni algoritmus vyrabejici redukci.
2. Je dan orientovany graf G=(V,E). Jeho tranzitivni podredukce se definuje jako podgraf G'=(V,E'), kde E' \subset E a plati, ze G a G' maji shodny tranzitivni uzaver a E' je minimalni. Dokazte, ze toto je NP-uplny problem. Tedy NP-uplnost nasledujiciho problemu:
Instance: orientovany graf G=(V,E), cislo k \in N
Otazka: existuje tranzitivni redukce grafu G s nejvyse k hranami? (|E'| <= k)
Jen velmi heslovite (jak jsem zhruba tapal)... ano, je to to same, ale uz ze zadani vime, ze pokud musime v redukci pouzivat pouze stavajici hrany, je to NP-tezke, pokud si muzeme hrany ponapajet sami, uz to lze resit rychle. Nejprve je treba si uvedomit, ze graf je orientovany, takze nestaci postavit kostru.
No jo, tak jake mohou byt problemy... jednak hrany, ktere preskakuji v tranzitivnich retizcich nejake vrcholy, druhak hrany navic uvnitr cyklu.
Takhle jsem se placal, az hint mne konecne nakopl. Rozeberu-li pripady, s SS komponentami si mohu poradit tak, ze je pretransformuji na cyklus prochazejici vsehny vrcholu uvnitr a v puvodnim grafu je pro dalsi ucely zkontrahuji do jedineho vrcholu. Zbyde mi usmerneny acyklicky graf, musim si ale rozmyslet, jak ho prochazet, abych nepropasl zadnou zbytecnou hranu. Cepek pak ukazal trivialni zpusob - proste v tomhle grafu beru kazdou hranu, zkusim ji odebrat a testuji, zda se zmenil tranzitivni uzaver. Ja vymyslel slozitejsi, ale trochu rychlejsi - pro kazdy vrchol si spocitam rank: velikost tranzitivniho uzaveru vrcholu, tedy pocet vrcholu, do kterych z nej dokazu dojit. Rank nam pak jednoznacne urci poradi vrcholu - staci opakovane poustet DFS z vrcholu s nejvetsim rankem a deti take brat sestupne dle ranku; ignorovat budu pouze dopredne hrany, zbytek opisu do redukce. Je celkem videt, ze hrany navic jsou prave jen ty dopredne, vsechny ostatni prinaseji oproti konkurentum nejaky vrchol navic.
Co se tyce NP-uplnosti, uvedomi-li si clovek, jak nalozit s SS komponentami, muze to uz byt nasnade - nemusim-li vyuzivat existujici hrany, staci postavit cyklus naprosto arbitrarne hned; pokud ale musim vyuzivat existujici hrany, je postaveni cyklu pres vsechny vrcholy doslova Hamiltonovska kruznice! Tedy muzu (neorientovanou) HK prevest na TpU; neorientovane hrany nahradim dvojicemi opacne jdoucich orientovanych, pokud byla HK v puvodnim grafu, je tohle SS graf. Najdu TpU, pokud pokyrva vysledny uzaver vsechny vrcholy a ma prave |V| hran, musi to byt hledana HK. (A naopak HK v puvodnim grafu dava TpU v tom orientovanem.)
Na ustni ulohy jsme prezili z prvni pulky jen dva, kolega dostal pseudopolynomialni algoritmy (co to je a priklad) a NP-tezkost, ja jsem mel za ukol popsat nejakou ulohu, ktera nelze resit s konstantni pomerovou chybou (nakonec jsme dokongvergovali k prikladu z prednasky na TSP, umime-li resit s pomerovou chybou r, muzeme pomoci toho resit HK tak, ze graf HK zuplnime a stare/nove hrany vhodne ohodnotime podle r,n, aby TSP byl nucen vybrat HK; potreboval jsem par hintu, takze za dva).
Tahle pisemka byla snadna, pokud jste meli jeden napad, nebo se aspon chytli a stihli zuzitkovat Cepkuv hint ve 2/3 zkousky ("uvedomte si, ze takovehle grafove veci se casto dokuzuji nejdriv zvlast pro SS komponenty, pak pro acyklicke grafy, pak pro obecne grafy (ty dva pripady dohromady)"). Jinak to bylo neprijemne, protoze oba priklady byly skoro to same. Kazdopadne jednomu cloveku rikal, ze se s nim da domluvit na dalsim opravnem terminu, bude tu do konce cervna...
O co slo:
1. Je dan orientovany graf G=(V,E). Jeho tranzitivni redukce se definuje jako graf G'=(V,E'), aby G a G' mely shodny tranzitivni uzaver a E' byla minimalni. Navrhnete a dokazte polynomialni algoritmus vyrabejici redukci.
2. Je dan orientovany graf G=(V,E). Jeho tranzitivni podredukce se definuje jako podgraf G'=(V,E'), kde E' \subset E a plati, ze G a G' maji shodny tranzitivni uzaver a E' je minimalni. Dokazte, ze toto je NP-uplny problem. Tedy NP-uplnost nasledujiciho problemu:
Instance: orientovany graf G=(V,E), cislo k \in N
Otazka: existuje tranzitivni redukce grafu G s nejvyse k hranami? (|E'| <= k)
Jen velmi heslovite (jak jsem zhruba tapal)... ano, je to to same, ale uz ze zadani vime, ze pokud musime v redukci pouzivat pouze stavajici hrany, je to NP-tezke, pokud si muzeme hrany ponapajet sami, uz to lze resit rychle. Nejprve je treba si uvedomit, ze graf je orientovany, takze nestaci postavit kostru. ;-) No jo, tak jake mohou byt problemy... jednak hrany, ktere preskakuji v tranzitivnich retizcich nejake vrcholy, druhak hrany navic uvnitr cyklu.
Takhle jsem se placal, az hint mne konecne nakopl. Rozeberu-li pripady, s SS komponentami si mohu poradit tak, ze je pretransformuji na cyklus prochazejici vsehny vrcholu uvnitr a v puvodnim grafu je pro dalsi ucely zkontrahuji do jedineho vrcholu. Zbyde mi usmerneny acyklicky graf, musim si ale rozmyslet, jak ho prochazet, abych nepropasl zadnou zbytecnou hranu. Cepek pak ukazal trivialni zpusob - proste v tomhle grafu beru kazdou hranu, zkusim ji odebrat a testuji, zda se zmenil tranzitivni uzaver. Ja vymyslel slozitejsi, ale trochu rychlejsi - pro kazdy vrchol si spocitam rank: velikost tranzitivniho uzaveru vrcholu, tedy pocet vrcholu, do kterych z nej dokazu dojit. Rank nam pak jednoznacne urci poradi vrcholu - staci opakovane poustet DFS z vrcholu s nejvetsim rankem a deti take brat sestupne dle ranku; ignorovat budu pouze dopredne hrany, zbytek opisu do redukce. Je celkem videt, ze hrany navic jsou prave jen ty dopredne, vsechny ostatni prinaseji oproti konkurentum nejaky vrchol navic.
Co se tyce NP-uplnosti, uvedomi-li si clovek, jak nalozit s SS komponentami, muze to uz byt nasnade - nemusim-li vyuzivat existujici hrany, staci postavit cyklus naprosto arbitrarne hned; pokud ale musim vyuzivat existujici hrany, je postaveni cyklu pres vsechny vrcholy doslova Hamiltonovska kruznice! Tedy muzu (neorientovanou) HK prevest na TpU; neorientovane hrany nahradim dvojicemi opacne jdoucich orientovanych, pokud byla HK v puvodnim grafu, je tohle SS graf. Najdu TpU, pokud pokyrva vysledny uzaver vsechny vrcholy a ma prave |V| hran, musi to byt hledana HK. (A naopak HK v puvodnim grafu dava TpU v tom orientovanem.)
Na ustni ulohy jsme prezili z prvni pulky jen dva, kolega dostal pseudopolynomialni algoritmy (co to je a priklad) a NP-tezkost, ja jsem mel za ukol popsat nejakou ulohu, ktera nelze resit s konstantni pomerovou chybou (nakonec jsme dokongvergovali k prikladu z prednasky na TSP, umime-li resit s pomerovou chybou r, muzeme pomoci toho resit HK tak, ze graf HK zuplnime a stare/nove hrany vhodne ohodnotime podle r,n, aby TSP byl nucen vybrat HK; potreboval jsem par hintu, takze za dva).