Drobnosti.

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

diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex
index 30cc044e56e0d57b273c29922d92e51539aafaf8..dac92709cccaf84e37a17d3ab903b87b262b3f01 100644 (file)
--- a/3-bipcon/3-bipcon.tex
+++ b/3-bipcon/3-bipcon.tex
@@ -7,7 +7,7 @@
 
 \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í
+\>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ù.
 
@@ -56,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)$.
@@ -73,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: