2-souvislost a kontrakce

[loki]

Ahoj, nevim si rady s nasledujicim prikladem:

Dokazte, ze v kazdem vrcholove 2-souvislem grafu s vice jak 4mi vrcholy existuje hrana, jejich kontrakce zachovava vrcholovou 2-souvislost.

Dik

[Dan]

Skusil by som pouzit Usate lemma ... posledne pridane uxo sa da kontrahovat ..

[laliebijard]

Ja by som povedal, ze je to obmena dokazu Lemma o kontrakcii, ale usatym lemma to ide zrejme este lahsie.

[MyS]

Kdyz uz jsme u tech otazek;).... nevedel by nekdo, jak na tohle?
"Ve vrcholově k-souvislém grafu leží každých k vrcholů na kružnici."

[hydrant]

Skusil by som pouzit Usate lemma ... posledne pridane uxo sa da kontrahovat ..

tiez som skusal, ale predstav si nasledujuci pripad.... mas jednu velku kruznicu. Pridas ucho ktore nema vlastne vrcholy iba spoji nejake dva (na povodnej kruznici) hranou. Tuto hranu ked potom skontrahujes vznikne ti nieco ako maslicka |><| .... -> graf sa stane vrcholovo jednosuvisly. Takze nemozes odoberat posledne pridane ucho.


ja idem na skusku v stredu, rad by som predebatoval nejake priklady. Myslim si, ze som dokazal vyriesit tieto A1 A2 A3 B1 B2 B3... ostatne by som potreboval vediet... ak ich niekto viete napiste prosim. Ak chce niekto vediet postup pri tych co som napisal tak napiste... asi nemam cas aby som pisal vsetko, hlavne ak to nikoho nezaujima.

hydrant

[WOW]

Skusil by som pouzit Usate lemma ... posledne pridane uxo sa da kontrahovat ..

tiez som skusal, ale predstav si nasledujuci pripad.... mas jednu velku kruznicu. Pridas ucho ktore nema vlastne vrcholy iba spoji nejake dva (na povodnej kruznici) hranou. Tuto hranu ked potom skontrahujes vznikne ti nieco ako maslicka |><| .... -> graf sa stane vrcholovo jednosuvisly. Takze nemozes odoberat posledne pridane ucho.


ja idem na skusku v stredu, rad by som predebatoval nejake priklady. Myslim si, ze som dokazal vyriesit tieto A1 A2 A3 B1 B2 B3... ostatne by som potreboval vediet... ak ich niekto viete napiste prosim. Ak chce niekto vediet postup pri tych co som napisal tak napiste... asi nemam cas aby som pisal vsetko, hlavne ak to nikoho nezaujima.

hydrant

mohl bys teda pls napsat reseni B2 a B3 ?
diky

[loki]

Ja by som povedal, ze je to obmena dokazu Lemma o kontrakcii, ale usatym lemma to ide zrejme este lahsie.

no ja nepochopil poradne ani dukaz lematu o kontrakci, jinac paralelu vidim jasne.
jak je ukazano nize, lema o usich by se asi muselo hodne rozsirit - v jakem poradi to delat

protoze kdyz z trojuhelniku udelas nejdriv sestiuhelnik a jako posledni propojis dva protilehle vrcholy, vznikne ti po kontrakci teto hrany maslicka. zkousel jsem najit pravidla, podle kterych se maji ty usi pridavat, ale nejak mi to nedocvaklo :/

[hydrant]

B3: mali sme vetu (dosledok hallovky), ktora hovori "ak mam bipartitny graf (A U B, E) a pre vsetky a z A, b z B plati deg(a) >= deg(b) potom existuje parovanie velkosit |A|

graf je bipartitny a k-regularny ==> |A| = |B|, veta ktoru som napisal je splnena, pretoze je k-regularny ==> existuje parovanie F, ktore je perfektne. teraz z povodneho grafu vyhodim hrany ktorimy som paroval (tj G1 = G \ F)
novy graf je k-1 regularny ==> znovu pouzijem vetu najdem p. p. odstanim hrany ... atd. tymto sposobom najdem k disjunktnych perfektnych parovani.
tym je to dokazane

B2: toto neviem obkecat moc formalne, ale myslim ze takato myslienka by stacila (dufam ze som pochopil zadanie, pretoze na webe je napisane dost nejasne): Tvrdenie bude splnene pre dostatocne velke N... ja som ho zvolil N=max(n, k+1)
1) AK je vsetkych N bodov na jednej priamke => n bodov je tiez na jednej priamke a implikacia je splnena.
2) AK nie su vsetky na jednej priamke => tri body tvoria trojuholnik ==> uz som spotreboval 3 smery a 3 body. => kazdy dalsi bod prida minimalne jeden novy smer... ja ich musim este pridat k-3+1 (tak aby ich bolo N) no a kedze kazdy bod prida minimalne jeden smer. Vsetkych N bodov vytvara spolu minimalne k+1 smerov. ==> prva cast implikacie nie je splnena takze nemusi byt splnena ani ta druha.
(teda jedine mnoziny M ktore splnili lavu stranu implikacie boli take, kde vsetky body lezali na jednej priamke)

ps: ak tomu rieseniu vobec nechpete, mozno som pochopil zle zadanie, tak ukazte kde mam chybu v uvahe

hydrant

[laliebijard]

Ja by som povedal, ze je to obmena dokazu Lemma o kontrakcii, ale usatym lemma to ide zrejme este lahsie.

no ja nepochopil poradne ani dukaz lematu o kontrakci, jinac paralelu vidim jasne.
jak je ukazano nize, lema o usich by se asi muselo hodne rozsirit - v jakem poradi to delat

protoze kdyz z trojuhelniku udelas nejdriv sestiuhelnik a jako posledni propojis dva protilehle vrcholy, vznikne ti po kontrakci teto hrany maslicka. zkousel jsem najit pravidla, podle kterych se maji ty usi pridavat, ale nejak mi to nedocvaklo :/

Tak ja to mozem skusit napisat, neviem, nakolko to bude spravne:
Pre spor predpokladajme, ze pre vsetky e<-E(G) G.e nie je 2-suvisly. T.j. ex. A podmnozina V(G.e) tak, ze A je rez a |A|<2. Lenze vrchol xe (ktory vznikne kontrakciou hrany e) musi patrit do A, inak A je rez v G - spor. Takze |A|=1.
=> Kazda hrana e={u, v} tvori v G vrcholovy rez. Zvolme taku e={u, v}, ze odobranim vrcholov u a v z grafu G dostaneme max. komponentu suvislosti K. Dostaneme k tomu este jednu komponentu suvislosti Z. Z vrcholu u, alebo z vrcholu v musi viest nejaka hrana f do Z. Zoberme vrcholy tejto hrany a ked ich odoberieme, dostaneme komponentu suvislosti vacsiu ako K, t.j. K nie je maximalna - spor.

[Che]

=> Kazda hrana e={u, v} tvori v G vrcholovy rez.

Myslím, že to máš správně, jenom mně napadlo, jestli v tomhle momentě nestačí říct, že hrana {u,v} tvoří v G hranový řez, takže Ke(G) = 1 a to je spor s tím, že pro každý graf platí: Kv(G) <= Ke(G)?
Kv ... vrcholová souv. Ke ... hranová souv.