od Krakonoš » 18. 6. 2009 12:11
Takže Pangrác 18.6:
1) Definovat k-souvislosti a ekvivalentní podmínky (Ford-Fulkerson, Menge),
2) Nějaká tvrzeníčka okolo Hallovy věty (ve formulaci, obměny Hallovy... nic těžkého)
3) Co vím o odhadech kombinačních čísel - potom chtěl dokázat jeden (dolní nebo horní) odhad na kombinační číslo \binom{2m}{m}... Tam jsem se trochu zadrh, nakonec s malou nápovědou to dal, proto taky jsem dostal bonus:
Bonus:
Tvrzeníčko na Ramseyovky... Prakticy byl neúplný graf, \forall n \exists N \in \N že \forall G(V,E) V=N \forall c: E -> {1,2} \exists W \subsetq V kde |V| >= n takový, aby indukovaný podgraf W měl stejnou barvu...
To tvrzení bylo jednoduché, stačí doplnit na úplný graf, přidat hrany a obarvit je třetí barvou... Potom použiju ramseyovku pro 3 barvy a stačí říct, že pokud má ten graf barvu 1, 2 tak je to ok, pokud 3, tak je to vlastně prázdný graf a pro něj platí cokoliv...
Jinak byl Pangrác jako vždy hodný
Takže Pangrác 18.6:
1) Definovat k-souvislosti a ekvivalentní podmínky (Ford-Fulkerson, Menge),
2) Nějaká tvrzeníčka okolo Hallovy věty (ve formulaci, obměny Hallovy... nic těžkého)
3) Co vím o odhadech kombinačních čísel - potom chtěl dokázat jeden (dolní nebo horní) odhad na kombinační číslo \binom{2m}{m}... Tam jsem se trochu zadrh, nakonec s malou nápovědou to dal, proto taky jsem dostal bonus:
Bonus:
Tvrzeníčko na Ramseyovky... Prakticy byl neúplný graf, \forall n \exists N \in \N že \forall G(V,E) V=N \forall c: E -> {1,2} \exists W \subsetq V kde |V| >= n takový, aby indukovaný podgraf W měl stejnou barvu...
To tvrzení bylo jednoduché, stačí doplnit na úplný graf, přidat hrany a obarvit je třetí barvou... Potom použiju ramseyovku pro 3 barvy a stačí říct, že pokud má ten graf barvu 1, 2 tak je to ok, pokud 3, tak je to vlastně prázdný graf a pro něj platí cokoliv...
Jinak byl Pangrác jako vždy hodný :-)