From f7175bf1b61778276d4d6704f525b406eac6b86d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 23 Oct 2008 12:49:39 +0200 Subject: [PATCH] Dinicuv algoritmus: Oprava preklepu. --- 2-dinic/2-dinic.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 992a858..2d64e58 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -3,7 +3,7 @@ \prednaska{2}{Dinicùv algoritmus a jeho varianty}{} Maximální tok v~síti u¾ umíme najít pomocí Ford-Fulkersonova algoritmu -z~minulé kapitoly. Nyní pojednáme pojednáme o~efektivnìj¹ím Dinicovì algoritmu +z~minulé kapitoly. Nyní pojednáme o~efektivnìj¹ím Dinicovì algoritmu a o~rùzných jeho variantách pro sítì ve~speciálním tvaru. \h{Dinicùv algoritmus} @@ -122,7 +122,7 @@ proto podrobn ¾e èasto pracuje pøekvapivì efektivnì. \s{Jednotkové kapacity:} -Pokud sí» neobsahuje cykly délky~1 (dvojice navzájem opaèných hran), v¹echny rezervy +Pokud sí» neobsahuje cykly délky~2 (dvojice navzájem opaèných hran), v¹echny rezervy jsou jen 0 nebo~1. Pokud obsahuje, mohou rezervy být i dvojky, a~proto sí» upravíme tak, ¾e ke~ka¾dé hranì pøidáme hranu opaènou s~nulovou kapacitou a rezervu proti smìru toku pøiøkneme jí. Vzniknou tím sice paralelní hrany, ale to tokovým algoritmùm -- 2.39.2