hippies píše:Neměl by tu někdo autorské řešení na 2. a 3. příklad?
Ten druhý příklad jsem řešil následovně:
I. Přidal jsem ke grafu jeden vrchol, který jsem označil jako zdroj a natáhl z něj hrany s jednotkovou kapacitou ke všem černým vrcholům uvnitř mřížky (ne těm na okraji)
II. Obdobně jsem přidal stok a hrany s jednotkovými kapacitami z bílých vrcholů na okraji.
III. Pak jsem přidělil všem hranám mezi vrcholy na okraji a těm, které vycházely z černých vrcholů na okraji kapacitu 0 a zbylým 1.
IV. Pomocí Ford-Fulkersona jsem našel max. tok (Ford-Fulkerson je na sítích s jednotkovými kapacitami nejrychlejší) a díval jsem se na jeho velikost.
Výsledek: Označím-li m' počet černých vrcholů bez těch na okraji, pak pokud
- byl max. tok >= m' tyto cesty existovaly
- jinak ne
Je v tom ještě jedna drobnost a to, že takhle by ten algo nezajistil vrcholovou disjunktnost těch cest, ale to se vyřeší fíglem:
Každý vrchol se rozdělí na dva, do jednoho povedou všechny vstupní hrany z druhého půjdou všechny výstupní a mezi nimi povede jen hrana kapacity 1.
Pak to funguje (alespoň zkoušející to uznal
)
Třetí příklad jsem zvoral, ale i tak jsem dostal z písemky 2 body a nakonec jedničku, takže hlavu vzhůru, není to tak zlé
Přeji všem, které to ještě čeká hodně štěstí a na viděnou v dalším semestru
[quote="hippies"]Neměl by tu někdo autorské řešení na 2. a 3. příklad?[/quote]
Ten druhý příklad jsem řešil následovně:
I. Přidal jsem ke grafu jeden vrchol, který jsem označil jako zdroj a natáhl z něj hrany s jednotkovou kapacitou ke všem černým vrcholům uvnitř mřížky (ne těm na okraji)
II. Obdobně jsem přidal stok a hrany s jednotkovými kapacitami z bílých vrcholů na okraji.
III. Pak jsem přidělil všem hranám mezi vrcholy na okraji a těm, které vycházely z černých vrcholů na okraji kapacitu 0 a zbylým 1.
IV. Pomocí Ford-Fulkersona jsem našel max. tok (Ford-Fulkerson je na sítích s jednotkovými kapacitami nejrychlejší) a díval jsem se na jeho velikost.
Výsledek: Označím-li m' počet černých vrcholů bez těch na okraji, pak pokud
- byl max. tok >= m' tyto cesty existovaly
- jinak ne
:!: Je v tom ještě jedna drobnost a to, že takhle by ten algo nezajistil vrcholovou disjunktnost těch cest, ale to se vyřeší fíglem:
Každý vrchol se rozdělí na dva, do jednoho povedou všechny vstupní hrany z druhého půjdou všechny výstupní a mezi nimi povede jen hrana kapacity 1.
Pak to funguje (alespoň zkoušející to uznal :D )
Třetí příklad jsem zvoral, ale i tak jsem dostal z písemky 2 body a nakonec jedničku, takže hlavu vzhůru, není to tak zlé :)
Přeji všem, které to ještě čeká hodně štěstí a na viděnou v dalším semestru :D