Fórum studentů MFF UK

[i]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.[/i]

[b]Důkaz:[/b] Indukcí dle |X|
[u]|X|=1:[/u]
množina je lineárně uspořádaná, R=S, OK.

[u]Indukční krok:[/u]
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.
[i]q.e.d.[/i]

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

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