From 25722f257d6a65e76999ccd244c12baa9876a646 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 13 Mar 2007 15:15:54 +0100 Subject: [PATCH] Drobne upravy sazby. --- 11-planar/11-planar.tex | 1 + 5-mst/5-mst.tex | 2 +- 9-decomp/9-decomp.tex | 1 + 3 files changed, 3 insertions(+), 1 deletion(-) diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 307940f..d95bfc9 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -94,6 +94,7 @@ le rovinnost. \finalfix{ +\smallskip \figure{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize} \figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize} } diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 8c27cf3..dab140b 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -214,7 +214,7 @@ jedn je maximální na~nìjakém cyklu tvoøeném touto hranou a nìjakými døíve pøidanými. Potøebujeme èas $\O(m \log n)$ na~setøídìní hran a dále datovou strukturu pro udr¾ování komponent souvislosti -(Union-Find Problem), se~kterou provedeme $m$ operací \ a $n$ operací \. Nejlep¹í známá implementace +(Union-Find Problem), se~kterou provedeme $m$~operací \ a $n$ operací \. Nejlep¹í známá implementace této struktury dává slo¾itost obou operací $\O(\alpha(n))$ amortizovanì, tak¾e celkovì hladový algoritmus dobìhne v~èase $\O(m \log n + m \alpha(n))$. diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex index 38f4aea..e769400 100644 --- a/9-decomp/9-decomp.tex +++ b/9-decomp/9-decomp.tex @@ -137,6 +137,7 @@ ji nahrad ¾e $\log n=4$. Vrcholy mikrostromù jsou èerné, makrostromu bílé. Spojovací hrany kreslíme teèkovanì, hrany komprimovaných cest tuènì. +\medskip \fig{mima.eps}{\epsfxsize} \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si ulo¾íme -- 2.39.5