From 50f0a83c21c35c37e0a4e6be27b6d5471c3785e2 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 13 Jan 2013 00:15:30 +0100 Subject: [PATCH] Toky: "m" je rezervovano pro pocet hran S diky Davidovi Pegrimkovi za upozorneni. --- 1-toky/1-toky.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index dd3543a..07e3497 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -107,12 +107,12 @@ v~na \algo \:$f \leftarrow \$. \:Dokud existuje zlep¹ující cesta $P$ z~$s$ do~$t$: -\::$m \leftarrow \min_{e\in P} r(e)$. -\::Zvìt¹íme tok $f$ podél~$P$ o~$m$ (ka¾dé hranì $e\in P$ zvìt¹íme $f(e)$, pøípadnì zmen¹íme $f(e^\prime)$, podle toho, co jde). +\::$\varepsilon \leftarrow \min_{e\in P} r(e)$. +\::Zvìt¹íme tok $f$ podél~$P$ o~$\varepsilon$ (ka¾dé hranì $e\in P$ zvìt¹íme $f(e)$, pøípadnì zmen¹íme $f(e^\prime)$, podle toho, co jde). \endalgo \s{Analýza:} Nejdøíve si rozmysleme, ¾e pro celoèíselné kapacity algoritmus v¾dy dobìhne: v~ka¾dém kroku -stoupne velikost toku o~$m \ge 1$, co¾ mù¾e nastat pouze koneènì-krát. Podobnì pro racionální kapacity: +stoupne velikost toku o~$\varepsilon \ge 1$, co¾ mù¾e nastat pouze koneènì-krát. Podobnì pro racionální kapacity: pøenásobíme-li v¹echny kapacity jejich spoleèným jmenovatelem, dostaneme sí» s~celoèíselnými kapacitami, na~které se bude algoritmus chovat identicky a jak ji¾ víme, skonèí. Pro~iracionální kapacity obecnì dobìhnout nemusí, zkuste vymyslet protipøíklad. -- 2.39.2