Kombinatorika a grafy - pangrac
Kombinatorika a grafy - pangrac
kategorie komb a grafy u nas v ls chybi, chci se hlavne zeptat tech kdo uz byli na zkousce u pangrace jak to vypadalo na co se ptal a tak..diky.
zkouska 4.6.
Moje zadani:
1.definujte co to je retezec a antiretezec
2. pokud je graf vrcholove k-souvisly, potom pro kazdou k-tici vrcholu existuje kruznice, na ktere lezi. dokazte!
plati podobne tvrzeni i pro k+1 tice?
3. co vite o principu inkluze a exkluze.
1.definujte co to je retezec a antiretezec
2. pokud je graf vrcholove k-souvisly, potom pro kazdou k-tici vrcholu existuje kruznice, na ktere lezi. dokazte!
plati podobne tvrzeni i pro k+1 tice?
3. co vite o principu inkluze a exkluze.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 14
- Registrován: 29. 1. 2009 11:31
- Typ studia: Informatika Mgr.
- Login do SIS: 84250710
Re: Kombinatorika a grafy - pangrac
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ý
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ý