From dee8a7afcbe0a06d835246f8e7e768da54429771 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 27 Oct 2014 19:45:45 +0100 Subject: [PATCH] =?utf8?q?Karger-Stain:=20Dv=C4=9B=20drobn=C3=A9=20chybky?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 12-randcut/12-randcut.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/12-randcut/12-randcut.tex b/12-randcut/12-randcut.tex index de98dd4..ce522b8 100644 --- a/12-randcut/12-randcut.tex +++ b/12-randcut/12-randcut.tex @@ -13,7 +13,7 @@ pomoc \h{Náhodné kontrakce} Uva¾ujme nejdøíve následující algoritmus, který náhodnì vybírá -hrany a kontrahuje je, dokud poèet vrcholù neklesne na~danou konstantu~$\ell$. +hrany a kontrahuje je, dokud poèet vrcholù neklesne na~danou hodnotu~$\ell$. \s{Algoritmus} $\hbox{\sc Contract}(G_0,\ell)$: \algo @@ -42,7 +42,7 @@ Ozna vrcholù a hran. Zøejmì $n_i=n-i+1$ (ka¾dou kontrakcí pøijdeme o~jeden vrchol). Navíc ka¾dý vrchol má stupeò alespoò~$k$, jeliko¾ jinak by triviální øez okolo tohoto vrcholu byl men¹í ne¾ minimální øez. Proto platí $m_i \ge kn_i/2$. Hranu -le¾ící v~øezu~$C$ tedy vybereme s~pravdìpodobností $k/m_i \le k/(kn_i/2) = 2/n_i +le¾ící v~øezu~$C$ tedy vybereme s~pravdìpodobností nejvý¹e $k/m_i \le k/(kn_i/2) = 2/n_i = 2/(n-i+1)$. V¹echny hrany z~øezu~$C$ proto postoupí do výsledného grafu~$G$ s~pravdìpodobností $$\eqalign{ -- 2.39.5