From 50259d853d8a8cb4c78f42a8178219803cfd4e85 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Thu, 22 Feb 2007 15:08:06 +0100
Subject: [PATCH] Pridana zminka o stridavych cestach a Hopcroft-Tarjanove
 algoritmu.

---
 1-toky/1-toky.tex   | 11 +++++++++++
 2-dinic/2-dinic.tex |  8 ++++++++
 ga.bib              | 10 ++++++++++
 3 files changed, 29 insertions(+)

diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex
index 83db9d2..916bd4f 100644
--- a/1-toky/1-toky.tex
+++ b/1-toky/1-toky.tex
@@ -248,4 +248,15 @@ pou
 stejné velikosti.
 \qed
 
+Nìkteré algoritmy na~hledání maximálního párování vyu¾ívají také volné støídavé cesty:
+
+\s{Definice:} {\I (Volná) støídavá cesta} v~grafu $G$ s~párováním~$M$ je cesta, která
+zaèíná i konèí nespárovaným vrcholem a støídají se na~ní hrany le¾ící v~$M$ s~hranami
+mimo párování.
+
+V¹imnìte si, ¾e pro bipartitní grafy odpovídají zlep¹ující cesty v~pøíslu¹né síti
+právì volným støídavým cestám a zlep¹ení toku podél cesty odpovídá pøexorováním
+párování volnou støídavou cestou. Ford-Fulkersonùv algoritmus tedy lze velice
+snadno formulovat i v~øeèi støídavých cest.
+
 \bye
diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex
index 11c8da4..cc92d9d 100644
--- a/2-dinic/2-dinic.tex
+++ b/2-dinic/2-dinic.tex
@@ -182,6 +182,14 @@ Algoritmu zb
 Nyní staèí zvolit $k = \sqrt{n}$ a slo¾itost
 celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$.
 
+Mimochodem, hledání maximálního párování pomocí Dinicova algoritmu je také ekvivalentní
+známému Hopcroft-Karpovì algoritmu \cite{hopcroft:matching}. Ten je zalo¾en na~støídavých
+cestách z~pøedchozí kapitoly a v~ka¾dé iteraci nalezne mno¾inu vrcholovì disjuktních
+nejkrat¹ích støidavých cest, která je maximální vzhledem k~inkluzi.
+Touto mno¾inou pak aktuální párování pøexoruje, èím¾ ho zvìt¹í. V¹imnìte si, ¾e tyto
+mno¾iny cest odpovídají právì blokujícím tokùm v~proèi¹tìné síti rezerv, tak¾e mù¾eme
+i~zde pou¾ít ná¹ odhad na~poèet iterací.
+
 \s{Tøetí pokus pro jednotkové kapacity bez omezení na stupnì vrcholù v síti:}
 Hlavní my¹lenkou je opìt po $k$ krocích najít nìjaký malý øez. Najdeme dvì malé
 sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.
diff --git a/ga.bib b/ga.bib
index 6012746..10f0a34 100644
--- a/ga.bib
+++ b/ga.bib
@@ -481,3 +481,13 @@
   year={1975},
   publisher={ACM Press New York, NY, USA}
 }
+
+@article{ hopcroft:matching,
+  title={{An 2 5 n algorithm for maximum matchings in bipartite graphs}},
+  author={Hopcroft, J.E. and Karp, R.M.},
+  journal={SIAM Journal on Computing},
+  volume={2},
+  number={4},
+  pages={225--231},
+  year={1973}
+}
-- 
2.39.2