# Zk. 2009-06-12 - Kratochvíl

<{ForumPost(poster="seby", timestamp=2009-06-12 11:13:27)}>
Snad všechny dnešní příklady jsem už někde v historii fóra viděl, takže zadání popíšu jen tak lehce. Upřesnění a případně i výsledky budou možná následovat později.  
1) Dpolňte LO 3×6 na LČ 6×6 (nebo dokažte, že to nejde).  
2) Napište vytvořující funkci pro řadu (2,2,3,3,4,4,5,5,...).  
3) Najděte min. řez v grafu.  
4) Které z následujících množinových systémů mají SRR? (Následovaly 3 množinové systémy o max. 5 množinách o max. 4 prvcích.)  
5) Dokažte, že pro každý k-regulární graf G platí, že k_v(G) = k_e(G).  
6) Dokažte, že pro každé *k*, *n* existuje *N*, že v každé množině bodů v rovině o velikosti *N*, jejíž dvojice bodů určují max. *k* směrů, existuje *n* bodů, které leží na 1 přímce.
<{/ForumPost}>

<{ForumPost(poster="seby", timestamp=2009-06-12 22:35:11)}>
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.
<{/ForumPost}>