12.6.2012 Pangrác

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.

12.6.2012 Pangrác

Příspěvekod Alesak » 12. 6. 2012 12:38

Vytáhl jsem si luxusní zadání:

1. definice: KPR
2. věta & důkaz: Menger
3. příklad: kolik existuje čísel, jejichž dekadický zápis je desetimístný a vyskytují se v něm alespoň jednou cifry 0, 1, 2? (bylo to podané méně kostrbatě)

Jako v pohádce.
Alesak
Matfyz(ák|ačka) level I
 
Příspěvky: 15
Registrován: 9. 2. 2011 11:27
Typ studia: Informatika Bc.

Re: 12.6.2012 Pangrác

Příspěvekod Miso » 13. 6. 2012 21:50

Ja som dostal:
1. Definovat SRR
2. Vzorec pre Fibonacciho postupnost
3. Dokazat, ze hranova suvislost grafu, ktory ma minimalny stupen viac ako |V| / 2, je rovna tomu min. stupnu.
U tej trojky chcel dokaz poriadne, nestacilo povedat, ze to obratime hore nohami.
Miso
 

Re: 12.6.2012 Pangrác

Příspěvekod rkapll » 14. 6. 2012 17:47

14.6.2012
1) Definujte vrcholovou souvislost grafu
2) Ukazte a dokazete odhady faktorialu (chtel jenom ty e(e/n)^n)
3) Mejme graf G a \forall H \subseteq G : |E(H)| \le k|V(H)|. Plyne z toho existence orientace tak, že \forall v \in G: deg_{in}(V) \le k?
Pangrác Hint pro 3: použijte systém různých reprezentantů.
rkapll
 

Re: 12.6.2012 Pangrác

Příspěvekod mykem » 18. 6. 2012 14:53

1. Definice hranový souvislosti
2. Odhady kombinačních čísel (dolní je triviální (n/k)^k, horní je (e*n/k)^k) - formulace a důkaz
3. Nějakej příklad s KPR, analogie podmínky existence čtveřice
mykem
Matfyz(ák|ačka) level II
 
Příspěvky: 80
Registrován: 13. 2. 2011 18:52
Typ studia: Informatika Ph.D.

Re: 12.6.2012 Pangrác

Příspěvekod Danstahr » 27. 6. 2012 14:11

27.6.2012

  • Definice hranoveho rezu

  • Pocet hran v grafu bez ctyrcyklu

  • Ukazat, ze pokud je a(x) vytvorujici funkce posloupnosti, pak je a(x)/(1 - x) vytvorujici funkce posloupnosti castecnych souctu posloupnosti a.
Danstahr
Matfyz(ák|ačka) level I
 
Příspěvky: 12
Registrován: 26. 1. 2012 18:50
Typ studia: Informatika Bc.
Login do SIS: 62601319


Zpět na DMI011 Kombinatorika a grafy I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron