od Osiris » 1. 2. 2010 08:44
No, ten 5. příklad je podobný příkladu z předmětu Pravděpodobnostní metoda. Průměrný stupeň je
a dá se dokázat (pravděpodobnostní metodou), že nezávislá množina je větší nebo rovna, než
. 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
. A kdyz se to zprumeruje, vyjde ten vysledek.
[quote="in5inity"]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/~rakdver/kgii_z09_serie_3.pdf[/quote]
No, ten 5. příklad je podobný příkladu z předmětu Pravděpodobnostní metoda. Průměrný stupeň je [latex]k[/latex] a dá se dokázat (pravděpodobnostní metodou), že nezávislá množina je větší nebo rovna, než [latex]\frac{|V(G)|}{k+1}[/latex]. 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 [latex]\sum\limits_{v\in V}\frac{1}{deg(V)+1}[/latex]. A kdyz se to zprumeruje, vyjde ten vysledek.