# Kombinatorika a grafy II - Zdeněk Kratochvíl

<{ForumPost(poster="in5inity", timestamp=2010-01-24 13:58:25)}>
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?
<{/ForumPost}>

<{ForumPost(poster="in5inity", timestamp=2010-01-25 22:42:16)}>
Hmm. Tak to tady asi nikdo moc nečte...
<{/ForumPost}>

<{ForumPost(poster="Isidor", timestamp=2010-01-25 22:59:11)}>
Tak mne z 3. serie chybaju este prve dva priklady :) ale "napoveda" mi jaksi nic podstatne nenapovedala...
<{/ForumPost}>

<{ForumPost(poster="in5inity", timestamp=2010-01-31 23:47:26)}>
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](http://atrey.karlin.mff.cuni.cz/~rakdver/kgii_z09_serie_3.pdf)
<{/ForumPost}>

<{ForumPost(poster="Osiris", timestamp=2010-02-01 08:44:23)}>

 > in5inity wrote: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](http://atrey.karlin.mff.cuni.cz/~rakdver/kgii_z09_serie_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.
<{/ForumPost}>