From 7bcbe88621fff3b6e5d61934d7490e186c0e67fc Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Thu, 26 Oct 2017 09:38:50 +0200
Subject: [PATCH] Randcut: Uvaha o smyckach

---
 12-randcut/12-randcut.tex | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/12-randcut/12-randcut.tex b/12-randcut/12-randcut.tex
index feb2c91..f6f53ce 100644
--- a/12-randcut/12-randcut.tex
+++ b/12-randcut/12-randcut.tex
@@ -13,7 +13,8 @@ pomocí toků nebo $\O(nm)$ Nagamochiho-Ibarakiho algoritmem.
 \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 hodnotu~$\ell$.
+hrany a kontrahuje je, dokud počet vrcholů neklesne na~$\ell$.
+(Konkrétní hodnotu~$\ell$ zvolíme později.)
 
 \s{Algoritmus} $\hbox{\sc Contract}(G_0,\ell)$:
 \algo
@@ -52,6 +53,12 @@ p     &\ge \prod_{i=1}^{n-\ell} \left( 1 - {2\over n-i+1} \right)
        = {\ell\cdot(\ell-1) \over n\cdot(n-1)}. \cr
 }$$
 
+Ještě musíme ošetřit případ, kdy bychom hranu řezu smazali, protože se mezitím
+stala smyčkou. Ovšem smyčky vznikají pouze z~hran paralelních s~právě kontrahovanou
+hranou. Jelikož v~libovolném svazku paralelních hran buďto všechny leží v~$C$,
+nebo ani jedna neleží, museli jsme v~takovém případě řez~$C$ rozbít už dříve.
+Odhad pravděpodobnosti to tedy neovlivní.
+
 Můžeme tedy zvolit pevně~$\ell$, spustit na~zadaný graf proceduru {\sc Contract}
 a ve~vzniklém konstantně velkém grafu pak nalézt minimální řez hrubou silou
 (to je obzvláště snadné pro $\ell=2$ -- tehdy stačí vzít všechny zbylé hrany).
-- 
2.39.5