rafy - minimální kostry
Mějme ohodnocený neorientovaný graf G = (\/, E, w) s minimální kostrou M. Ukažte, jak přepočítat minimální kostru při následujících změnách v grafu:
1. Odstraníme z grafu jednu hranu.
2. Přidáme do grafu jednu novou hranu.
3. Vybereme jednu hranu grafu a zvětšíme její ohodnocení.
4. Vybereme jednu hranu grafu a zmenšíme její ohodnocení.
Grafy - minimální kostry
Mějme kladně ohodnocený neorientovaný graf G = (\/, E, w) a vrchol s G V. Spustíme Dijkstrův algoritmus pro hledání nejkratších cest z vrcholu s. To nám dá strom nejkratších cest.
► Rozhodněte a dokažte: Je tento strom zároveň minimální kostrou grafu Gl
Grafy - minimální kostry
Mějme kladně ohodnocený neorientovaný graf G = (\/, E, w) a vrchol s G V. Spustíme Dijkstrův algoritmus pro hledání nejkratších cest z vrcholu s. To nám dá strom nejkratších cest.
► Rozhodněte a dokažte: Je tento strom zároveň minimální kostrou grafu Gl
► Rozhodněte a dokažte: Dá se v grafu G najít takový počáteční vrchol s, aby jeho strom nejkratších cest byl minimální kostrou grafu Gl
Grafy - maximální toky
Mějme síť (graf s kapacitami, zdrojem a cílem) G = (\/, E, c,s, t) a její maximální tok f. Ukažte, jak přepočítat maximální tok při následujících změnách v síti:
1. Vybereme jednu hranu a zvětšíme její kapacitu o 1.
2. Vybereme jednu hranu a zmenšíme její kapacitu o 1.
(Předpokládejme, že jak kapacity hran, tak i hodnota toku f na každé hraně jsou nezáporná celá čísla.)
rafy - použití maximálních toků
Pokrytí šachovnice dominem
Mějme šachovnici n x m, na níž jsou některé pole obsazena kameny. Chceme zjistit, zda můžeme všechna prázdná pole šachovnice pokrýt kostkami domina (velikosti 1x2 pole šachovnice). Kostky domina se nesmí překrývat a nesmí být položeny na obsazená pole.
► Jak převedeme tento problém na hledání maximálního toku?