Matematické Fórum

slender · 23. 11. 2016 15:57

Ahoj,
řeším následující úlohu a nejsem si jist, zda správně analyzuji časovou složitost.

Snažím se najít příklad konkrétní sítě, ve které by Dinicův algoritmus udělal $\lvert V\rvert^2\lvert E\rvert$ kroků.

Napadlo mě, zda by nestačila jednoduchá síť o dvou vrcholech, kdy jeden je zdroj, druhý je stok a jsou spojeny hranou. Algoritmus by měl udělat $2^2\cdot 1=4$ kroků. Tady si nejsem jist svou analýzou:

1) Prohledání dítě ze stoku do šířky a rozdělení do vrstev (1 krok)
2) Kontrola každé hrany, odstranění všech hran, které nejsou dopředné (1 krok)
3) Nalezení cesty ze zdroje do stoku (1 krok)
4) Odstranění nasycené hrany (1 krok)

Je tato analýza správná, tedy je graf $G=(\{u,v\},\{(u,v)\})$ s kapacitami $c(u,v)=1$ příkladem sítě, kdy poběží Dinitzův algoritmus v čase $\lvert V\rvert^2\lvert E\rvert$ ?

Matematické Fórum

#1 23. 11. 2016 15:57

Kdy udělá Dinitzův algoritmus co nejvíc kroků? (kontrola řešení)

Zápatí