Kostra pro setridene hrany: Precislovavame na 1...m (preklep).

[ga.git] / 6-borjar / 6-borjar.tex

diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex
index b13e5dbfdcad1f63b0f8fe3b73d301dba0567929..4df7a17fb4710a3d2b630b43d7277b6f75db99fa 100644 (file)
--- a/6-borjar/6-borjar.tex
+++ b/6-borjar/6-borjar.tex
@@ -158,7 +158,8 @@ jsme novou podkostru k~n
 \endalgo
 
 \s{Pozorování:}
-Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami.
+Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami
+(do toho poèítáme i vnitøní hrany vedoucí mezi vrcholy podkostry).
 Jak to vypadá pro jednotlivá ukonèení:
 \numlist\ndotted
 \itemcount=\algcnt
@@ -199,7 +200,7 @@ omezen
 \:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) \cite{fw90trans} -- uká¾eme v~jedné
   z~následujících kapitol.
 \:$\O(m)$, pokud u¾ máme hrany setøídìné podle vah: jeliko¾ víme, ¾e zále¾í jen na~uspoøádání,
-  mù¾eme váhy pøeèíslovat na~$1\ldots n$ a pou¾ít pøedchozí algoritmus.
+  mù¾eme váhy pøeèíslovat na~$1\ldots m$ a pou¾ít pøedchozí algoritmus.
 \:$\O(m)$ randomizovanì v~prùmìrném pøípadì \cite{karger:randomized}.
 \:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
   lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí