From 54cc78bb075fface0e93040801f496bf76e9f353 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 22 Jan 2007 18:36:39 +0100 Subject: [PATCH] Doplnen dukaz Koenigovy vety a rozsiren uvodni odstavec. --- 1-toky/1-toky.tex | 39 ++++++++++++++++++++++++--------------- 1 file changed, 24 insertions(+), 15 deletions(-) diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index eb7dae4..b88a7c1 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -3,9 +3,9 @@ \prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{} V~této kapitole nadefinujeme toky v~sítích, odvodíme základní vìty o~nich -a Ford-Fulkersonùv algoritmus pro hledání maximálního toku. Také uká¾eme, +a také Ford-Fulkersonùv algoritmus pro hledání maximálního toku. Také uká¾eme, jak na~hledání maximálního toku pøevést problémy týkající se øezù, separátorù -a párování. Dal¹í algoritmy budou následovat v~pøí¹tích kapitolách. +a párování v~bipartitních grafech. Dal¹í tokové algoritmy budou následovat v~pøí¹tích kapitolách. \h{Toky v sítích} @@ -52,6 +52,8 @@ se nikde mimo tato dv Základním problémem, kterým se budeme zabývat, je hledání {\I maximálního toku} (tedy toku nejvìt¹í mo¾né velikosti) a {\I minimálního øezu} (øezu nejmen¹í mo¾né kapacity). +\goodbreak + \s{Vìtièka:} V~ka¾dé síti existuje maximální tok a minimální øez. \proof Existence minimálního øezu je triviální, proto¾e øezù v~ka¾dé síti je koneènì mnoho; @@ -202,9 +204,6 @@ Toky nyn \figure{vertex-split.eps}{Rozdìlení vrcholu}{\epsfxsize} -%\figure{vrchol.eps}{Vrchol který chceme podrozdìlit.}{0.1\hsize} -%\figure{podrozdeleni.eps}{Výsledek podrozdìlení vrcholu.}{0.15\hsize} - Podobnì dostaneme neorientované lokální vìty (neorientovanou hranu nahradíme orientovanými v~obou smìrech) a z~nich pak i globální varianty popisující $k$-souvislost grafù: @@ -219,26 +218,36 @@ vrcholy existuje alespo \h{Maximální párování v bipartitním grafu} -Jedním z~problémù, které lze snadno pøevést na~hledání maximálního toku, je nalezení -{\I maximálního párování} v~bipartitním grafu\foot{Párování je mno¾ina hran taková, ¾e ¾ádné -dvì nemají spoleèný vrchol. Maximálním míníme vzhledem k~poètu hran, nikoliv vzhledem k~inkluzi.}. +Jiným problémem, který lze snadno pøevést na~hledání maximálního toku, je nalezení +{\I maximálního párování} v~bipartitním grafu, tedy mno¾iny hran takové, ¾e ¾ádné +dvì hrany nemají spoleèný vrchol. Maximálním míníme vzhledem k~poètu hran, +nikoliv vzhledem k~inkluzi. -Bipartitní graf $(A\cup B, E)$ pøevedeme na sí» obsahující v¹echny pùvodní vrcholy -a navíc dva nové vrcholy $s$ a~$t$, dále v¹echny pùvodní hrany orientované z~$A$ do~$B$, +Z~bipartitního grafu $(A\cup B, E)$ sestrojíme sí» obsahující v¹echny pùvodní vrcholy +a navíc dva nové vrcholy $s$ a~$t$, dále pak v¹echny pùvodní hrany orientované z~$A$ do~$B$, nové hrany z~$s$ do~v¹ech vrcholù partity~$A$ a ze~v¹ech vrcholù partity~$B$ do~$t$. Kapacity v¹ech hran nastavíme na jednièky: \fig{bipartitni.eps}{0.4\hsize} -Nyní si v¹imneme, ¾e ke~ka¾dému párování existuje celoèíselný tok stejné velikosti a naopak. -Tak¾e najdeme maximální celoèíselný tok (tøeba F-F algoritmem) a do~párování umístíme -právì hrany, po~kterých nìco teèe. +Nyní si v¹imneme, ¾e párování v~pùvodním grafu odpovídají celoèíselným tokùm v~této síti +a ¾e velikost toku je rovna velikosti párování. Staèí tedy nalézt maximální celoèíselný +tok (tøeba F-F algoritmem) a do~párování umístit ty hrany, po~kterých nìco teèe. Podobnì mù¾eme najít souvislost mezi øezy v~této síti a {\I vrcholovými pokrytími} zadaného grafu -- to jsou mno¾iny vrcholù takové, ¾e se dotýkají ka¾dé hrany. -Tak z~F-F vìty získáme: +Tak z~F-F vìty získáme jinou standardní vìtu: -\s{Vìta (König):} V~ka¾dém bipartitním grafu je velikost maximálního párování +\s{Vìta (Königova):} V~ka¾dém bipartitním grafu je velikost maximálního párování rovna velikosti minimálního vrcholového pokrytí. +\proof +Pokud je $W$ vrcholové pokrytí, musí hrany vedoucí mezi vrcholy této mno¾iny a zdrojem +a spotøebièem tvoøit stejnì velký øez, proto¾e ka¾dá $st$-cesta obsahuje alespoò +jednu hranu bipartitního grafu a ta je pokryta. Analogicky vezmeme-li libovolný +$st$-øez (ne~nutnì tokový, staèí hranový), mù¾eme ho bez zvìt¹ení upravit na~$st$-øez +pou¾ívající pouze hrany ze~$s$ a do~$t$, kterému pøímoèaøe odpovídá vrcholové pokrytí +stejné velikosti. +\qed + \bye -- 2.39.2