Paralelni algoritmy

Lado
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 29. 1. 2007 11:42

Paralelni algoritmy

Příspěvek od Lado »

Ahoj,
mam mensi problem s dokazom vety o 2-suvislych komponentach grafu.
Ide o siedmu prednasku, posledny dokaz. Konkretne o stranu 19 ( ak sa to chce niekomu studovat :) )
Vobec nechapem cast o pomocnom grafe

Kód: Vybrat vše

graf G ( V, E )
G' = ( E, E'' ) – vrcholy sú hrany grafu G,
T = ( V, E' ) je kostra, p(v) je otec vrcholu v; do E'' dáme hrany tvaru
(i) { { w, p(w) }, { w, u } }, ak { w, u } patri E \ T, u < w a w nie je koren
(ii) { { w, p(w) }, { x, p(x) } }, ak { w, x } patri E \ T, w a x sú
neporovnatelné (nie je jeden následníkom druhého)
(iii) { { w, p(w) }, { p(w), p(p(x)) } }, ak ani w, ani p(w) nie je koren a
existuje hrana { z, y} patriaca E \ T taká, že z je následníkom w a y nie
je následníkom p(w)
Moze mi niekto vysvetlit, co za hrany to vytvarame a preco? Dalej v slajdoch je uz len nieco o tom, ako ich vytvorime, ale nie preco.
Vdaka

to admin: je mozne zalozit vlakno venovane tomuto predmetu? thx
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Paralelni algoritmy

Příspěvek od Osiris »

Stručně řečeno, zkonstruujeme nový graf, jehož komponenty souvislosti jsou dvousouvislé komponenty původního grafu.

Hrany typu i) spojují kostrové hrany s nekostrovými (abychom měli komponenty dvousouvislosti úplné). Hrany typu ii) odpovídají hranám, které vytvářejí cykly - spojí koncové hrany kostry vytvářející s tou hranou cyklus. Hrany typu iii) se "šplhají" nahoru po kostře tak dlouho, dokud tvoří cyklus.
Osiris
Lado
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 29. 1. 2007 11:42

Re: Paralelni algoritmy

Příspěvek od Lado »

Vdaka :) Pekne povedane, lepsie ako tymi pismenkami

Inak, v (i) pise, ze u < w a v (ii) ze su neporovnatelne. O slajd skor hovori nieco o preorder. Plati, ze v (i) je u < w, alebo tam malo byt u je naslednik w ?
Odpovědět

Zpět na „I1 Ostatní Teoretická informatika“