Dijkstr˚ uv algoritmus Hled´an´ı nejkratˇs´ı cesty v nez´apornˇe hranovˇe ohodnocen´em grafu Necht’ je d´ an orientovan´ y graf G = (V, H) a funkce, kter´ a kaˇzd´e hranˇe h = (u, v) ∈ H pˇriˇrad´ı nez´ aporn´e re´aln´e ˇc´ıslo oznaˇcovan´e L(h) nebo L(u, v). Je-li u0 , u1 , . . . , uk orientovan´a cesta v G, pak jej´ı d´elkou nazveme ˇc´ıslo k X
L(ui−1 , ui ).
i=1
Jsou-li d´ any dva vrcholy u, v grafu G, c´ılem je urˇcit, zda existuje orientovan´a cesta z u do v a pˇredevˇs´ım pokud existuje, tak nal´ezt nejkratˇs´ı z nich. Zn´ am´e algoritmy pro tento probl´em urˇcuj´ı bud’ vzd´ alenosti z u do vˇsech ostatn´ıch vrchol˚ u (mezi nimi i do v) a nebo naopak vzd´ alenosti ze vˇsech vrchol˚ u do v. Probl´em nalezen´ı nejkratˇs´ı cesty v grafu je ˇreˇsen Bellman-Fordov´ ym algoritmem, kter´ y nevyˇzaduje pˇredpoklad o nez´apornosti d´elky hrany. Pokud ovˇsem jsou hrany nez´ aporn´e, coˇz je v praxi velmi ˇcast´e, pokud napˇr´ıklad d´elky hran souvisej´ı s fyzickou vzd´ alenost´ı vrchol˚ u, je vhodn´e pouˇz´ıvat algoritmus Dijkstr˚ uv, kter´ y je jednoduˇs´ı a pˇredevˇs´ım rychlejˇs´ı. Poˇca´tek, ze kter´eho budeme hledat vzd´ alenosti do ostatn´ıch vrchol˚ u si oznaˇc´ıme jako v0 . Existuje ˇrada variant implementace Dijkstrova algoritmu. Zde byla zvolena varianta, kde kaˇzd´ y vrchol m˚ uˇze b´ yt ve tˇrech stavech: nedosaˇzen´y, dosaˇzen´y a probran´y; dosaˇzen´ y pˇritom je ch´ ap´an jako “dosaˇzen´ y, ale neprobran´ y”; pro kaˇzd´ y vrchol w, kter´ y je dosaˇzen´ y nebo probran´ y, je d´ ano ˇc´ıslo E(w) (E jako “Estimation”), coˇz, jak pozdˇeji dok´ aˇzeme, bude horn´ı odhad vzd´ alenosti z poˇca´tku v0 do w a na konci v´ ypoˇctu pˇr´ımo vzd´ alenost z v0 do w. Pro nedosaˇzen´e vrcholy bude E(w) nedefinov´ano. Pokud w nen´ı poˇca´tek, pak jestliˇze E(w) je definov´ano, bude pro takov´ y vrchol d´ an vrchol P (w); pomoc´ı hodnot P bude moˇzn´e pro kaˇzd´ y vrchol w s definovan´ ym E(w) snadno nal´ezt cestu d´elky E(w) z poˇca´tku do w zp˚ usobem, kter´ y bude pops´ an pozdˇeji. Dijkstr˚ uv algoritmus 1. oznaˇc poˇca´tek v0 jako dosaˇzen´ y a E(v0 ) := 0; 2. for kaˇzd´ y vrchol w r˚ uzn´ y od poˇca´tku v0 do 3. oznaˇc vrchol w jako nedosaˇzen´ y; 4. while existuje dosaˇzen´ y vrchol u do begin 5. zvol jako u dosaˇzen´ y vrchol, kter´ y m´a minim´aln´ı E(u); 6. oznaˇc u jako probran´ y; 7. for vˇsechny vrcholy w takov´e, ˇze (u, w) je hrana do 8. if w je nedosaˇzen´ y nebo E(w) > E(u) + L(u, w) then begin 9. if w je nedosaˇzen´ y then oznaˇc w jako dosaˇzen´ y; 10. E(w) := E(u) + L(u, w); 11. P (w) := u; 12. end; 13. end.
1
Volba u znamen´ a zvolit dosaˇzen´ y vrchol u takov´ y, ˇze E(u) ≤ E(w) pro kaˇzd´ y dosaˇzen´ y vrchol w; takov´ ych vrchol˚ u u m˚ uˇze b´ yt v´ıce, pak je moˇzno zvolit libovoln´ y z nich. Je snadn´e dok´ azat, ˇze se v´ ypoˇcet algoritmu zastav´ı: Lemma 1 Stav vrcholu se m˚ uˇze mˇenit jen z “nedosaˇzen´y” na “dosaˇzen´y” nebo z “dosaˇzen´y’ na “probran´y”. D˚ ukaz: Jedin´e zmˇeny stavu proti poˇca´teˇcn´ımu nastaven´ı mohou nastat v ˇr´adc´ıch 6 a 9. ♣ Theorem 2 V´ypoˇcet Dijkstrova algoritmu se zastav´ı ponejv´yˇse N iterac´ıch while cyklu, kde N je poˇcet vrchol˚ u grafu. D˚ ukaz: Z popisu algoritmu a pˇredchoz´ıho lemmatu plyne, ˇze mnoˇzina probran´ ych vrchol˚ u se kaˇzdou iterac´ı cyklu zvˇetˇs´ı o jeden vrchol a jej´ı velikost je pˇritom mezi 0 a N . ♣ V dalˇs´ım budeme dokazovat r˚ uzn´e vztahy mezi hodnotami promˇenn´ ych. Nˇekter´e plat´ı st´ ale, nˇekter´e mohou b´ yt doˇcasnˇe naruˇseny a v z´ apˇet´ı obnoveny. Budeme se proto zaj´ımat, zda plat´ı v okamˇzic´ıch, kdy se zaˇc´ın´a testovat podm´ınka while cyklu. Tyto okamˇziky budeme naz´ yvat vstupy do cyklu. V prvn´ım ˇr´adku v´ ypoˇctu se poˇca´tek v0 oznaˇc´ı jako dosaˇzen´ y a definuje se hodnota E(v0 ). Pˇri prvn´ım vstupu do while cyklu je poˇca´tek jedin´ ym dosaˇzen´ ym vrcholem, bude tedy vybr´ an jako vrchol u v ˇr´adku 5 a v z´ apˇet´ı v ˇr´adku 6 oznaˇcen jako probran´ y. Na z´ akladˇe lemmatu 1 pak jiˇz z˚ ustane probran´ ym aˇz do konce v´ ypoˇctu. Status ostatn´ıch vrchol˚ u popisuje n´ asleduj´ıc´ı Lemma 3 Pokud w 6= v0 , pak pˇri kaˇzd´em vstupu do cyklu plat´ı: E(w) je definov´ ano pr´ avˇe kdyˇz je definov´ ano P (w) a to je pr´ avˇe kdyˇz w je dosaˇzen´y nebo probran´y vrchol. D˚ ukaz: Vrchol w jin´ y neˇz poˇca´tek je po proveden´ı inicializace v ˇr´adc´ıch 2 a 3 nedosaˇzen´ y a E(w) a P (w) nejsou definov´any. Uvaˇzujme prvn´ı okamˇzik, kdy se nˇekter´e z tˇechto tvrzen´ı zmˇen´ı. To se m˚ uˇze st´at pouze kdyˇz je prob´ır´ ana hrana (u, w) pro nˇejak´ y vrchol u. V takov´em pˇr´ıpadˇe se najednou zmˇen´ı klasifikace vrcholu w na dosaˇzen´ y a definuj´ı se hodnoty E(w) a P (w). Podle lemmatu 1 uˇz vrchol w nikdy nestane nedosaˇzen´ ym a E(w) a P (w) z˚ ust´ avaj´ı st´ale definov´any. ♣ Velmi d˚ uleˇzit´ ym, i kdyˇz na prvn´ı pohled samozˇrejm´ ym je n´ asleduj´ıc´ı Lemma 4 Je-li v probran´y vrchol a w dosaˇzen´y vrchol, pak E(v) ≤ E(w). Jestliˇze v je probran´y vrchol, pak se hodnota E(v) nem˚ uˇze zmˇenit. D˚ ukaz: Podle pˇredchoz´ıho lemmatu jsou pro probran´e a dosaˇzen´e vrcholy hodnoty E definov´any. Tvrzen´ı lemmatu dok´ aˇzeme indukc´ı podle poˇctu krok˚ u v´ ypoˇctu. Po proveden´ı inicializace v ˇr´adc´ıch 1-3 trivi´alnˇe plat´ı, neexistuj´ı probran´e vrcholy. Necht’ plat´ı do nˇejak´eho vstupu do while cyklu. Platnost tvrzen´ı 2
by se mohla poruˇsit bud’ zmˇenou stavu nˇejak´eho vrcholu nebo zmˇenou hodnoty E(w) nˇejak´eho vrcholu w pˇri prov´adˇen´ı tˇela cyklu. Pˇredpokl´adejme, ˇze se prov´ad´ı tˇelo cyklu a v ˇr´adku 6 algoritmu byl vybr´ an vrchol u. Uk´ aˇzeme, ˇze pro kaˇzd´ y jiˇz probran´ y vrchol v a kaˇzd´ y dosaˇzen´ y vrchol w plat´ı E(v) ≤ E(u) ≤ E(w). Pˇri vstupu do cyklu E(v) ≤ E(u) pˇredstavuje indukˇcn´ı pˇredpoklad, nerovnost E(u) ≤ E(w) zase vypl´ yv´a z toho, jak byl vrchol u vybr´ an. Zmˇeny, kter´e mohou nastat nebo nastanou pˇri prov´adˇen´ı tˇela cyklu s vybran´ ym vrcholem u, kter´e by mohly naruˇsit platnost tvrzen´ı lemmatu, jsou n´ asleduj´ıc´ı: Vrchol u je pˇreklasifikov´an na probran´ y; jelikoˇz E(u) ≤ E(w) pro kaˇzd´ y dosaˇzen´ y w, lemma z˚ ust´ av´ a v platnosti. Objev´ı se nov´ y dosaˇzen´ y vrchol x; pro takov´ y vrchol se nastav´ı E(x) = E(u)+L(u, w), a v d˚ usledku nez´apornosti pro libovoln´e probran´e v plat´ı E(v) ≤ E(u) ≤ E(x), coˇz je v souladu s tvrzen´ım lemmatu. Pro nˇekter´ y dosaˇzen´ y vrchol x se hodnota E(x) zmˇen´ı na E(u) + L(u, w); podobnˇe jako v pˇredchoz´ım odstavci se uk´aˇze, ˇze nov´a hodnota je st´ale alespoˇ n tak velk´a, jako E(v) pro libovoln´ y probran´ y vrchol v. Je-li vrchol x probran´ y a (u, x) je hrana, pak je E(x) ≤ E(u) ≤ E(u)+L(u, x) (lev´ a nerovnost plyne z indukˇcn´ıho pˇredpokladu, druh´ a z nez´apornosti d´elek hran) a tedy podm´ınka E(x) > E(u) + L(u, x) v ˇr´adku 8 nebude nikdy splnˇena. U probran´eho vrcholu x proto jiˇz ke zmˇenˇe stavu nebo hodnoty E(x) nebo P (x) nem˚ uˇze doj´ıt. ♣ Lemma 5 Hodnota P (v0 ) nen´ı nikdy definov´ ana. D˚ ukaz: Po proveden´ı inicializace P (v0 ) definov´ano nen´ı a pokud by bylo definov´ano pozdˇeji, stalo by se to souˇcasnˇe se zmˇenou E(v0 ) v okamˇziku, kdy jiˇz v0 je probran´ y. Tuto moˇznost ale pˇredchoz´ı lemma vylouˇcilo. ♣ Nyn´ı uk´ aˇzeme, ˇze hodnoty P (w) umoˇzn ˇ uj´ı pro kaˇzd´ y probran´ y nebo dosaˇzen´ y vrchol w naj´ıt cestu z poˇca´tku do w, kter´ a m´a d´elku E(w). Lemma 6 Je-li P (w) definov´ ano a oznaˇc´ıme-li v = P (w), pak (v, w) je hrana v je probran´y vrchol a E(v) + L(v, w) = E(w). D˚ ukaz: Uvaˇzujme jist´ y okamˇzik τ v´ ypoˇctu, kdy P (w) je definov´ano. V okamˇziku, kdy bylo P (w) naposledy mˇenˇeno a to na hodnotu v, byla prob´ır´ ana hrana (v, w), a provedlo se dosazen´ı P (w) := v. (P (w), w) = (v, w) je tedy hrana a vrchol v je probran´ y. Hodnota E(w) byla tehdy zmˇenˇena na E(u) + L(v, w) a od t´e doby se do okamˇziku τ nezmˇenila, protoˇze zmˇeny E(w) a P (w) jsou spolu. Jelikoˇz v bylo v okamˇziku zmˇeny P (w) probran´e, pˇredchoz´ı lemma ˇr´ık´ a, ˇze E(v) se jiˇz tak´e nezmˇenilo, proto rovnost E(v) + L(v, w) = E(w) z˚ ust´ av´ av platnosti. ♣ Lemma 7 P je acyklick´ a relace, neboli neexistuje posloupnost vrchol˚ u w0 , . . . , wk takov´ a, ˇze wi−1 = P (wi ) pro i = 1, . . . , k a wk = P (w0 ).
3
D˚ ukaz: Z lemmatu 1 a podm´ınky cyklu plyne, ˇze kaˇzd´ y vrchol w, pro kter´ y je v pr˚ ubˇehu v´ ypoˇctu E(w) definov´ano, je na konci v´ ypoˇctu probran´ y. Pro takov´ y vrchol oznaˇcme jako T (w) takov´e ˇc´ıslo T , ˇze vrchol se stal probran´ ym v T -t´e iteraci while cyklu. Jelikoˇz se v kaˇzd´e iteraci stane probran´ ym jedin´ y vrchol, je tato funkce prost´ a. Jestliˇze v nˇekter´em okamˇziku je v probran´ y vrchol a w je dosaˇzen´ y, pak zˇrejmˇe T (v) < T (w). Kdykoli se novˇe definuje nebo mˇen´ı P (w) pro nˇejak´ y vrchol w, stane se tak pˇri prob´ır´ an´ı hrany (u, w) v okamˇziku, kdy u kr´ atce pˇredt´ım byl oznaˇcen za probran´ y vrchol a w je jeˇstˇe (novˇe nebo dˇr´ıve) dosaˇzen´ y. Kdykoliv je tedy u = P (w), je T (u) < T (w), coˇz ale vyluˇcuje moˇznost cyklu relace P . ♣ Jestliˇze tedy E(w) definov´ano, pak definujme posloupnost w = z0 , z1 , . . . pˇredpisem zi = P (zi−1 ) pro i = 1, . . .. Na z´ akladˇe pˇredchoz´ıho lemmatu mus´ı tato posloupnost b´ yt prost´ a a protoˇze mnoˇzina vrchol˚ u je koneˇcn´a, mus´ı i pr´avˇe definovan´a posloupnost b´ yt koneˇcn´a. Pˇredpokl´adejme, ˇze do n´ı uˇz nen´ı moˇzno pˇridat dalˇs´ı prvek. Podle lemmat 3, 6 a 5 tedy tato posloupnost konˇc´ı vrcholem v0 . Posloupnost m´a tedy tvar w = z0 , . . . , zk = v0 a podle lemmatu 6 je obr´ acen´ a posloupnost v0 = zk , zk−1 , . . . , z0 = w cestou z v0 do w v grafu G. Tuto cestu nazveme vytˇcen´ a cesta do w. Vytˇcen´a cesta je jednoznaˇcnˇe d´ ana sv´ ym c´ılov´ ym vrcholem. Lemma 8 Je-li E(w) definov´ ano, pak existuje vytˇcen´ a cesta do w a jej´ı d´elka je E(w). D˚ ukaz: Existence vytˇcen´e cesty v0 = w0 , w1 , . . . , wk = w z v0 do w byla zd˚ uvodnˇena v pˇredchoz´ım odstavci. Pro kaˇzdou hranu (wi−1 , wi ) t´eto cesty plat´ı podle lemmatu 6 E(wi ) − E(wi−1 ) = L(wi−1 , wi ), z ˇcehoˇz ihned plyne, ˇze d´elka cel´e cesty je L(w0 , w1 ) + · · · + L(wk−1 , wk ) = [E(w1 ) − E(w0 )] + · · · + [E(wk ) − E(wk−1 )] = E(wk ) − E(w0 ) = E(w) − E(v0 ) = E(w). ♣
ˇ Rekneme,ˇ ze cesta v0 = w0 , . . . , wk = w z poˇca´tku do vrcholu w je definitivn´ı, jestliˇze jej´ı vrcholy w0 , . . . , wk−1 jsou probran´e. Povˇsimnˇete si toho, ˇze vrchol wk nemus´ı b´ yt probran´ y, definitivn´ı cesta tedy m˚ uˇze v´est i do vrcholu, kter´ y nen´ı probran´ y. Je ovˇsem zˇrejm´e, ˇze Lemma 9 Je-li pˇri vstupu do while cyklu v0 = w0 , . . . , wk = w definitivn´ı cesta, pak w je dosaˇzen´y vrchol. D˚ ukaz: Jakmile byl wk−1 oznaˇcen za probran´ y, byla v z´ apˇet´ı prob´ır´ ana hrana (wk−1 , wk ) a tedy se vrchol wk stal dosaˇzen´ ym, pokud jiˇz dosaˇzen´ y nebyl. ♣ Lemma 10 Je-li E(w) definov´ ano, pak vytˇcen´ a cesta do w je definitivn´ı. D˚ ukaz: Plyne ihned z lemmatu 6. ♣ Kl´ıˇcov´e lemma d˚ ukazu spr´ avnosti Dijkstrova algoritmu je 4
Lemma 11 Je-li pˇri nˇekter´em vstupu do while cyklu E(w) definov´ ano, pak E(w) je d´elka nejkratˇs´ı definitivn´ı cesty z v0 do w. D˚ ukaz: Z pˇredchoz´ıho lemmatu plyne, ˇze E(w) je d´elka vytˇcen´e cesty, kter´ a je definitivn´ı. Je tedy tˇreba dok´ azat, ˇze neexistuje definitivn´ı cesta do w, kratˇs´ı neˇz E(w). Na zaˇca´tku v´ ypoˇctu existuje jedin´ a definitivn´ı cesta a to cesta v0 (jedin´ y vrchol, ˇza´dn´a hrana) do v0 a ta m´a d´elku 0 = E(v0 ), tvrzen´ı tedy plat´ı. Uvaˇzujme okamˇziky ukonˇcen´ı prov´adˇen´ı nˇekter´e iterace tˇela while cyklu a pˇredpokl´adejme, ˇze se platnost tvrzen´ı v nˇekter´em z nich poruˇs´ı a uvaˇzujme prvn´ı okamˇzik, kdy se tak stane (pˇred t´ım tedy tvrzen´ı plat´ı). Mohlo doj´ıt bud’ k vytvoˇren´ı nov´e definitivn´ı cesty do w, kter´ a by byla kratˇs´ı neˇz E(w) nebo ke zmˇenˇe E(w). Pokud vznikla nov´a definitivn´ı cesta v0 = w0 , w1 , . . . , wk = w do w, stalo se tak v ˇr´adku 6 algoritmu, kdy byl nˇekter´ y vrchol u oznaˇcen za probran´ y, takˇze tato cesta, kter´ a p˚ uvodnˇe definitivn´ı nebyla, se definitivn´ı stala. V tom pˇr´ıpadˇe muselo b´ yt u = wi pro nˇekter´e i takov´e, ˇze 0 ≤ i < k. Pokud bylo i = k − 1, neboli novˇe probran´ y vrchol u byl pˇredposledn´ı vrchol cesty, pak cesta v0 = w0 , w1 , . . . , wk−1 jiˇz definitivn´ı byla, tedy dle indukˇcn´ıho pˇredpokladu jej´ı d´elka byla alespoˇ n E(wk−1 ) a proto d´elka cel´e cesty v0 = w0 , w1 , . . . , wk = w je alespoˇ n E(wk−1 )+L(wk−1 , wk ), coˇz je hodnota, na kterou je vz´ apˇet´ı upraveno E(wk ) pˇri prob´ır´ an´ı hrany (u, w) = (wk−1 , wk ); k poruˇsen´ı platnosti tvrzen´ı lemmatu by tedy doˇslo jen na okamˇzik, ale do dokonˇcen´ı iterace while cyklu se zase platnost obnov´ı. Pokud by bylo i < k − 1 pak cesta v0 = w0 , w1 , . . . , wi jiˇz definitivn´ı byla a tedy d´elka tohoto u ´ seku byla alespoˇ n E(wi ) podle indukˇcn´ıho pˇredpokladu. Jelikoˇz d´elky hran jsou nez´ aporn´e, d´elka cesty v0 = w0 , w1 , . . . , wk−1 , rovn´a souˇctu d´elky cesty v0 = w0 , w1 , . . . , wi (alespoˇ n E(wi )) a d´elky cesty wi , w1 , . . . , wk (nez´ aporn´ a),je alespoˇ n E(wi ). Jelikoˇz ale vrchol u byl pr´avˇe pˇreˇrazen z dosaˇzen´ ych mezi probran´e, plyne z lemmatu 4,ˇze E(wi ) ≥ E(wk−1 ) a pˇritom E(wk−1 ) je d´elka vytˇcen´e cesty do wk−1 . D´elka cesty w0 , w1 , . . . , wk , coˇz je d´elka cesty w0 , w1 , . . . , wk−1 plus d´elka hrany (wk−1 , wk ), tedy nen´ı niˇzˇs´ı neˇz d´elka cesty C tvoˇren´e vytˇcenou cestou do wk−1 prodlouˇzenou o hranu (wk−1 , wk ). Cesta C ale jiˇz definitivn´ı byla a m´a tedy d´elku alespoˇ n E(wk ) podle indukˇcn´ıho pˇredpokladu, takˇze v tomto pˇr´ıpadˇe nem˚ uˇze doj´ıt k poruˇsen´ı platnosti lemmatu ani na kr´ atk´ y okamˇzik. ♣ Z toho jiˇz okamˇzitˇe plyne Theorem 12 V okamˇziku ukonˇcen´ı v´ypoˇctu Dijkstrova algoritmu je pro kaˇzd´y vrchol w, do kter´eho existuje cesta z poˇca ´tku v0 , E(w) definov´ ano a rovno d´elce nejkratˇs´ı cesty z v0 do w a vytˇcen´ a cesta do w je nejkratˇs´ı cesta do w (nebo jedna z nejkratˇs´ıch cest). D˚ ukaz: Nakonci v´ ypoˇctu nejsou v grafu ˇza´dn´e dosaˇzen´e vrcholy a tedy kaˇzd´a cesta do w je dosaˇzen´ a. ♣ Dijkstr˚ uv algoritmus je velmi bl´ızk´ y Bellman-Fordovu algoritmu; vznikne z nˇeho t´ım, ˇze pro prob´ır´ an´ı nevybereme prvn´ı vrchol ve frontˇe Q, ale vrchol u s 5
nejniˇzˇs´ım E(u) (fronta je tvoˇrena pr´avˇe dosaˇzen´ ymi vrcholy, kter´e jsou identick´e s vrcholy oznaˇcen´ ymi k prob´ır´ an´ı v Bellman-Fordovˇe algoritmu). Jelikoˇz v pˇr´ıpadˇe nez´ apornˇe oznaˇcen´ ych hran m´a dosaˇzen´ y vrchol s nejniˇzˇs´ım E(u) jiˇz tuto hodnotu rovnou vzd´ alenosti od poˇca´tku, nebude jiˇz nikdy prob´ır´ an a proto odpad´ a opakovan´e prob´ır´ an´ı vrchol˚ u, kter´e zp˚ usobuje vˇetˇs´ı vypoˇcetn´ı sloˇzitost Bellman-Fordova algoritmu. Jestliˇze ale se opakovan´e prob´ır´ an´ı vrchol˚ u zak´aˇze, jak je tomu u v´ yˇse podan´e varianty Dijkstrova algoritmu, pak v pˇr´ıpadˇe existence z´ apornˇe ohodnocen´ ych hran m˚ uˇzeme dostat chybn´ y v´ ysledek. Stejnˇe tak se m˚ uˇzeme v ˇr´adku 7 algoritmu omezit (na rozd´ıl od obecn´eho Bellman-Fordova algoritmu) na hrany vedouc´ı do jin´ ych vrchol˚ u neˇz probran´ ych, protoˇze lemma 4 ˇr´ık´ a, ˇze u hrany vedouc´ı do probran´eho vrcholu nem˚ uˇze v grafu s nez´ apornˇe ohodnocen´ ymi hranami nikdy doj´ıt ke zlepˇsen´ı E(w).
6
