Fórum studentů MFF UK

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 ?

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.

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)

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
[code]
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)[/code]

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