Kombinatorika a grafy II - Zdeněk Kratochvíl

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: Kombinatorika a grafy II - Zdeněk Kratochvíl

Re: Kombinatorika a grafy II - Zdeněk Kratochvíl

od Osiris » 1. 2. 2010 08:44

in5inity píše:Nemáte nikdo tip jak řešit příklady 4 a 5 ze 3. série příkladů?
Díky.
http://atrey.karlin.mff.cuni.cz/~rakdve ... erie_3.pdf
No, ten 5. příklad je podobný příkladu z předmětu Pravděpodobnostní metoda. Průměrný stupeň je k a dá se dokázat (pravděpodobnostní metodou), že nezávislá množina je větší nebo rovna, než \frac{|V(G)|}{k+1}. Idea dukazu: vezmes nahodnou permutaci vrcholu a jedes zleva doprava: pokud vrchol nema hrany s aktualni NM, pridej ho do NM, jinak nedelej nic. Pak stredni hodnota poctu vrcholu v NM je \sum\limits_{v\in V}\frac{1}{deg(V)+1}. A kdyz se to zprumeruje, vyjde ten vysledek.

Re: Kombinatorika a grafy II - Zdeněk Kratochvíl

od in5inity » 31. 1. 2010 23:47

Nemáte nikdo tip jak řešit příklady 4 a 5 ze 3. série příkladů?
Díky.
http://atrey.karlin.mff.cuni.cz/~rakdve ... erie_3.pdf

Re: Kombinatorika a grafy II - Zdeněk Kratochvíl

od Isidor » 25. 1. 2010 22:59

Tak mne z 3. serie chybaju este prve dva priklady :) ale "napoveda" mi jaksi nic podstatne nenapovedala...

Re: Kombinatorika a grafy II - Zdeněk Kratochvíl

od in5inity » 25. 1. 2010 22:42

Hmm. Tak to tady asi nikdo moc nečte...

Kombinatorika a grafy II - Zdeněk Kratochvíl

od in5inity » 24. 1. 2010 13:58

Kdo jste již byli na zkoušce, jaké to bylo? Napište své dojmy, ať víme, co máme čekat.
Dále potom, někteří z nás úspěšně vyřešili příklady 3. série. Co vy ostatní, jak na tom jste?

Nahoru