]> mj.ucw.cz Git - ga.git/blob - 14-floyd/14-floyd.tex
APSP: Metoda Rozdel a panuj
[ga.git] / 14-floyd / 14-floyd.tex
1 \input ../sgr.tex
2
3 \prednaska{13}{Nejkrat¹í cesty: Maticové metody}{}
4
5 {\bf POZOR: Pracovní verze. Zacházet opatrnì.}
6
7 V~pøedchozí kapitole jsme se zabývali algoritmy pro hledání nejkrat¹ích
8 cest z~daného poèáteèního vrcholu. Nyní se zamìøíme na výpoèet celé
9 metriky grafu, tedy matice vzdáleností, která pro ka¾dou dvojici vrcholù
10 obsahuje délku nejkrat¹í cesty mezi nimi.
11
12 Jeden zpùsob se ihned nabízí: postupnì spustit Dijkstrùv algoritmus pro v¹echny
13 mo¾né volby poèáteèního vrcholu, pøípadnì se pøed tím je¹tì pomocí potenciálù
14 zbavit záporných hran. Tak dosáhneme èasové slo¾itosti $\O(mn + n^2\log n)$,
15 co¾ je pro øídké grafy nejlep¹í známý výsledek -- jen $\O(\log n)$-krát
16 pomalej¹í, ne¾ je velikost výstupu.
17
18 Pro husté grafy obvykle pracují rychleji algoritmy zalo¾ené na maticích a zejména
19 na jejich násobení. Nìkolik takových si nyní pøedvedeme. Vrcholy grafu budou
20 v¾dy oèíslované èísly 1 a¾~$n$ a graf doplníme na úplný, pøièem¾ hrany, které
21 pùvodnì neexistovaly, obdr¾í délku $+\infty$.
22
23 \h{Floydùv-Warshallùv algoritmus}
24
25 Zaènìme algoritmem, který nezávisle na sobì objevili Floyd a Warshall.
26 Funguje pro libovolný orientovaný graf bez záporných cyklù.
27
28 Oznaème $D^k_{ij}$ délku nejkrat¹í cesty z~vrcholu~$i$ do vrcholu~$j$ pøes
29 vrcholy 1 a¾~$k$ (tím myslíme, ¾e v¹echny vnitøní vrcholy cesty le¾í v~mno¾inì $\{1,\ldots,k\}$).
30 Jako obvykle polo¾íme $D^k_{ij}=+\infty$, pokud ¾ádná taková cesta neexistuje.
31 Pak platí:
32 $$\eqalign{
33 D^0_{ij} &= \hbox{délka hrany $ij$,} \cr
34 D^n_{ij} &= \hbox{vzdálenost z~$i$ do~$j$,} \cr
35 D^k_{ij} &= \min( D^{k-1}_ij, D^{k-1}_{ik} + D^{k-1}_{kj} ). \cr
36 }$$
37 První dvì rovnosti dostaneme pøímo z~definice. Tøetí rovnost dostaneme rozdìlením
38 cest z~$i$ do~$j$ pøes 1 a¾~$k$ na ty, které se vrcholu~$k$ vyhnou (a~jsou tedy
39 cestami pøes 1 a¾~$k-1$), a ty, které ho pou¾ijí -- ka¾dou takovou mù¾eme slo¾it
40 z~cesty z~$i$ do~$k$ a cesty z~$k$ do~$j$, obojí pøes 1 a¾~$k-1$.
41
42 Zbývá vyøe¹it jednu malièkost: slo¾ením cesty z~$i$ do~$k$ s~cestou z~$k$ do~$j$
43 nemusí nutnì vzniknout cesta, proto¾e se nìjaký vrchol mù¾e opakovat. V~grafech
44 bez záporných cyklù nicménì takový sled nemù¾e být krat¹í ne¾ nejkrat¹í cesta,
45 tak¾e tím fale¹né øe¹ení nevyrobíme. (Pøesnìji: ze sledu $i\alpha v\beta k\gamma v\delta j$,
46 kde $v\not\in\beta,\gamma$, mù¾eme vypu¹tìním èásti $v\beta k\gamma v$ nezáporné
47 délky získat sled z~$i$ do~$j$ pøes 1 a¾~$k-1$, jeho¾ délka nemù¾e být men¹í
48 ne¾~$D^{k-1}{ij}$.)
49
50 Samotný algoritmus pak postupnì poèítá matice $D^0, D^1, \ldots, D^n$:
51
52 \algo
53 \:$D^0 \leftarrow \hbox{matice délek hran}$
54 \:Pro $k=1,\ldots,n$:
55 \::Pro $i,j=1,\ldots,n$:
56 \:::$D^k_{ij} = \min( D^{k-1}_ij, D^{k-1}_{ik} + D^{k-1}_{kj} )$.
57 \:$\hbox{Matice vzdáleností} \leftarrow D^n.$
58 \endalgo
59
60 Èasová slo¾itost tohoto algoritmu èiní $\Theta(n^3)$. Kubickou prostorovou
61 slo¾itost mù¾eme snadno sní¾it na~kvadratickou: Buï si uvìdomíme, ¾e v~ka¾dém
62 okam¾iku potøebujeme jen aktuální matici~$D^k$ a pøedchozí~$D^{k-1}$. Anebo
63 nahlédneme, ¾e mù¾eme $D^{k-1}$ na~$D^k$ pøepisovat na místì. U~hodnot $D_{ik}$
64 a~$D_{kj}$ je toti¾ podle definice stará i nová hodnota stejná. Algoritmu tedy
65 staèí $\Theta(n^2)$ pamìti.
66
67 \h{Regulární výrazy}
68
69 Pøedchozí algoritmus lze zajímavì zobecnit, toti¾ tak, aby pro ka¾dou dvojici
70 vrcholù sestrojil vhodnou reprezentaci mno¾iny v¹ech sledù vedoucích mezi touto
71 dvojicí. Tato reprezentace bude velice podobná regulárním výrazùm známým
72 z~teorie automatù. Zadaný orientovaný graf pøitom mù¾e obsahovat i smyèky
73 a násobné hrany.
74
75 \s{Definice:} {\I Svazek} je mno¾ina sledù, které mají spoleèný poèáteèní
76 a koncový vrchol. {\I Typem} svazku nazveme uspoøádanou dvojici tìchto vrcholù.
77 Místo \uv{svazek typu $(u,v)$} budeme obvykle øíkat prostì {\I $uv$-svazek.}
78
79 Triviálními pøípady svazkù jsou prázdná mno¾ina~$\emptyset$, hrana~$uv$ a pro
80 $u=v$ také sled~$\varepsilon$ nulové délky. Svazky mù¾eme kombinovat
81 následujícími operacemi:
82
83 \itemize\ibull
84 \:$A\cup B$ -- {\I sjednocení} dvou svazkù tého¾ typu,
85 \:$AB$ nebo $A\cdot B$ -- {\I zøetìzení} $uv$-svazku~$A$ s~$vw$-svazkem~$B$: výsledkem je $uw$-svazek
86 obsahující v¹echna spojení sledu z~$A$ se sledem z~$B$,
87 \:$A^*$ -- {\I iterace} $uu$-svazku: výsledkem je $uu$-svazek
88 $\varepsilon \cup A \cup AA \cup AAA \cup \ldots$ (tedy v¹echna mo¾ná
89 spojení koneènì mnoha sledù z~$A$).
90 \endlist
91
92 \>Ve~výrazu definujícím~$A^*$ jsme vyu¾ili, ¾e operace sjednocení a zøetìzení
93 jsou asociativní, tak¾e je nemusíme závorkovat. Navíc sjednocení má ve~výrazech
94 ni¾¹í prioritu ne¾ zøetìzení.
95
96 \>Svazky budeme obvykle reprezentovat {\I sledovými výrazy,} co¾ jsou
97 výrazy koneèné délky sestávající se z~triviálních svazkù a vý¹e uvedených
98 operací.
99
100 \s{Pozorování:} Sledy mù¾eme reprezentovat øetìzci nad abecedou, její¾
101 symboly jsou identifikátory hran. Sledové výrazy pak odpovídají regulárním
102 výrazùm nad touto abecedou.
103
104 Uká¾eme, jak pro v¹echny dvojice vrcholu $i,j$ sestrojit sledový výraz $R_{ij}$
105 popisující svazek v¹ech sledù z~$i$ do~$j$. Podobnì jako u~Floydova-Warshallova
106 algoritmu zavedeme $R^k_{ij}$ coby výraz popisující sledy z~$i$ do~$j$ pøes 1 a¾~$k$
107 a nahlédneme, ¾e platí:
108 $$\eqalign{
109 R^0_{ij} &= \hbox{mno¾ina v¹ech hran z~$i$ do~$j$}, \cr
110 R^n_{ij} &= \hbox{hledané $R_{ij}$}, \cr
111 R^k_{ij} &= R^{k-1}_{ij} \cup R^{k-1}_{ik}(R^{k-1}_{kk})^*R^{k-1}_{kj}. \cr
112 }$$
113 První dvì rovnosti opìt dostaneme pøímo z~definice (mno¾inu v¹ech hran zapí¹eme
114 buï jako prázdnou nebo ji vytvoøíme sjednocováním z~jednoprvkových mno¾in). Tøetí
115 rovnost vychází z~toho, ¾e ka¾dý sled z~$i$ do~$j$ buï neobsahuje~$k$, nebo ho
116 mù¾eme rozdìlit na~èásti mezi jednotlivými náv¹tìvami vrcholu~$k$.
117
118 Algoritmus tedy bude postupnì budovat matice $R^0, R^1, \ldots, R^n$ podle tìchto
119 pravidel. Provedeme pøi tom $\Theta(n^3)$ operací, ov¹em s~výrazy, jejich¾ délka
120 mù¾e být a¾ øádovì~$4^n$. Radìji ne¾ jako øetìzce je budeme ukládat v~podobì
121 acyklických orientovaných grafù: vrcholy budou operace, hrany je budou pøipojovat
122 k~operandùm.
123
124 K~pøímému pou¾ití se takový exponenciálnì dlouhý výraz hodí málokdy, ale mù¾e
125 nám pomoci odpovídat na rùzné otázky týkající se sledù s~danými koncovými vrcholy.
126 Máme-li nìjakou funkci~$f$ pøiøazující hodnoty mno¾inám sledù kódovaným sledovými
127 výrazy, staèí umìt vyhodnotit:
128 \itemize\ibull
129 \:výsledek pro triviální výrazy $f(\emptyset)$, $f(\varepsilon)$ a $f(e)$ pro hranu~$e$,
130 \:hodnoty $f(\alpha\cup\beta)$, $f(\alpha\beta)$ a $f(\alpha^*)$, známe-li ji¾ $f(\alpha)$ a $f(\beta)$.
131 \endlist
132 \>Pro výpoèet v¹ech $f(R_{ij})$ nám pak staèí $\Theta(n^3)$ vyhodnocení funkce~$f$.
133
134 \s{Poznámka pro ctitele algebry:} Vý¹e uvedená konstrukce není nic jiného, ne¾ popis
135 homomorfismu~$f$ z~algebry $({\cal S},\emptyset,\varepsilon_1,\ldots,\varepsilon_n,
136 e_1,\ldots,e_m,\cup,\cdot,{}^*)$ nad mno¾inou~${\cal S}$ v¹ech svazkù do~nìjaké
137 algebry $(X,{\bf 0},c_1,\ldots,c_n,h_1,\ldots,h_m,\oplus,\otimes,\circledast)$, kde~$X$ je mno¾ina
138 v¹ech ohodnocení sledù, {\bf 0}, $c_1,\ldots,c_n$ a $h_1,\ldots,h_m$ jsou konstanty,
139 $\oplus$ a~$\otimes$ binární operace a $\circledast$ unární operace. Prùbìh výpoètu
140 upraveného algoritmu je pak homomorfním obrazem prùbìhu výpoètu pùvodního algoritmu
141 pracujícího pøímo se svazky.
142
143 \s{Pøíklady:}
144
145 \>{\I Nejkrat¹í sled:}
146 $$\eqalign{
147 f(\emptyset)&=+\infty \cr
148 f(\varepsilon)&=0 \cr
149 f(e)&=\ell(e) \hbox{\quad (délka hrany)} \cr
150 f(\alpha\cup\beta) &= \min(f(\alpha),f(\beta)) \cr
151 f(\alpha\beta) &= f(\alpha) + f(\beta) \cr
152 f(\alpha^*) &= \cases{0 & \hbox{pro $f(\alpha)\ge 0$} \cr -\infty & \hbox{pro $f(\alpha)<0$} \cr} \cr
153 }$$
154 (Pokud pøedpokládáme, ¾e v~grafu nejsou záporné cykly, je $f(\alpha^*)$ v¾dy nulové
155 a dostaneme pøesnì Floydùv-Warshallùv algoritmus.)
156
157 \>{\I Nej¹ir¹í cesta} (hranám jsou pøiøazeny ¹íøky, ¹íøka cesty je minimum z~¹íøek hran):
158 $$\eqalign{
159 f(\emptyset)&=0 \cr
160 f(\varepsilon)&=\infty \cr
161 f(e)&=w(e) \hbox{\quad (¹íøka hrany)} \cr
162 f(\alpha\cup\beta) &= \max(f(\alpha),f(\beta)) \cr
163 f(\alpha\beta) &= \min(f(\alpha),f(\beta)) \cr
164 f(\alpha^*) &= \infty \cr
165 }$$
166
167 \>{\I Pøevod koneèného automatu na regulární výraz:} Vrcholy multigrafu budou odpovídat
168 stavùm automatu, hrany mo¾ným pøechodùm mezi stavy. Ka¾dou hranu ohodnotíme symbolem
169 abecedy, po jeho¾ pøeètení automat pøechod provede. Funkce~$f$ pak pøiøadí $uv$-svazku~$\psi$
170 regulární výraz popisující mno¾inu v¹ech øetìzcù, po jejich¾ pøeètení automat pøejde
171 ze~stavu~$u$ do stavu~$v$ po pøechodech z~mno¾iny~$\psi$. Vyhodnocování funkce~$f$
172 odpovídá pøímoèarým operacím s~øetìzci.
173
174 \h{Násobení matic}
175
176 Øe¹íme-li grafové problémy pomocí matic, nabízí se pou¾ít známé subkubické algoritmy
177 pro lineárnì algebraické úlohy. Ty jsou obvykle zalo¾eny na efektivním násobení
178 matic -- dvì matice $n\times n$ mù¾eme vynásobit v~èase $\O(n^2.808)$ Strassenovým
179 algoritmem~\cite{strassen:matmult}, pøípadnì asymptoticky nejrychlej¹ím známým algoritmem od Coppersmithe
180 a Winograda~\cite{coppersmith:matmult} v~èase $\O(n^{2.376})$. Slavná hypotéza øíká,
181 ¾e pro ka¾dé $\omega>2$ existuje algoritmus násobící matice se slo¾itostí $\O(n^\omega)$
182 (blí¾e o~tomto fascinujícím tématu viz \cite{szegedy:matmult}). Oznaème tedy~$\omega$
183 nejni¾¹í exponent, kterého jsme schopni dosáhnout.
184
185 Co se stane, kdy¾ mocníme matici sousednosti~$A$ grafu? V~matici $A^k$ se na pozici
186 $i,j$ nachází poèet sledù délky~$k$, které vedou z~vrcholu~$i$ do vrcholu~$j$.
187 (Snadný dùkaz indukcí vynecháváme.) Pro libovolné $k\ge n-1$ jsou tedy v~$(A+E)^k$
188 (kde $E$ znaèí jednotkovou matici; doplnili jsme tedy do grafu smyèky) nenuly
189 pøesnì tam, kde z~$i$ do~$j$ vede cesta.
190
191 To nám dává jednoduchý algoritmus pro výpoèet matice dosa¾itelnosti~$R$ ($R_{ij}$
192 je 1 nebo~0 podle toho, zda z~$i$ do~$j$ vede cesta). Do~matice~$A$ doplníme
193 na diagonálu jednièky a poté ji $\lceil \log_2 n\rceil$-krát umocníme na~druhou.
194 Abychom se vyhnuli velkým èíslùm, nahradíme po ka¾dém umocnìní nenuly jednièkami.
195 Celkem tedy provedeme $\O(\log n)$ násobení matic obsahující polynomiálnì velká
196 èísla, co¾ trvá $\O(n^\omega\log n)$.
197
198 Na~tento postup se mù¾eme dívat i~obecnìji:
199
200 \s{Definice:} {\I $(\oplus,\otimes)$-souèin} matic~$A,B \in X^{n\times n}$
201 kde $\oplus$ a~$\otimes$ jsou dvì asociativní binární operace na~mno¾inì~$X$,
202 je matice~$C$ taková, ¾e
203 $$
204 C_{ij} = \bigoplus_{k=1}^n A_{ik}\otimes B_{kj}.
205 $$
206 Klasické násobení matic je tedy $(+,\cdot)$-souèin.
207
208 \s{Pozorování:} Pokud $A$ a~$B$ jsou matice svazkù ($A_{ij}$ a $B_{ij}$
209 jsou $ij$-svazky) a $C$ jejich $(\cup,\cdot)$-souèin, pak $C_{ij}$ je
210 svazek v¹ech sledù vzniklých spojením nìjakého sledu z~$A$ zaèínajícího
211 v~$i$ a nìjakého sledu z~$B$ konèícího v~$j$.
212
213 Podobnì jako v~pøedchozí sekci si tedy mù¾eme poøídit funkci~$f$ pøiøazující
214 svazkùm hodnoty z~nìjaké mno¾iny~$X$ a operace $\oplus$ a $\otimes$ na~$X$,
215 pro nì¾ platí $f(\alpha\cup\beta) = f(\alpha) \oplus f(\beta)$ a $f(\alpha\beta)
216 = f(\alpha) \otimes f(\beta)$. Pak staèí vzít matici popisující ohodnocení
217 v¹ech sledù délky 0 nebo~1 (to je obdoba matice sousednosti), a provést $\O(\log n)$
218 $(\oplus,\otimes)$-souèinù k~tomu, abychom znali ohodnocení svazkù sledù délky
219 právì~$k$ pro nìjaké $k\ge n$.
220
221 S~$(\lor,\land)$-souèiny a maticí sousednosti s~jednièkami na diagonále získáme
222 algoritmus pro výpoèet dosa¾itelnosti. Ka¾dý souèin pøitom mù¾eme provést jako
223 obyèejné násobení matic následované pøepsáním nenul na jednièky, tak¾e celý
224 výpoèet bì¾í v~èase $\O(n^\omega\log n)$.
225
226 Podobnì mù¾eme poèítat i matici vzdáleností: zaèneme s~maticí délek hran doplnìnou o~nuly na~diagonále
227 a pou¾ijeme $(\min,+)$-souèiny. Tyto souèiny ale bohu¾el neumíme pøevést na klasické násobení matic.
228 Pøesto je známo nìkolik algoritmù efektivnìj¹ích ne¾ $\Theta(n^3)$, by» pouze o~málo:
229 napøíklad Zwickùv \cite{zwick:apsp} v~èase $\O(n^3\sqrt{\log\log n}/\log n)$
230 (zalo¾ený na dekompozici a pøedpoèítání malých blokù) nebo Chanùv \cite{chan:apsp} v~$\O(n^3/\log n)$
231 (pou¾ívající geometrické techniky). Abychom porazili Floydùv-Warshallùv algoritmus,
232 potøebovali bychom ov¹em vìt¹í ne¾ logaritmické zrychlení, proto¾e souèinù potøebujeme
233 vypoèítat logaritmicky mnoho.
234
235 Dodejme je¹tì, ¾e pro grafy ohodnocené malými celými èísly je mo¾né vyu¾ít
236 celou øadu dal¹ích trikù. Zájemce o~tento druh algoritmù odkazujeme na Zwickùv
237 èlánek~\cite{zwick:apspint}.
238
239 \h{Rozdìl a panuj}
240
241 Pøedchozí pøevod je ov¹em trochu marnotratný. ©ikovným pou¾itím metody Rozdìl a panuj
242 mù¾eme èasovou slo¾itost podstatnì sní¾it. Postup pøedvedeme pro dosa¾itelnost: na vstupu
243 tedy dostaneme matici sousednosti~$A$, výstupem má být její transitivní uzávìr~$A^*$
244 (matice dosa¾itelnosti). V¹echny souèiny matic v~tomto oddílu budou typu $(\lor,\land)$.
245
246 Vrcholy grafu rozdìlíme na dvì mno¾iny $X$ a~$Y$ pøibli¾nì stejné velikosti,
247 bez újmy na obecnosti tak, aby matice~$A$ mìla následující blokový tvar:
248 $$A = \pmatrix{ P & Q \cr R & S \cr }.$$
249 Zde podmatice~$P$ popisuje hrany z~$X$ do~$X$, podmatice~$Q$ hrany z~$X$ do~$Y$, atd.
250
251 Pokud matici~$A^*$ zapí¹eme rovnì¾ v~blokovém tvaru:
252 $$A^* = \pmatrix{ I & J \cr K & L \cr },$$
253 bude platit:
254 $$\eqalign{
255 I &= (P \lor QR^*S)^*, \cr
256 J &= IQS^*, \cr
257 K &= S^*RI, \cr
258 L &= S^* \lor S^*RIQS^*.
259 }$$
260 Jednotlivé rovnosti mù¾eme èíst takto:
261 \def\nIJKL{\count0=`H\advance\count0 by\itemcount{\bf\char\count0:}}
262 \numlist\nIJKL
263 \:Sled z~$X$ do~$X$ vznikne opakováním èástí, z~nich¾ ka¾dá je buïto
264 hrana uvnitø~$X$ nebo pøechod po hranì z~$X$ do~$Y$ následovaný sledem
265 uvnitø~$Y$ a pøechodem zpìt do~$X$.
266 \:Sled z~$X$ do~$Y$ mù¾eme rozdìlit v~místì, kdy naposledy pøechází
267 po~hranì z~$X$ do~$Y$. První èást pøitom bude sled z~$X$ do~$X$,
268 druhá sled uvnitø~$Y$.
269 \:Se sledem z~$Y$ do~$X$ nalo¾íme obdobnì.
270 \:Sled z~$Y$ do~$Y$ vede buïto celý uvnitø~$Y$, nebo ho mù¾eme rozdìlit
271 na èást pøed prvním pøechodem z~$Y$ do~$X$, tento pøechod, sled z~$X$ do~$Y$,
272 pøechod zpìt a sled uvnitø~$Y$.
273 \endlist
274
275 K~výpoètu matice~$A^*$ nám tedy staèí spoèítat 3~tranzitivní uzávìry
276 matic polovièní velikosti (k~èemu¾ pou¾ijeme rekurzi), dále pak $\O(1)$
277 $(\lor,\land)$-souèinù a $\O(1)$ souètù matic.
278
279 Èasovou slo¾itost $t(n)$ mù¾eme popsat následující rekurencí:
280 $$t(n) = 3t(n/2) + \Theta(1)\cdot\mu(n/2) + \Theta(n^2),$$
281 kde $\mu(k)$ znaèí èas potøebný na jeden $(\lor,\land)$-souèin
282 matic $k\times k$. Jeliko¾ jistì platí $\mu(n/2)=\Omega(n^2)$,
283 má tato rekurence podle kuchaøkové vìty øe¹ení $t(n) = \mu(n)$.
284
285 Ukázali jsme tedy, ¾e výpoèet transitivního uzávìru je nejvý¹e stejnì
286 nároèný jako $(\lor,\land)$-násobení matic -- mù¾eme ho tedy provést
287 v~èase $\O(n^\omega)$. Dokonce mù¾eme snadno nalézt i opaèný pøevod,
288 tak¾e oba problémy jsou asymptoticky stejnì tì¾ké.
289
290 Podobnì nalézt matici vzdáleností je stejnì tì¾ké jako $(\min,+)$-souèin,
291 tak¾e na to staèí èas $\O(n^3/\log n)$.
292
293 \h{Seidelùv algoritmus}
294
295 Pro neorientované neohodnocené grafy mù¾eme dosáhnout je¹tì lep¹ích
296 výsledkù. Matici vzdáleností lze spoèítat v~èase $\O(n^\omega\log n)$
297 Seidelovým algoritmem (FIXME: odkaz). Ten funguje následovnì:
298
299 \s{Definice:} {\I Druhá mocnina grafu~$G$} je graf~$G^2$ na té¾e mno¾inì vrcholù,
300 v~nìm¾ jsou vrcholy~$i$ a~$j$ spojeny hranou právì tehdy, existuje-li v~$G$ sled
301 délky nejvý¹e~2 vedoucí z~$i$ do~$j$.
302
303 \s{Pozorování:} Matici sousednosti grafu~$G^2$ získáme z~matice sousednosti
304 grafu~$G$ jedním $(\lor,\land)$-souèinem, tedy v~èase $\O(n^\omega)$.
305
306 Seidelùv algoritmus bude postupovat rekurzivnì: Sestrojí graf~$G^2$, rekurzí
307 spoèítá jeho matici vzdáleností~$D'$ a z~ní pak rekonstruuje matici vzdáleností~$D$
308 zadaného grafu. Rekurze konèí, pokud $G^2=G$ -- tehdy u¾ je ka¾dá komponenta
309 souvislosti zahu¹tìna na~úplný graf, tak¾e matice vzdálenosti je rovna matici sousednosti.
310
311 Zbývá ukázat, jak z~matice~$D'$ spoèítat matici~$D$. Zvolme pevnì~$i$ a zamìøme
312 se na funkce $d(v)=D_{iv}$ a $d'(v)=D'_{iv}$. Jistì platí $d'(v) = \lfloor d(v)/2 \rfloor$,
313 proèe¾ $d(v)$ je buï rovno $2d'(v)$ nebo o~1 vy¹¹í. Nauèíme se rozpoznat, jestli
314 $d(v)$ má být sudé nebo liché, a~z~toho v¾dy poznáme, jestli je potøeba jednièku pøièíst.
315
316 Jak vypadá funkce~$d$ na sousedech vrcholu~$v\ne i$? Pro alespoò jednoho souseda~$u$ je
317 $d(u) = d(v)-1$ (to platí pro sousedy, kteøí le¾í na nìkteré z~nejkrat¹ích cest z~$v$ do~$i$).
318 Pro v¹echny ostatní sousedy je $d(u)=d(v)$ nebo $d(u)=d(v)+1$.
319
320 Pokud $d(v)$ je liché, vyjde pro sousedy le¾ící na nejkrat¹ích cestách $d'(u)=d'(v)$
321 a pro ostatní sousedy $d'(u)\ge d'(v)$, tak¾e prùmìr z~$d'(u)$ pøes sousedy je
322 alespoò~$d'(v)$. Je-li naopak $d(v)$ sudé, musí být pro sousedy na nejkrat¹ích cestách
323 $d'(u) < d(v)$ a pro v¹echny ostatní $d'(u) = d(v)$, tak¾e prùmìr klesne pod~$d'(v)$.
324
325 Prùmìry pøes sousedy pøitom mù¾eme spoèítat násobením matic: vynásobíme matici
326 sousednosti grafu~$G$ maticí vzdáleností~$D'$. Na pozici~$i,j$ se objeví souèet
327 hodnot $D_{ik}$ pøes v¹echny sousedy vrcholu~$j$. Ten staèí vydìlit stupòem
328 vrcholu~$j$ a hledaný prùmìr je na svìtì.
329
330 Po~provedení jednoho násobení matic tedy dovedeme pro ka¾dou dvojici vrcholù
331 v~konstantním èase spoèítat $D_{ij}$ z~$D'_{ij}$. Jedna úroveò rekurze proto
332 trvá $\O(n^\omega)$ a jeliko¾ prùmìr grafu poka¾dé klesne alespoò dvakrát,
333 je úrovní $\O(\log n)$ a celý algoritmus dobìhne ve~slíbeném èase $\O(n^\omega\log n)$.
334
335 \references
336 \bye