Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : Kombinatorika A Grafy / Zkouška LS 2008
Přihlášení:  Heslo:  
Matfiz: KombinatorikaAGrafy/ZkouškaLS2008 ...
Hlavní Stránka | Seznam Stránek | Poslední Změny | Poslední Komentované | Uživatelé | Registrace |
Toto je stará verze stránky KombinatorikaAGrafy/ZkouškaLS2008 z 2008-06-17 16:18:10..

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.


Zkouska 17.6.

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.
Hodnoceni:
Kazdy priklad za sest bodu, ctyry priklady.
dvacet a vys jednicka, na trojku stacilo myslim deset bodu ale nevim, at nekdo doplni.
7,5 a mene uz byla ctyrka bez moznosti dozkouseni.
Zadani:

  1. Dokazte nebo vyvratte: Necht T je strom na aspon 3 vrcholech nemajici zadny vrchol stupne 2 a necht C je kruznice prochazejici vsemi listy stromu T (a nemajici zadny dalsi vrchol). Potom pridanim hran kruznice C ke stromu T vznikne 3-souvisly 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.
  2. Dokaz nebo vyvrat nasledujici tvrzeni:
  1. Urcete maximalni tok v siti o osmi vrcholech (z nichz jeden je zdroj a jeden stok), pricemz z kazdeho vrcholu do kazdeho jineho vrcholu vede orientovana hrana majici kapacitu 12. Odpoved zduvodnete!
    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.
  2. Zformuluj a dokaz Hallovu vetu. (O tom si radeji prectete jinde :) )

Hodne stesti tem, kteri se na zkousku teprve chystaji Karl


 
Na stránce nejsou žádné soubory. [Zobrazit soubory (formulář)]
Na stránce nejsou žádné komentáře. [Zobrazit komentáře (formulář)]