zkouska 22.12

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:-)

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

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.