# zkouska 22.12

<{ForumPost(poster="evajs", timestamp=2006-12-22 23:38:17)}>
ahoj, tady je zadani jedne skupiny:  
  
1) definujte centrum, zformulujte a dokazte vetu o centru grafu  
2) strom lze ekvivalentne definovat jako minimalni souvisly graf, zformulujte a dokazte  
3) zformulujte a dokazte vetu o linearnim rozsireni  
4) kazdy graf obsahujici most ma alespon dva vrcholy licheho stupne, dokazte  
5) urcete pocet permutaci s prave dvema pevnymi body  
6) kolik minimalnich koster grafu ma graf, kde pro kazdou hranu plati w(e)=3  
7) \alpha(P)*\omega(P)>= 6 pro kazde castecne usporadani na sesti vrcholech. dokazte.  
  
statistika celkem dobra, asi 4 jednicky a 6 dvojek, dvojku daval za vic nez jeden priklad spatne. na zkousku je dve hodiny a rozhodne si neberte oblek:-) je to jenom pisemka:-)
<{/ForumPost}>

<{ForumPost(poster="dz", timestamp=2007-01-08 19:22:41)}>
Asi budu vypadat jako blbec, ale nikde jsem to nenašel. Jak zní a v čem tkví důkaz věty o linárním rozšíření? Díky moc..
<{/ForumPost}>

<{ForumPost(poster="Ondřej", timestamp=2007-01-11 19:16:28)}>
*Pro každou konečnou částečně uspořádanou množinu (X,R) existuje lineární uspořádání (X,S) tak, že R je podmnožinou či rovno S.*  
  
**Důkaz:** Indukcí dle |X|  
|X|=1:  
množina je lineárně uspořádaná, R=S, OK.  
  
Indukční krok:  
Nechť x je minimální prvek (X,R). Uvažme (X',R') tak, že X'=X-{x}, R'= R průnik s (X'¤X').  
Dle indukčního předpokladu existuje lineárně uspořádaná množina (X',S') tak, že R' je podmnožinou či rovno S'.  
Definujme (X,S) předpisem:  
S průnik (X'¤X') = S', (x,x) je prvkem S, pro každé y z X' platí, že (x,y) je prvkem S.  
Protože pro všechny dvojice prvků z X, platí, že buď neobsahují x (a tedy jsou z (X',S'), a tedy jsou ony dva prvky porovnatelné), a nebo obsahují x (což je nejmenší prvek v (X,S), a tedy jsou prvky porovnatelné), je (X,S) lineární uspořádání.  
Jelikož R' je podmnožinou nebo rovno S' a x je minimální prvek (X,R), je R podmnožinou nebo rovno S.  
*q.e.d.*
<{/ForumPost}>