od seby » 12. 6. 2009 22:35
Příklad řešení:
1) LO lze vždy doplnit na LČ - nejlépe to tam prostě nějak ručně doplnit.
2) Standardní řešení - vyjdu z (1,1,1,1,...) a postupně funkci upravuji.
3) Najdu max. tok, ten se rovná min. řezu, najdu takový min. řez (min. řezem se myslí řez o min. kapacitě).
4) Pokud SRR existuje, stačí jej napsat. Pokud neexistuje, stačí napsat množinu množin, které nesplňují Hallovu podmínku.
5) Lze řešit buď rozborem případů pro k_v(G) nebo pomocí F-F a Mengerovy věty (vím-li, že existuje k hranově disjunktních hran, potom tyto cesty jsou také vrcholově disjunktní - kdyby ne, tak vrchol, ve kterém se protínají musí mít stupeň 4).
6) Přesné zadání: Dokažte tvrzení: Pro každá dvě přirozená čísla k a n existuje přirozené číslo N s následující vlastností. Pokud pro nějakou množinu M obsahující N bodů v rovině platí, že přímky určené dvojicemi bodů z M určují nejvýše k směrů, pak alespoň n bodů z M leží na jedné přímce.
Řešení A: Přes Ramseyovu větu o barvení k-tic - barvy jsou směry, barvíme dvojice, vyjde nám, že existuje n bodů, ze kterých vybereme libovolný bod a ten s libovolným jiným bodem v této množině určuje tentýž směr. Z analytické geometrie víme, že přímku lze jednoznačně určit bodem a směrem, tedy všechny body jsou na jedné přímce.
Řešení B: Vybereme libovolný pevný bod a proložíme přímky všemi ostatními body. Směrů (tedy i přímek) musí být k, ale bodů máme N, tedy musí existovat přímka (Dirichlet), že je na ní >= N/k bodů. zvolíme-li N dostatečně velké, pak N/k > n.
Toto jsou pouze myšlenky řešení. V písemce je to potřeba podrobněji rozebrat.
Příklad řešení:
1) LO lze vždy doplnit na LČ - nejlépe to tam prostě nějak ručně doplnit.
2) Standardní řešení - vyjdu z (1,1,1,1,...) a postupně funkci upravuji.
3) Najdu max. tok, ten se rovná min. řezu, najdu takový min. řez (min. řezem se myslí řez o min. kapacitě).
4) Pokud SRR existuje, stačí jej napsat. Pokud neexistuje, stačí napsat množinu množin, které nesplňují Hallovu podmínku.
5) Lze řešit buď rozborem případů pro k_v(G) nebo pomocí F-F a Mengerovy věty (vím-li, že existuje [i]k[/i] hranově disjunktních hran, potom tyto cesty jsou také vrcholově disjunktní - kdyby ne, tak vrchol, ve kterém se protínají musí mít stupeň 4).
6) Přesné zadání: Dokažte tvrzení: Pro každá dvě přirozená čísla [i]k[/i] a [i]n[/i] existuje přirozené číslo [i]N[/i] s následující vlastností. Pokud pro nějakou množinu [i]M[/i] obsahující [i]N[/i] bodů v rovině platí, že přímky určené dvojicemi bodů z [i]M[/i] určují nejvýše [i]k[/i] směrů, pak alespoň [i]n[/i] bodů z [i]M[/i] leží na jedné přímce.
Řešení A: Přes Ramseyovu větu o barvení k-tic - barvy jsou směry, barvíme dvojice, vyjde nám, že existuje [i]n[/i] bodů, ze kterých vybereme libovolný bod a ten s libovolným jiným bodem v této množině určuje tentýž směr. Z analytické geometrie víme, že přímku lze jednoznačně určit bodem a směrem, tedy všechny body jsou na jedné přímce.
Řešení B: Vybereme libovolný pevný bod a proložíme přímky všemi ostatními body. Směrů (tedy i přímek) musí být [i]k[/i], ale bodů máme [i]N[/i], tedy musí existovat přímka (Dirichlet), že je na ní >= N/k bodů. zvolíme-li [i]N[/i] dostatečně velké, pak N/k > n.
Toto jsou pouze myšlenky řešení. V písemce je to potřeba podrobněji rozebrat.