X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=3-bipcon%2F3-bipcon.tex;h=362bd7b75a79cb904c7c8009f4040da281cb03ca;hb=b2484e9e3f714201f2c3543a2a265d015e6e5915;hp=2b41a5416bef5b66de1f906e0aa5c17374632149;hpb=9caf01a8298a65d9ff4e7e40c9dd61cb6fb60c1d;p=ga.git

diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex
index 2b41a54..362bd7b 100644
--- a/3-bipcon/3-bipcon.tex
+++ b/3-bipcon/3-bipcon.tex
@@ -1,118 +1,120 @@
 \input ../sgr.tex
 
-\prednaska{3}{Bipartitní párování a globální k-souvislost}{}
-
-V~pøede¹lých kapitolách jsme se zabývali aplikacemi tokù na~hledání maximálního párování
-a minimálního $st$-øezu. Nyní si pøedvedeme dva algoritmy pro podobné problémy,
-které se obejdou bez tokù.
-
-\h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}}
-
-Nejprve si nadefinujme operaci {\I ¹tìpení grafu,} která zadaný graf $G=(V,E)$
-se v¹emi vrcholy sudého stupnì a sudým poètem hran v~ka¾dé komponentì souvilosti
-rozlo¾í na~disjunktní podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$,
-v~nich¾ bude pro ka¾dý vrchol~$v$ platit ${\rm deg}_{G_1}(v) = {\rm
-deg}_{G_2}(v) = {\rm deg}_G(v)/2$. Tuto operaci mù¾eme snadno
-provést v~lineárním èase tak, ¾e si graf rozdìlíme na~komponenty, v~ka¾dé
-nalezneme eulerovský tah a jeho hrany budeme pøidávat støídavì do~$G_1$ a do~$G_2$.
-
-©tìpení nám pomù¾e ke~snadnému algoritmu pro nalezení maximálního párování ve~$2^t$-regulárním
-bipartitním grafu.\foot{V¹imnìte si, ¾e takové párování bude v¾dy perfektní (viz Hallova vìta).}
-Komponenty takového grafu mají urèitì sudý poèet hran, tak¾e jej mù¾eme
-roz¹tìpit na~dva $2^{t-1}$-regulární grafy. Libovolný jeden z~nich pak opìt roz¹tìpíme
-atd., a¾ dostaneme $1$-regulární graf, který je perfektním párováním v~$G$.
-To v¹e jsme schopni stihnout v~lineárním èase, jeliko¾ velikosti grafù, které
-¹tìpíme, exponenciálnì klesají. Také bychom mohli rekurzivnì zpracovávat obì
-èásti a tak se v~èase $\O(m\log n)$ dobrat ke~kompletní 1-faktorizaci
-zadaného grafu.\foot{To je rozklad hran grafu na~disjunktní perfektní párování
-a má ho ka¾dý regulární bipartitní graf.}
-
-Pokud zadaný graf nebude $2^t$-regulární, pomù¾eme si tím, ¾e ho novými hranami
-doplníme na $2^t$-regulární a pak si pøi ¹tìpeních budeme vybírat ten podgraf,
-do~kterého padlo ménì nových hran, a uká¾eme, ¾e nakonec v¹echny zmizí.
-Abychom graf pøíli¹ nezvìt¹ili, budeme se sna¾it místo pøidávání úplnì nových
-hran pouze zvy¹ovat násobnost hran existujících. Pro ka¾dou hranu $e$ si tedy
-budeme pamatovat její násobnost $n(e)$.
-
-{\I ©tìpení grafu s~násobnostmi} pak budeme provádìt následovnì: hranu~$e$
-s~násobností $n(e)$ umístíme do~$G_1$ i~do~$G_2$ s~násobností $\lfloor n(e)/2
-\rfloor$ a pokud bylo $n(e)$ liché, pøidáme hranu do~pomocného grafu
-$G^\prime$. V¹imnìte si, ¾e $G^\prime$ bude graf bez násobností, v~nìm¾ mají
-v¹echny vrcholy sudý stupeò, tak¾e na~nìj mù¾eme aplikovat pùvodní ¹tìpící algoritmus
-a $G^\prime_i$ pøiøadit ke~$G_i$. To~v¹e zvládneme v~èase $\O(m)$.
-
-Mìjme nyní $k$-regulární bipartitní graf. Obì jeho partity jsou stejnì velké,
-oznaème si poèet vrcholù v~ka¾dé z~nich~$n$. Zvolme $t$ tak aby $2^t\geq kn$.
-Zvolme dále parametry
+\prednaska{3}{Bipartitní párování a globální k-souvislost}{}
+
+V~předešlých kapitolách jsme se zabývali aplikacemi toků na~hledání maximálního párování
+a minimálního $st$-řezu. Nyní si předvedeme dva algoritmy pro podobné problémy,
+které se obejdou bez toků.
+
+\h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}}
+
+Nejprve si nadefinujme operaci {\I štěpení grafu,} která zadaný graf $G=(V,E)$
+se všemi vrcholy sudého stupně a sudým počtem hran v~každé komponentě souvislosti
+rozloží na~disjunktní podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$,
+v~nichž bude pro každý vrchol~$v$ platit ${\rm deg}_{G_1}(v) = {\rm
+deg}_{G_2}(v) = {\rm deg}_G(v)/2$. Tuto operaci můžeme snadno
+provést v~lineárním čase tak, že si graf rozdělíme na~komponenty, v~každé
+nalezneme eulerovský tah a jeho hrany budeme přidávat střídavě do~$G_1$ a do~$G_2$.
+
+Štěpení nám pomůže ke~snadnému algoritmu pro nalezení maximálního párování ve~$2^t$-regulárním
+bipartitním grafu.\foot{Všimněte si, že takové párování bude vždy perfektní (viz Hallova věta).}
+Komponenty takového grafu mají určitě sudý počet hran, takže jej můžeme
+rozštěpit na~dva $2^{t-1}$-regulární grafy. Libovolný jeden z~nich pak opět rozštěpíme
+atd., až dostaneme $1$-regulární graf, který je perfektním párováním v~$G$.
+To vše jsme schopni stihnout v~lineárním čase, jelikož velikosti grafů, které
+štěpíme, exponenciálně klesají. Také bychom mohli rekurzivně zpracovávat obě
+části a tak se v~čase $\O(m\log n)$ dobrat ke~kompletní 1-faktorizaci
+zadaného grafu.\foot{To je rozklad hran grafu na~disjunktní perfektní párování
+a má ho každý regulární bipartitní graf.}
+
+Pokud zadaný graf nebude $2^t$-regulární, pomůžeme si tím, že ho novými hranami
+doplníme na $2^t$-regulární a pak si při štěpeních budeme vybírat ten podgraf,
+do~kterého padlo méně nových hran, a ukážeme, že nakonec všechny zmizí.
+Abychom graf příliš nezvětšili, budeme se snažit místo přidávání úplně nových
+hran pouze zvyšovat násobnost hran existujících. Pro každou hranu $e$ si tedy
+budeme pamatovat její násobnost $n(e)$.
+
+{\I Štěpení grafu s~násobnostmi} pak budeme provádět následovně: hranu~$e$
+s~násobností $n(e)$ umístíme do~$G_1$ i~do~$G_2$ s~násobností $\lfloor n(e)/2
+\rfloor$ a pokud bylo $n(e)$ liché, přidáme hranu do~pomocného grafu
+$G^\prime$. Všimněte si, že $G^\prime$ bude graf bez násobností, v~němž mají
+všechny vrcholy sudý stupeň, takže na~něj můžeme aplikovat původní štěpící algoritmus
+a $G^\prime_i$ přiřadit ke~$G_i$. To~vše zvládneme v~čase $\O(m)$.
+
+Mějme nyní $k$-regulární bipartitní graf. Obě jeho partity jsou stejně velké,
+označme si počet vrcholů v~každé z~nich~$n$. Zvolme $t$ tak aby $2^t\geq kn$.
+Zvolme dále parametry
 $\alpha := \lfloor 2^t/k \rfloor$ a
 $\beta := 2^t \bmod k$.
-Ka¾dé pùvodní hranì nastavíme násobnost~$\alpha$ a pøidáme triviální párování~$F$
-($i$-tý vrchol vlevo se spojí s~$i$-tým vrcholem vpravo) s~násobností~$\beta$.
-V¹imnìte si, ¾e $\beta<k$, a~proto hran v~$F$ (vèetnì násobností) bude ménì ne¾ $2^t$.
+Každé původní hraně nastavíme násobnost~$\alpha$ a přidáme triviální párování~$F$
+($i$-tý vrchol vlevo se spojí s~$i$-tým vrcholem vpravo) s~násobností~$\beta$.
+Všimněte si, že $\beta<k$, a~proto hran v~$F$ (včetně násobností) bude méně než $2^t$.
 
-Takto získáme $2^t$-regulární graf, jeho¾ reprezentace bude lineárnì velká. Na tento graf budeme aplikovat operaci
-¹tìpení a budeme si vybírat v¾dy tu polovinu, kde bude ménì hran z~$F$. Po~$t$ iteracích dospìjeme k~párování
-a jeliko¾ se~v~ka¾dém kroku zbavíme alespoò poloviny hran z~$F$, nebude toto párování obsahovat ¾ádnou takovou hranu
-a navíc nebude obsahovat ani násobné hrany, tak¾e bude podgrafem zadaného grafu, jak potøebujeme.
+Takto získáme $2^t$-regulární graf, jehož reprezentace bude lineárně velká. Na tento graf budeme aplikovat operaci
+štěpení a budeme si vybírat vždy tu polovinu, kde bude méně hran z~$F$. Po~$t$ iteracích dospějeme k~párování
+a jelikož se~v~každém kroku zbavíme alespoň poloviny hran z~$F$, nebude toto párování obsahovat žádnou takovou hranu
+a navíc nebude obsahovat ani násobné hrany, takže bude podgrafem zadaného grafu, jak potřebujeme.
 
-Èasová slo¾itost algoritmu je $\O(m \log n)$, jeliko¾ provádíme inicializaci v~èase
-$\O(m)$ a celkem $\log_2 kn=\O(\log n)$ iterací po~$\O(m)$.
+Časová složitost algoritmu je $\O(m \log n)$, jelikož provádíme inicializaci v~čase
+$\O(m)$ a celkem $\log_2 kn=\O(\log n)$ iterací po~$\O(m)$.
 
-\h{Stupeò souvislosti grafu}
+\h{Stupeň souvislosti grafu}
 
-Problém zji¹tìní {\I stupnì hranové souvislosti} grafu lze pøevést na problém hledání minimálního øezu,
-který ji¾ pro zadanou dvojici vrcholù umíme øe¹it pomocí Dinicova algoritmu v~èase $\O(n^{2/3}m)$.
-Pokud chceme najít minimum ze~v¹ech øezù v~grafu, mù¾eme vyzkou¹et v¹echny dvojice $(s,t)$.
-To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z~vrcholù (tøeba $s$) mù¾eme zvolit
-pevnì: vezmeme-li libovolný øez $C$, pak jistì najdeme alespoò jedno~$t$, které padne
-do~jiné komponenty ne¾ pevnì zvolené~$s$, tak¾e minimální $st$-øez bude nejvý¹e tak velký jako~$C$.
-V~orientovaném grafu musíme projít jak øezy pro $s \rightarrow t$, tak i $t \rightarrow s$.
-Algoritmus bude mít slo¾itost $\O(n^{{5/3}}m)$.
+Problém zjištění {\I stupně hranové souvislosti} grafu lze převést na problém hledání minimálního řezu,
+který již pro zadanou dvojici vrcholů umíme řešit pomocí Dinicova algoritmu v~čase $\O(n^{2/3}m)$.
+Pokud chceme najít minimum ze~všech řezů v~grafu, můžeme vyzkoušet všechny dvojice $(s,t)$.
+To však lze snadno zrychlit, pokud si uvědomíme, že jeden z~vrcholů (třeba $s$) můžeme zvolit
+pevně: vezmeme-li libovolný řez $C$, pak jistě najdeme alespoň jedno~$t$, které padne
+do~jiné komponenty než pevně zvolené~$s$, takže minimální $st$-řez bude nejvýše tak velký jako~$C$.
+V~orientovaném grafu musíme projít jak řezy pro $s \rightarrow t$, tak i $t \rightarrow s$.
+Algoritmus bude mít složitost $\O(n^{{5/3}}m)$.
 
-U~{\I vrcholové $k$-souvislosti} to ov¹em tak snadno nepùjde. Pokud by toti¾ fixovaný vrchol byl souèástí nìjakého
-minimálního separátoru, algoritmus mù¾e selhat. Pøesto ale nemusíme procházet v¹echny dvojice vrcholù. Staèí jako
-$s$ postupnì zvolit více vrcholù, ne¾ je velikost minimálního separátoru. Algoritmus si tedy bude pamatovat, kolik
-vrcholù u¾ pro¹el a nejmen¹í zatím nalezený $st$-separátor, a jakmile poèet vrcholù pøekroèí velikost separátoru,
-prohlásí separátor za~minimální. To zvládne v~èase $\O(\kappa (G) \cdot n^{3/2} m)$, kde $\kappa(G)$ je nalezený stupeò souvislosti~$G$.
+U~{\I vrcholové $k$-souvislosti} to ovšem tak snadno nepůjde. Pokud by totiž fixovaný vrchol byl součástí nějakého
+minimálního separátoru, algoritmus může selhat. Přesto ale nemusíme procházet všechny dvojice vrcholů. Stačí jako
+$s$ postupně zvolit více vrcholů, než je velikost minimálního separátoru. Algoritmus si tedy bude pamatovat, kolik
+vrcholů už prošel a nejmenší zatím nalezený $st$-separátor, a jakmile počet vrcholů překročí velikost separátoru,
+prohlásí separátor za~minimální. To zvládne v~čase $\O(\kappa (G) \cdot n^{3/2} m)$, kde $\kappa(G)$ je nalezený stupeň souvislosti~$G$.
 
-Pro minimální øezy v~neorientovaných grafech ov¹em existuje následující rychlej¹í algoritmus:
+Pro minimální řezy v~neorientovaných grafech ovšem existuje následující rychlejší algoritmus:
 
-\h{Globálnì minimální øez (Nagamochi, Ibaraki \cite{nagaiba:conn})}
+\h{Globálně minimální řez (Nagamochi, Ibaraki \cite{nagaiba:conn})}
 
-Buï $G$ neorientovaný multigraf s~nezáporným ohodnocením hran. Oznaèíme si:
+Buď $G$ neorientovaný multigraf s~nezáporným ohodnocením hran. Označíme si:
 
-\s{Znaèení:}
+\s{Značení:}
 
 \itemize\ibull
-\:$r(u,v)$ buï kapacita minimálního $uv$-øezu,
-\:$d(P,Q)$ buï kapacita hran vedoucích mezi mno¾inami $P,Q \subseteq V$,
-\:$d(P) = d(P,\overline P)$ buï kapacita hran vedoucích mezi $P\subseteq V$ a zbytkem grafu,
-\:$d(v) = d(\{v\})$ buï kapacita hran vedoucích z~$v$ (tedy pro neohodnocené grafy stupeò~$v$),
+\:$r(u,v)$ buď kapacita minimálního $uv$-řezu,
+\:$d(P,Q)$ buď kapacita hran vedoucích mezi množinami $P,Q \subseteq V$,
+\:$d(P) = d(P,\overline P)$ buď kapacita hran vedoucích mezi $P\subseteq V$ a zbytkem grafu,
+\:$d(v) = d(\{v\})$ buď kapacita hran vedoucích z~$v$ (tedy pro neohodnocené grafy stupeň~$v$),
 \:analogicky zavedeme $d(v,w)$ a $d(v,P)$.
 \endlist
 
 \s{Definice:}
-{\it Legálním uspoøádáním vrcholù} (LU) budeme nazývat lineární uspoøádání vrcholù $v_1 \ldots v_n$ takové, ¾e platí
-$d(\{v_1 \ldots v_{i-1}\},v_i) \geq d(\{v_1 \ldots v_{i-1}\},v_j)$ pro ka¾dé $1 \leq i<j\leq n$.
+{\it Legálním uspořádáním vrcholů} (LU) budeme nazývat lineární uspořádání vrcholů $v_1 \ldots v_n$ takové, že platí
+$d(\{v_1 \ldots v_{i-1}\},v_i) \geq d(\{v_1 \ldots v_{i-1}\},v_j)$ pro každé $1 \leq i<j\leq n$.
 
 \s{Lemma:} Je-li $v_1 \ldots v_n$ LU na $G$, pak $r(v_{n-1},v_n)=d(v_n)$.
 
-\proof Buï $C$ nìjaký øez oddìlující $v_{n-1}$ a $v_n$. Utvoøme posloupnost vrcholù $u_i$ takto:
+\proof Buď $C$ libovolný řez oddělující $v_{n-1}$ a $v_n$.
+Dokážeme, že jeho velikost je alespoň~$d(v_n)$.
+Utvořme posloupnost vrcholů $u_i$ takto:
 
 \algo
 \:$u_0 := v_1$
-\:$u_i := v_j$ tak, ¾e $j>i$, $v_i$ a $v_j$ jsou oddìleny øezem $C$ a $j$ je minimální takové.
-[Tedy $v_j$ je nejbli¾¹í vrchol na~druhé stranì øezu.]
+\:$u_i := v_j$ tak, že $j>i$, $v_i$ a $v_j$ jsou odděleny řezem $C$ a $j$ je minimální takové.
+[Tedy $v_j$ je nejbližší vrchol na~druhé straně řezu.]
 \endalgo
 
-Ka¾dé $u_{i-1}$ je tedy buï rovno $u_i$, pokud jsou $v_i$ a $v_{i-1}$ na stejné stranì øezu, nebo rovno $v_i$, pokud
-jsou $v_i$ a $v_{i-1}$ na~stranách opaèných. Z~toho dostáváme, ¾e $d(\{v_1\ldots v_{i-1}\},u_i)\leq d(\{v_1\ldots
-v_{i-1}\},u_{i-1})$, proto¾e buïto $u_i=u_{i-1}$, a pak je nerovnost splnìna jako rovnost, nebo je $u_i=v_j$, $j>i$ a
-nerovnost plyne z~legálnosti uspoøádání.
+Každé $u_{i-1}$ je tedy buď rovno $u_i$, pokud jsou $v_i$ a $v_{i-1}$ na stejné straně řezu, nebo rovno $v_i$, pokud
+jsou $v_i$ a $v_{i-1}$ na~stranách opačných. Z~toho dostáváme, že $d(\{v_1\ldots v_{i-1}\},u_i)\leq d(\{v_1\ldots
+v_{i-1}\},u_{i-1})$, protože buďto $u_{i-1}=u_i$, a pak je nerovnost splněna jako rovnost, nebo je $u_{i-1}=v_i$ a
+nerovnost plyne z~legálnosti uspořádání.
 
-Chceme ukázat, ¾e velikost na¹eho øezu~$C$ je alespoò taková, jako velikost øezu kolem vrcholu $v_n$.
-V¹imneme si, ¾e $\vert C \vert \geq \sum_{i=1}^{n-1} d(v_i,u_i)$. Hrany mezi $v_i$ a $u_i$ jsou toti¾ navzájem
-rùzné a ka¾dá z~nich je souèástí øezu~$C$. Uká¾eme, ¾e pravá strana je alespoò $d(v_n)$:
+Chceme ukázat, že velikost našeho řezu~$C$ je alespoň taková, jako velikost řezu kolem vrcholu $v_n$.
+Všimneme si, že $\vert C \vert \geq \sum_{i=1}^{n-1} d(v_i,u_i)$. Hrany mezi $v_i$ a $u_i$ jsou totiž navzájem
+různé a každá z~nich je součástí řezu~$C$. Ukážeme, že pravá strana je alespoň $d(v_n)$:
 $$\eqalign{
 \sum_{i=1}^{n-1} d(v_i,u_i) &= \sum_{i=1}^{n-1} d(\{v_1\ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_i) \geq \cr
 &\geq \sum_{i=1}^{n-1} d(\{v_1 \ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_{i-1}) = \cr
@@ -121,28 +123,28 @@ $$\eqalign{
 }$$
 \qed
 
-Dokázali jsme, ¾e libovolný øez separující $v_{n-1}$ a $v_n$ je alespoò tak velký jako jednoduchý øez skládající se jen z hran
-kolem~$v_n$. Kdy¾ tedy sestavíme nìjakou LU posloupnost vrcholù, budeme mít k dispozici jednoduchý minimální øez
-$v_{n-1}$ a~$v_n$. Následnì vytvoøíme graf $G'$, v nìm¾ $v_{n-1}$ a $v_n$ kontrahujeme. Rekurzivnì najdeme minimální
-øez v $G'$ (sestrojíme nové LU atd.). Hledaný minimální øez poté buïto oddìluje vrcholy $v_n$ a $v_{n-1}$, a potom je øez
-kolem vrcholu $v_n$ minimální, nebo vrcholy $v_n$ a $v_{n-1}$ neoddìluje, a v takovém pøípadì jej najdeme
-rekurzivnì. Hledaný øez je tedy men¹í z rekurzivnì nalezeného øezu a øezu kolem $v_n$.
-
-Zbývá ukázat, jak konstruovat LU. Postaèí hladovì: Pamatujeme si $\forall v\neq v_1 \ldots v_{i-1}$ hodnotu $d(\{v_1 \ldots v_{i-1}\},v)$, oznaème ji $z_v$. V ka¾dém kroku vybereme vrchol $v$ s maximální hodnotou $z_v$, prohlásíme ho za $v_i$ a pøepoèítáme~$z_v$.
-
-Zde se hodí datová struktura, která doká¾e rychle hledat maxima a zvy¹ovat hodnoty prvkù,
-napøíklad Fibonacciho halda. Ta zvládne \<DeleteMax> v~èase $\O(\log n)$ a \<Increase> v~$\O(1)$
-amortizovanì. Celkem pak ná¹ algoritmus bude mít slo¾itost $\O(n(m+n\log n))$ pro obecné kapacity.
-
-Pokud jsou kapacity malá celá èísla, mù¾eme vyu¾ít pøihrádkové struktury. Budeme
-si udr¾ovat obousmìrný seznam zatím pou¾itých hodnot $z_v$, ka¾dý prvek takového
-seznamu bude obsahovat v¹echny vrcholy se spoleènou hodnotou $z_v$. Kdy¾ budeme
-mít seznam seøazený, vybrání minimálního prvku bude znamenat pouze podívat se na
-první prvek seznamu a z nìj odebrat jeden vrchol, pøípadnì celý prvek ze seznamu
-odstranit. Operace \<Increase> poté bude reprezentovat pouze pøesunutí vrcholu o
-malý poèet pøihrádek, pøípadnì zalo¾ení nové pøihrádky na správném místì.
-\<DeleteMax> proto bude mít slo¾itost $\O(1)$, v¹echny \<Increase> dohromady $\O(m)$,
-jeliko¾ za~ka¾dou hranu pøeskakujeme maximálnì jednu pøihrádku, a celý algoritmus $\O(mn)$.
+Dokázali jsme, že libovolný řez separující $v_{n-1}$ a $v_n$ je alespoň tak velký jako jednoduchý řez skládající se jen z hran
+kolem~$v_n$. Když tedy sestavíme nějakou LU posloupnost vrcholů, budeme mít k dispozici jednoduchý minimální řez
+$v_{n-1}$ a~$v_n$. Následně vytvoříme graf $G'$, v němž $v_{n-1}$ a $v_n$ kontrahujeme. Rekurzivně najdeme minimální
+řez v $G'$ (sestrojíme nové LU atd.). Hledaný minimální řez poté buďto odděluje vrcholy $v_n$ a $v_{n-1}$, a potom je řez
+kolem vrcholu $v_n$ minimální, nebo vrcholy $v_n$ a $v_{n-1}$ neodděluje, a v takovém případě jej najdeme
+rekurzivně. Hledaný řez je tedy menší z rekurzivně nalezeného řezu a řezu kolem $v_n$.
+
+Zbývá ukázat, jak konstruovat LU. Postačí hladově: Pamatujeme si $\forall v\neq v_1 \ldots v_{i-1}$ hodnotu $d(\{v_1 \ldots v_{i-1}\},v)$, označme ji $z_v$. V každém kroku vybereme vrchol $v$ s maximální hodnotou $z_v$, prohlásíme ho za $v_i$ a přepočítáme~$z_v$.
+
+Zde se hodí datová struktura, která dokáže rychle hledat maxima a zvyšovat hodnoty prvků,
+například Fibonacciho halda. Ta zvládne \<DeleteMax> v~čase $\O(\log n)$ a \<Increase> v~$\O(1)$
+amortizovaně. Celkem pak náš algoritmus bude mít složitost $\O(n(m+n\log n))$ pro obecné kapacity.
+
+Pokud jsou kapacity malá celá čísla, můžeme využít přihrádkové struktury. Budeme
+si udržovat obousměrný seznam zatím použitých hodnot $z_v$, každý prvek takového
+seznamu bude obsahovat všechny vrcholy se společnou hodnotou $z_v$. Když budeme
+mít seznam seřazený, vybrání minimálního prvku bude znamenat pouze podívat se na
+první prvek seznamu a z něj odebrat jeden vrchol, případně celý prvek ze seznamu
+odstranit. Operace \<Increase> poté bude reprezentovat pouze přesunutí vrcholu o
+malý počet přihrádek, případně založení nové přihrádky na správném místě.
+\<DeleteMax> proto bude mít složitost $\O(1)$, všechny \<Increase> dohromady $\O(m)$,
+jelikož za~každou hranu přeskakujeme maximálně jednu přihrádku, a celý algoritmus $\O(mn)$.
 
 \references
 \bye