Kombinatorika a grafy – zkouška LS 2008
Přehled zadání
Zadání z šesti níže uvedených termínů (tedy do 5. 6.) v PDF
Zkouška 15. 5., 26. 5. 2008
Na fóru: 
15. 5., 26. 5.
Zkouška 2. 6. 2008
1. určit počet koster zadaného grafu
2. máme zadanou funkci sqrt(1 – 3x), v její příslušné řadě je koeficient a0 celé nezáporné číslo. Úkolem je zjistit, který další koeficient je nezáporný a který další koeficient je celočíselný.
3. v daném bipartitním grafu nalézt největší párování
4. sestrojit projektivní rovinu řádu 3
5. důkaz: pro každé n > 2 platí, že systém n různých množin o velikosti n – 2 má systém různých reprezentantů
6. důkaz: pro každý vrcholově 2-souvislý graf o n vrcholech platí, že má alespoň n různých koster
7. důkaz: máme čísla od 1 do n obarvená 3 barvami => existují čísla x, y, z stejné barvy taková, že splňují x + y = z
8. napsat větu z přednášky, která se nám zdála nejlehčí a napsat proč.
Z příkladů 5, 6, 7 stačilo mít dva, bodování pravděpodobně jako na předchozích termínech:
příklady 1, 2, 3, 4 po 5 bodech, 5, 6, 7 dohromady za 20, celkem tedy 40 bodů a na trojku by měla stačit zhruba polovina.
Důležité je u všech příkladů popsat postup (např. u příkladu 3 nejen napsat nalezené párování, ale také zdůvodnit, proč je největší).
Kdo není po písemné části spokojený se známkou, může jít na ústní, kde se dá známka zlepšit až o 2 stupně, ale je potřeba dobře umět důkazy.
– Zdeněk
Na fóru: 2. 6.
Zkouška 3. 6., 5. 6. 2008
Na fóru: 3. 6., 5. 6.
Zkouška 17. 6. 2008 – doc. Valtr
U Valtra vypadala zkouska mirne odlisne nez u Kratochvila, v zadani byly pouze ctyry priklady, pak to dve hodiny opravoval a potom, kdo nebyl spokojen se znamkou mohl jit na prezkouseni. (Ja dostal za jedna hned takze nevim jak dozkouseni vypadalo.) Co jsem si stacil vsimnout tak z pisemne casti bylo par jednicek, vetsina dvojek a trojek a jedna (mozna vic, nevim) ctyrka. Prislo mi to dost jednoduche ikdyz to bylo v podstate zamerene pouze na HK a miru souvislosti, potom hallova veta no a hodne jednoduchy priklad na toky. Zadne vytvorujici fce, kostry grafu nebo KPR a latinske ctverce. — Karl
4 příklady po 6 bodech. Bodování (asi tak nějak – neručím za správnost):
- 1 – 20–24 (výborně)
- 2 – 16–19,5 (velmi dobře)
- 3 – 12–15,5 (dobře)
- 4+ – 8–11,5 (ústní douzkoušení)
- 4- – 0–7,5 (příště)
- Dokažte nebo vyvraťe: Nechť T je strom na alespoň 3 vrcholech nemající žádný vrchol stupně 2 a nechť C je kružnice procházející všemi listy stromu T (a nemající žádný další vrchol). Potom přidáním hran kružnice T vznikne 3-souvislý graf.
- Ja jsem rozborem pripadu ukazal ze pro kazdy dva vrcholy existuji tri vrcholove disjunktni cesty, dalo se to pry delat vyhodne i primo z definic 3-souvislosti nebo dukazem, ze pri odebrani jakehokoli vrcholu je graf aspon dvousouvisly. — Karl
- PLATÍ – Lze dokázat rozborem případů. Chceme ukázat, že když vyhodíme libovolný vrchol, dostaneme 2-souvislý graf. Máme kružnici na listech a strom uvnitř. Vyhodíme vrchol na kružnici a rozebíráme, co se stane. Nebo vyhodíme vrchol ze z vnitřích vrcholů stromu a zas rozebíráme. Chce si to nějak rozmyslet. — Bohouš
- Dokažte nebo vyvraťte každé z následujících tvrzení:
- a) Má-li graf hamiltonovskou kružnici, potom jeho vrcholová souvislost je alespoň 2.
- PLATÍ celkem triviálně. Když odebereme jeden libovolný vrchol, v grafu zůstane hamiltonovská cesta, tedy graf zůstane souvislý. To je definice 2-souvislosti. — Bohouš
- b) Má-li graf dvě navzájem diskunktní hamiltonovské kružnice, potom je 3-souvislý.
- NEPLATÍ – Stačí ukázat, že když z nějakého protipříkladového grafu odebereme dva vrcholy, přestane být souvislý. Jako protipříklad kreslil doc. Valtr nějaký graf, který vypadá jako kružnice, která má dvě polokoule stýkající se na dvou vrcholech {u,v}, které budeme vyhazovat. Jedna HK vede okolo, druhá uvnitř: z vrcholu u polokoulí, přes vrchol v, pak druhou polokoulí zpět do u a přitom obejde všechny vrcholy. — Bohouš
- c) Má-li graf všechny stupně sudé a větší než 2, potom má hamiltonovskou kružnici.
- NEPLATÍ – když neuvažujeme souvislost grafu (v zadání není), lze jako protipříklad použít třeba dva obalené pentagramy (K_5) vedle sebe (vrcholy mají stupeň 4). Jestliže souvislost požadujeme, spojíme tyto pentagramy tak, že sdílejí právě jeden vrchol (ten bude mít stupěň 8, ostatní 4). Lze vymyslet i takovou čtyřkytičku, která má jeden centrální uzel, přes který HK nemůže vést vícekrát (to by chtělo nakreslit...). — Bohouš
- Určete maximální tok v síti o osmi vrcholech (z nichž jeden je zdroj a jeden je tok), přičemž z každého vrcholu do každého jiného vrcholu vede orientovaná hrana mající kapacitu 12. Odpověď zdůvodněte!
- Maximalni tok je 7*12=84 (vetsi byt nemuze, je to maximalni kapacita hran vychazejici ze zdroje), jak se ho da dosahnout jsem uvedl na priklade. — Karl
- 84 = 7*12. Je to 12 po přímé hraně zdroj->stok a 6*12 za cestičky přes zbylé vrcholy. «Zdůvodněte» -> najít minimální řez (?). — Bohouš
- Zformulujte a dokažte Hallovu větu. Viz skripta Valla-Matoušek, tam je to pěkně popsané a pokreslené.
Hodne stesti tem, kteri se na zkousku teprve chystaji. — Karl
Příklad dozkoušení:
- Latinské čtverce – definice, napsat nějaké tvrzení (třeba doplnění latinského obdélníku na čtverec), zhruba říct, jak se to dokazuje.
- Ramseyova věta – ústně zformulovat.
Lze to dát z 8 bodů na trojku, i když se pořádně naučíte jen důkaz Hallovy věty, pár definic, tvrzení a znění vět a máte trochu štěstí a pevných nervů. Ty obrázky jsou jednoduché, ale chce to v tom vidět, nejlépe ještě před odevzáním zkoušky. :) A ještě bych doporučil, když si nejste jisti, radši tam něco napište či nakreslete, možná to je správně (a bodík se může hodit). «Skicák» na grafy jsem si nechal a pak jsem zjistil, že jsem ten jeden protigraf měl vlastně dobře, jen se na to podívat o minutu déle. — Bohouš
