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.
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!
