Drobnosti.

[ga.git] / 3-bipcon / 3-bipcon.tex

diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex
index 3dba149ca909ba8c117abf7ff443ecf74f931f15..dac92709cccaf84e37a17d3ab903b87b262b3f01 100644 (file)
--- a/3-bipcon/3-bipcon.tex
+++ b/3-bipcon/3-bipcon.tex
@@ -7,6 +7,10 @@
 
 \prednaska{3}{Bipartitní párování a globální k-souvislost}{zapsali Jiøí Peinlich, Michal Kùrka}
 
+\>V~minulé kapitole jsme se zabývali aplikacemi tokù na~hledání maximálního párování
+a minimálního øezu. V~této 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}
 
 Nejprve si nadefinujme operaci {\I Degree Split,} která dostane jako vstup libovolný
@@ -52,7 +56,7 @@ nebude ani obsahovat n
 
 Slo¾itost algoritmu je $\O(m \log n)$, jeliko¾ provádíme inicializaci v~$\O(m)$ a celkem $\log_2 kn=\O(\log n)$ iterací po~$\O(m)$.
 
-\h{Algoritmy na zji¹tìní stupnì globální k-souvislosti}
+\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)$.
@@ -69,9 +73,9 @@ pamatovat, kolik vrchol
 vrcholù vìt¹í ne¾ nejmen¹í separátor, tak u¾ jsme jistì na¹li jeden z minimálních øezù. Slo¾itost takového algoritmu pak
 bude $\O(\kappa (G) n^{3/2} m)$, kde $\kappa(G)$ je stupeò souvislosti $G$, který hledáme.
 
-Pro minimální øezy v~neorientovaných grafech ov¹em existuje rychlej¹í algoritmus, který toky nepou¾ívá.
+Pro minimální øezy v~neorientovaných grafech ov¹em existuje následující rychlej¹í algoritmus:
 
-\h{Algoritmus Namagochiho a Ibarakiho}
+\h{Globálnì minimální øez (Nagamochi, Ibaraki)}
 
 Buï $G$ neorientovaný graf s~ohodnocením na~hranách. Oznaèíme si: