Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 23. 11. 2016 15:57

slender
Příspěvky: 151
Pozice: student
Reputace:   
 

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

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$?

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson