Matematické Fórum

Speedding

Zdravím, mám pár otázek k částečnému uspořádání, respektive bych si rád ověřil, zdali jsem pojmy správně pochopil.

1) Nejdelší anti-řetězec je v Hasseho diagramu nejdelší "řetězec" prvků, které nejdou porovnat. Je to tedy tak, že nejsou spojené (?)

2) Nejdelší řetězec je v Hasseho diagramu nejdelší řetězec prvků, které jdou porovnat. Je to tedy tak, že jsou všechny propojené (?) Dalo by se obecně říct, že nejdelší řetězec musí nutně začínat minimálním prvek uspořádání a končit maximálním prvkem uspořádání (?)

Minimální, maximální, nejmenší a největší prvky mi jsou celkem jasné, stejně tak to, jak je definováno uspořádání.

Takže třeba když mám částečné uspořádání {{1,2,3,4,5,6,7,8,9,10}, |}, pak Hasseho diagram vypadá takto

//forum.matweb.cz/upload3/img/2016-10/11852_GGGG.png

Nejmenší a zároveň minimální prvek je 1. Maximální a zároveň největší prvek je 8.
Nejdelší antiřetězec je (4,6,9,10,7)
Nejdelší řetězec je (8,4,2,1)

Prosím, řekněte, že mám pravdu :D

Díky

byk7 · 20. 10. 2016 02:40

Prosím, řekněte, že mám pravdu :D

Máš pravdu, ale to lžu. :)

ad 1) Mně se ta formulace nelíbí. Proto budu formální, mějme uspořádanou množinu $(S,\le)$ . Antiřetězec je podmnožina $P\subseteq S$ taková, že pro každé $a,b\in P$ platí $a\not\le b,b\not\le a$ (jinak řečeno, každé dva prvky nejsou srovnatelné). A teď je tu opět rozdíl mezi největším a maximálním antiřetězcem. Radši teď nenapíšu víc, je pozdě a určitě bych to spletl. Takže citace z Wiki

A maximal antichain is an antichain that is not a proper subset of any other antichain. A maximum antichain is an antichain that has cardinality at least as large as every other antichain.

V jistém pořadí koresponduje maximální a největší s anglickými maximum a maximal.

ad 2) Opět největší/maximální... :) Jo, všechny jsou propojené. Jinak řečeno, řetězec neobsahuje nesrovnatelné prvky.

ad obrázek -- Chybí ti tam čára spojující 2 a 10.
S nejmenším/minimálním prvkem souhlasím.
Tvoje množina ale největší prvek nemá, za to má pět maximálních.
Jeden "nejdelší" antiřetězec je tebou uvedený, ale co {6,7,8,9,10}?
S nejdelší řetězcem souhlasím.

Matematické Fórum

#1 19. 10. 2016 23:20 — Editoval Speedding (19. 10. 2016 23:56)

Částečné uspořádání

#2 20. 10. 2016 02:40

Re: Částečné uspořádání

Zápatí