# 26.1. Pangrác

<{ForumPost(poster="cre8or", timestamp=2011-01-26 11:05:49)}>
Zkouska: kazdy si vylosoval svoje zadani, nevim do jake miry unikatni. Ja tam mel:  
1) definujte indukovany podgraf a urcete pocet neisomorfnich indukovanych podgrafu $P_4$ (spravna odpoved: 6)  
2) urcete nejlepsi dolni odhad poctu neisomorfnich grafu na n vrcholech a dokazte to  
3) v loterii se losuje 5 cisel z 10, sazkar hada 5 cisel. Urcete stredni hodnotu poctu uhadnutych cisel. (spravna odpoved: 2,5)  
Casu dost, jinak se na nic dalsiho nepta.
<{/ForumPost}>

<{ForumPost(poster="noox", timestamp=2011-01-28 08:56:46)}>
Ja vylosovala:  
  
1.) Definice sledu, tahu a cesty. Vztah mezi nimi.  
2.) Veta o maximalnim poctu hran rovinneho grafu + dukaz.  
3.) Mame osm karet ozacenych 1, 2, .. 8 a ctyri obalky oznacene A, B, C, D. Kolik je moznosti pokud:  
 a) V kazde obalce je prave jedna karta (ctyri zbydou). (= 8*7*6*5)  
 b) V kazde obalce je libovolny pocet karet, ale zadna nezbyde. (= 4^8)  
 c) V kazde obalce jsou prave dve karty. (= (8 nad 2) * (6 nad 2) * (4 nad 2))  
  
Zapomnela sem na jeden predpoklad u te vety, tak jsem dostala doplnujici otazku: definovat stredni hodnotu realne nahodne veliciny a rict jenom zneni Markovovy nerovnosi.  
Takze nakonec za 1. :)  
  
Jinak je to pohodova zkouska, casu kupa a Pangrac je moc hodnej a v nicem se nerype, za pul hodky jste klidne venku. :)
<{/ForumPost}>

<{ForumPost(poster="kralik", timestamp=2011-02-01 23:25:25)}>

 > cre8or wrote:
 > 2) urcete nejlepsi dolni odhad poctu neisomorfnich grafu na $n$ vrcholech a dokazte to

Co tady myslí tím "dokažte to"? Dokázat, že tech grafů opravdu je alespoň tolik, anebo i to, že ten odhad je nejlepší možný?
<{/ForumPost}>

<{ForumPost(poster="cre8or", timestamp=2011-02-02 23:23:45)}>

 > kralik wrote: Co tady myslí tím "dokažte to"? Dokázat, že tech grafů opravdu je alespoň tolik, anebo i to, že ten odhad je nejlepší možný?

No ja jsem v tom nehledal nic slozityho - proste stacilo napsat odhad, ze ten pocet je aspon $\frac {2^{n \choose 2}} {n!}$, coz je vcelku zrejmy - citatel je pocet vsech grafu na $n$ vrcholech a vzhledem k tomu ze isomorfismus je bijekce a tech je $n!$ ... Uznal mi to bez vyhrad a dikybohu jsme neresili, jestli existuje lepsi odhad :-)
<{/ForumPost}>

<{ForumPost(poster="kralik", timestamp=2011-02-03 14:13:52)}>
Ok, díky za info. No lepší odhad afaik není, oni totiž v Kapitolách mají k tomu důkaz, kdy se to celý zlogaritmuje se základem 2 a z toho to vyjde. Ale tak to evidentně nemusíme.
<{/ForumPost}>

<{ForumPost(poster="Davpe", timestamp=2011-02-03 21:09:12)}>

 > kralik wrote:Ok, díky za info. No lepší odhad afaik není, oni totiž v Kapitolách mají k tomu důkaz, kdy se to celý zlogaritmuje se základem 2 a z toho to vyjde. Ale tak to evidentně nemusíme.
 S Maresem jsme treba ten dukaz delali ;) Ale jak rikas, je to jen zlogaritmovani ;)
<{/ForumPost}>