Paralelni algoritmy
Napsal: 31. 5. 2009 20:28
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
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
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)Vdaka
to admin: je mozne zalozit vlakno venovane tomuto predmetu? thx