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

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

Čtyřek bylo mnohem víc, aspoň těch 4+, to mohlo být takových šest lidí (4- nevím). Viz ještě poznámky k dozkušování níže. — (/Adam Nohejl Adam))

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
  - U podobných věcí je dobré udělat rozbor příkladů opravdu podrobně (asi jako byste psali skripta;)). Já jsem popsal přes půl stránky přípravnými úvahami (tzn. zdůvpdněním, že každý vrchol bude mít stupeň aspoň 3 apod.) a rozbor případů (proč jsou tam fakt tři cesty) jsem, uznávám, odbyl, protože už mi to přišlo dost přesvědčivé. Ale nebylo, takže jen půlka bodů, totéž u třetího příkladu. Možná záleží i na tom, kdo vám to zrovna bude opravovat, ale jakmile máte nápad, jak to dokázat a uvědomíte si, že rozebrat případy je třeba, byly by to body lacino získané. — Adam
- 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š
    Protipříklad:
    — Martin Vseticka
- 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š
- Jde to takhle:
  \forall v \in V(K_8)\;\deg_{K_8} v = 7 (atd.), tedy tok nemůže být větší než 7 * c = 7 * 12. Pak už jen stačí najít tok velikosti 7 * 12 a to lze velmi snadno (hledáte sedm hranově disjunktních cest):
  
  No a protože jste tok našli a víte, že vyšší být nemůže, tak je prostě maximální. Tečka. Jindy může být výhodné hledání řezu, ale tady bylo řešení dost přímočaré takhle.
  Bohužel na zkoušce mi chyběl ten obrázek, tak si to teď vynahrazuju i s barvičkama;). — Adam
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

Dozkušování u Valtra

Valtr rozdělil lidi více méně na tři skupiny, ty co si jen zlepšovali známku (3 na 2, 2 na 1), byli jsme dva, pak čtyřkaře, kterým chybělo fakt málo, a pak ty, co jim chybělo trochu víc. Čtyřkařů mohlo být celkem tak šest(?). Trochu překvapivě dával přednost lidem s více body / lepší známkou, i když to nutně neznamenalo, že ve finále odešli dřív, viz příklady níže.

Příklad dozkoušení (ze 4 na 3)

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.

Příklad dozkoušení (ze 3 na 2; z 2 na 1 bylo, myslím, obdobné)

Ramseyova věta — formulovat všechny možné Ramseyovy věty (případně z trochou omáčky), ukázat ekvivalenci symetrické a nesymetrické, dokázat tu hlavní (a možná něco dalšího, dál jsem se nedostal)
Latinské čtverce — formulovat větu o NOLČ a dokázat (spolu s tím definovat potřebné pojmy LČ, jejich ortogonalita) (určitě by následovalo něco dalšího, kdybych předtím nedělal Ramseyovku, viz níže)

Probíhalo to takhle: Valtr mi dokonce dal nejdřív vybrat, jestli chci radši Ramseyovu větu nebo latinské čtverce. Dostal jsem papíry a měl dost času na přípravu. (Nějaké vylepšování toho, co jsem měl v písemce ho nezajímalo.) Vybral jsem si ramseyovku, protože jsem měl i důkaz docela v čerstvé paměti, ale chyba lávky, při dokazování jsem se dostal do slepé uličky: Měl jsem schéma té indukce (a la dynamické programování), správně volené velikosti grafů v indukčním kroku, ale prostě jsem nedokázal správně rozebrat případy, aby to do sebe zapadlo. Ono to vypadá strašně samozřejmě (když jste na přednášce nebo čtete skripta), že se má zvolit libovolný vrchol a zbytek rozdělit na jeho sousedy a ty ostatní (resp. spojené červenou/modrou hranou), ale kupodivu se mi podařilo najít nepřeberné množství jiných postupů, z nichž žádný nevedl k cíli. (Docela nadějně vypadalo například vybrání vrcholu s nejnižším, resp. nejvyšším, stupněm a rozdělení zbytku na část, která obsahu co největší úplný graf, resp. nezávislou množinu, a zbytek.) Valtr mi trochu vynadal, že jsem si vybral větu, kterou mají všichni studenti rádi a má hezký důkaz a pak tohle, pak mi dal ty latinské čtverce. Ty jsem naopak k mému vlastnímu údivu dal dohromady během pár minut. Trochu jsem si to zkomplikoval, ale byl jsem rád, že když už jsem se učil důkazy, tak jsem je měl komu předvést a nakonec jsem, myslím zaslouženě, dostal dvojku. — Adam

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š