From 1295b412f5e63fbb0f7373dd28a8f0e95a824993 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 23 Oct 2008 13:14:25 +0200 Subject: [PATCH] Kosmetika: Ford-Fulkersonuv -> Forduv-Fulkersonuv --- 0-intro/0-intro.tex | 2 +- 1-toky/1-toky.tex | 14 +++++++------- 2-dinic/2-dinic.tex | 4 ++-- 3 files changed, 10 insertions(+), 10 deletions(-) diff --git a/0-intro/0-intro.tex b/0-intro/0-intro.tex index a59a179..908b594 100644 --- a/0-intro/0-intro.tex +++ b/0-intro/0-intro.tex @@ -20,7 +20,7 @@ M na~jaøe 2006 první verzi této pøedná¹ky uvádìl, za~výbornì zpracované zápisky, je¾ se staly prazákladem tohoto textu. Jmenovitì: $$\vbox{\halign{\it #\hfil\cr -Toky, øezy a Ford-Fulkersonùv algoritmus: Radovan ©esták \cr +Toky, øezy a Fordùv-Fulkersonùv algoritmus: Radovan ©esták \cr Dinicùv algoritmus: Bernard Lidický \cr Globální souvislost a párování: Jiøí Peinlich a Michal Kùrka \cr Gomory-Hu Trees: Milan Straka \cr diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index d88199a..dd3543a 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -1,9 +1,9 @@ \input ../sgr.tex -\prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{} +\prednaska{1}{Toky, øezy a Fordùv-Fulkersonùv algoritmus}{} V~této kapitole nadefinujeme toky v~sítích, odvodíme základní vìty o~nich -a také Ford-Fulkersonùv algoritmus pro hledání maximálního toku. Také uká¾eme, +a také Fordùv-Fulkersonùv algoritmus pro hledání maximálního toku. Také uká¾eme, jak na~hledání maximálního toku pøevést problémy týkající se øezù, separátorù a párování v~bipartitních grafech. Dal¹í tokové algoritmy budou následovat v~pøí¹tích kapitolách. @@ -58,7 +58,7 @@ velikosti) a {\I minim pro toky v~sítích s~reálnými kapacitami to ov¹em není samozøejmost a je k~tomu potøeba trocha matematické analýzy (v~prostoru v¹ech ohodnocení hran tvoøí toky kompaktní mno¾inu, velikost toku je lineární funkce, a~tedy i spojitá, proèe¾ nabývá maxima). Pro racionální kapacity dostaneme tuto vìtièku jako dùsledek -analýzy Ford-Fulkersonova algoritmu. +analýzy Fordova-Fulkersonova algoritmu. \qed \s{Pozorování:} Kdybychom velikost toku definovali podle spotøebièe, vy¹lo by toté¾. Platí toti¾: @@ -82,10 +82,10 @@ n \proof Jednu nerovnost jsme dokázali v~pøedchozím lemmatu, druhá plyne z~duality lineárního programování [max. tok a min. øez jsou navzájem duální úlohy], ale k~pìknému kombinatorickému -dùkazu pùjde opìt pou¾ít Ford-Fulkersonùv algoritmus. +dùkazu pùjde opìt pou¾ít Fordùv-Fulkersonùv algoritmus. \qed -\h{Ford-Fulkersonùv algoritmus} +\h{Fordùv-Fulkersonùv algoritmus} Nejpøímoèaøej¹í zpùsob, jak bychom mohli hledat toky v~sítích, je zaèít s~nìjakým tokem (nulový je po~ruce v¾dy) a postupnì ho zlep¹ovat tak, ¾e nalezneme nìjakou nenasycenou cestu a po¹leme po~ní \uv{co pùjde}. @@ -124,7 +124,7 @@ b nulová. Tak¾e $f^-(C) = \vert C \vert$ a $f^+(C) = 0$, èili $\vert f\vert = \vert C \vert$. Na¹li jsme tedy k~toku, který algoritmus vydal, øez stejné velikosti, a~proto, jak u¾ víme, -je tok maximální a øez minimální. Tím jsme také dokázali Ford-Fulkersonovu vìtu\foot{Dokonce +je tok maximální a øez minimální. Tím jsme také dokázali Fordovu-Fulkersonovu vìtu\foot{Dokonce jsme ji dokázali i pro reálné kapacity, proto¾e mù¾eme algoritmus spustit rovnou na maximální tok místo nulového a on se ihned zastaví a vydá certifikující øez.} a existenci maximálního toku. Navíc algoritmus nikdy nevytváøí z~celých èísel necelá, èím¾ získáme: @@ -256,7 +256,7 @@ mimo p V¹imnìte si, ¾e pro bipartitní grafy odpovídají zlep¹ující cesty v~pøíslu¹né síti právì volným støídavým cestám a zlep¹ení toku podél cesty odpovídá pøexorováním -párování volnou støídavou cestou. Ford-Fulkersonùv algoritmus tedy lze velice +párování volnou støídavou cestou. Fordùv-Fulkersonùv algoritmus tedy lze velice snadno formulovat i v~øeèi støídavých cest. \bye diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 2d64e58..fc8c548 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -2,13 +2,13 @@ \prednaska{2}{Dinicùv algoritmus a jeho varianty}{} -Maximální tok v~síti u¾ umíme najít pomocí Ford-Fulkersonova algoritmu +Maximální tok v~síti u¾ umíme najít pomocí Fordova-Fulkersonova 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} -Dinicùv algoritmus je zalo¾en na~následující my¹lence: Ve~Ford-Fulkersonovì algoritmu +Dinicùv algoritmus je zalo¾en na~následující my¹lence: Ve~Fordovì-Fulkersonovì algoritmu nemusíme pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující toky. Nejlépe toky takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok dostateènì obohatily. Vhodnými objekty k~tomuto úèelu jsou blokující toky: -- 2.39.2