Kombinatorika a grafy - pangrac

kua

Kombinatorika a grafy - pangrac

Příspěvek od kua »

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.
marci

zkouska 4.6.

Příspěvek od marci »

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.
Krakonoš
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 29. 1. 2009 11:31
Typ studia: Informatika Mgr.

Re: Kombinatorika a grafy - pangrac

Příspěvek od Krakonoš »

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ý :-)
Odpovědět

Zpět na „Ostatní“