Zk. 2009-06-12 - Kratochvíl

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
seby
Matfyz(ák|ačka) level I
Příspěvky: 42
Registrován: 31. 1. 2008 15:40
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Zk. 2009-06-12 - Kratochvíl

Příspěvek od seby »

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.
seby
Matfyz(ák|ačka) level I
Příspěvky: 42
Registrován: 31. 1. 2008 15:40
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zk. 2009-06-12 - Kratochvíl

Příspěvek od seby »

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.
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“