zkouska 22.12

evajs

zkouska 22.12

Příspěvek od evajs »

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

Dotaz

Příspěvek od dz »

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..
Uživatelský avatar
Ondřej
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 22. 12. 2006 11:52
Typ studia: Informatika Bc.
Bydliště: Hlavní město Praha

Příspěvek od Ondřej »

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

Zpět na „2006“