# 14.1. Zkouska Kral

<{ForumPost(poster="tikiri", timestamp=2008-01-17 10:33:17)}>
1. Definujte pojem 2-souvisleho grafu. Rozhodnete, kdy je uplny bipartitni graf K_m,n 2-souvisly. (Zduvodnete)  
2. Zformulujte a dokazte Spernerovu vetu o maximalni velikosti systemu nezavislych podmnozin n prvkove mnoziny.  
3. Ukazte, ze nasledujici graf G=(V,E) neni rovinny, kde V={1,2, ... , 15}, E={{i,j} nalezici (V nad 2): i-j je sude a |i-j|>=4}.  
4. Kolik koster ma uplny bipartitni graf K_2,n?  
-----------------------------------------------------------------------------------------------------------------------------------------------------  
**Reseni pro zajemce:**  
1. Graf G nazveme 2-souvisly, pokud ma alespon 3 vrcholy a odebranim libovolneho z nich zustane G souvisly.  
    Uplny bipartitni graf K_m,n je 2- souvisly pokud m>1 a n>1.  
2. Spernerova veta rika, ze maximalni pocet nezavislych podmnozin je (n nad dolni cast(n/2)).  
Dukaz zde psat nebudu, ale doporucuji naucit se ho opravdu dobre, protoze Kral se pekne stoural a kvuli teto vete mam za 2. **Spernerova veta je jinak temer v kazdem testu.**  :evil:   
3. Graf G je nesouvisly, obsahuje-li jako podgraf K_5 nebo K_3,3. Nas graf si nakreslete a staci, kdyz budete kreslit pro licha cisla. Po pozornejsim prozkoumani uvidite, ze na vrcholech 15, 1, 3, 7, 9, 11 se nachazi K_3,3.  
4. Ty dva vrcholy si oznacime V1 a V2. Libovolne je spojim s jednim z n bodu, aby byl graf souvisly a dole mi uz zbyde jenom (n-1) vrcholu. Nyni se mohu u kazdeho z techto vrcholu rozhodnout, zda-li kazdy z tech (n-1) vrcholu spojim s V1 ci V2. Vysledek je n*2^(n-1).  
-----------------------------------------------------------------------------------------------------------------------------------------------------  
Jeste jedna poznamka - Kralovi nestaci neco jaks taks vysvetlit, docela se rejpe. Mne rekl, ze ten dukaz mam naucenej zpameti nebo ho neumim vysvetlit a neuznal mi ho. Ale mam to a to je hlavni. Ke zkousce mi stacilo podivat se na pisemky minulych let, 1 a 4 priklad uz se vyskytly ve stejnem zneni drive, ale radsi se naucte vsechno, ja mela asi i dost stesti.  :)   
  
Preji hodne stesti!  8)
<{/ForumPost}>