Stránka 1 z 1
Kombinatorika a grafy II - Zdeněk Kratochvíl
Napsal: 24. 1. 2010 13:58
od in5inity
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?
Re: Kombinatorika a grafy II - Zdeněk Kratochvíl
Napsal: 25. 1. 2010 22:42
od in5inity
Hmm. Tak to tady asi nikdo moc nečte...
Re: Kombinatorika a grafy II - Zdeněk Kratochvíl
Napsal: 25. 1. 2010 22:59
od Isidor
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
Napsal: 31. 1. 2010 23:47
od 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/~rakdve ... erie_3.pdf
Re: Kombinatorika a grafy II - Zdeněk Kratochvíl
Napsal: 1. 2. 2010 08:44
od Osiris
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ž
|}{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
+1})
. A kdyz se to zprumeruje, vyjde ten vysledek.