Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » Částečné uspořádání: řetězce a antiřetězce
#1 21. 11. 2012 22:16
Částečné uspořádání: řetězce a antiřetězce
Ahoj,neměli byste prosím nějaký tip jak dokázat:
Nechť (R,X) je částečné uspořádání, ve kterém má nejdelší rětězec délku m. Dokažte, že nosná množina X se dá pokrýt(=rozdelit na) m antiřetězci.
Offline
#2 22. 11. 2012 19:49
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: Částečné uspořádání: řetězce a antiřetězce
↑ 85978057:
ahoj, zkusil bych tu množinu antiřetězců sestrojit induktivne. Klíčové bude uvážit množinu minimálních prvků uspořádání (označoě ji M).
1) ukaž, že M (je neprázdná a ) tvoří antiřetězec.
2) ukaž, že množina X\M s restrikcí uspořádání R je č u m taková, že délka nejdelšího řetězce je m-1.
3) slep vhodně 1) a 2) dohromady. ; )
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline
#3 24. 11. 2012 13:41
Re: Částečné uspořádání: řetězce a antiřetězce
↑ 85978057:
Len tak pre zaujimavost vraj sa to vola Mirsky's theorem. Znamejsie je asi dualne tvrdenie - Dilworthova veta.
Offline
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » Částečné uspořádání: řetězce a antiřetězce