Skuska 5.6.2008

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Skuska 5.6.2008

Re: Skuska 5.6.2008

od dobry_den » 31. 5. 2009 22:01

no to jo, ale diky te podmince, ze to je minimalni rez, skoncim okamzite, jakmile se to rozpedne na dve komponenty. a vsechny hrany, ktere jsem odebral, musely byt mezi temito dvema komponentami - jinak by to nebyl minimalni hranovy rez..

Re: Skuska 5.6.2008

od Him » 31. 5. 2009 21:44

dobry_den: posledni otazka, ty ale neodebiras jednu hranu, ale potencialne vic.. nebo mi neco jeste unika?

Re: Skuska 5.6.2008

od dobry_den » 31. 5. 2009 21:42

V pohode. Ze by to bylo i v prednasce, o tom nevim, je to spis takova intuice..

Re: Skuska 5.6.2008

od Him » 31. 5. 2009 21:41

jo, sorry, to je vlastne i v prednaskach.. me uz to dneska nemysli.. radsi koncim

edit: i kdyz, ty ale odebiras vic jak jednu hranu..

Re: Skuska 5.6.2008

od dobry_den » 31. 5. 2009 21:38

No.. Mam nejmensi hranovy rez A. A pri odebrani jedne hrany se mi pocet komponent zvysi maximalne o jednicku...Teda doufam:)

Re: Skuska 5.6.2008

od Him » 31. 5. 2009 21:36

Dobry_den: Jenom otazka, jak vis, ze se to rozpadne jen na dve komponenty?

Re: Skuska 5.6.2008

od dobry_den » 31. 5. 2009 21:32

Jinak k te sedmicce - ja myslim, ze by se na to mohlo jit sporem. Necht existuje A podmozina E(G) takova, ze |A| < n a G(V, E-A) je nesouvisly. Mejme takovou A nejmensi. Potom se graf rozdeli do dvou komponent souvislosti o (n-k) a (n+k) vrcholech. Potom celkovy soucet stupnu v (n-k) komponente by mel byt (n-k)*n - |A| = n^2 - nk - |A|. To ovsem neni mozne - uvazme graf K_(n-k), tedy uplny graf na (n-k) vrcholech. V nem je soucet stupnu (n-k)(n-k-1) = (n^2 - nk) - (n+k(n-k-1)) < (n^2 - nk) - |A|...

Kdyztak komentujte, je to takovy trochu divny...

Re: Skuska 5.6.2008

od beny » 31. 5. 2009 21:15

Him: Diky!;-)

Re: Skuska 5.6.2008

od Him » 31. 5. 2009 19:43

Beny: podle mych odhadu je to dokonce volnejsi nez 2^(|E(G)|), takze to plati.

Preklad toho vzorce je, ze u kazdeho vrcholu mam d moznosti, jestli tam dam okolni hrany - coz je dost overkill.

Re: Skuska 5.6.2008

od beny » 31. 5. 2009 19:30

Him: Mimochodem nevim ani ulohu 5, takze kdybys vedel a chtel naznacit, budu vdecny;-)

Re: Skuska 5.6.2008

od beny » 31. 5. 2009 18:53

Him: Mne zatim taky ne..

Re: Skuska 5.6.2008

od Him » 31. 5. 2009 18:46

Beny: vis, jak dokazat ten 7. priklad? mne se to stale nedari

Re: Skuska 5.6.2008

od Him » 31. 5. 2009 18:41

nj, tak to dopada, kdyz uz clovek micha vrcholovou a hranovou souvislost :)

Re: Skuska 5.6.2008

od beny » 31. 5. 2009 18:29

No s tim vyvracenim bych si nebyl tak jisty :wink: , existuje jediny 1-regularni graf na dvou vrcholech a ten je hranove 1-souvisly, nebot jakmile odeberes jedinou hranu, prestane byt souvisly.

Re: Skuska 5.6.2008

od Him » 31. 5. 2009 16:33

ten 7. priklad by asi mel byt pro n >= 2, jinak to jde rychle vyvratit n = 1.

Nahoru