Antiřetězce a řetězce z Hasseova diagramu

Úloha číslo: 3408

U uspořádání daného následujícím Hasseho diagramem vyznačte nějaký nejdelší řetězec a antiřetězec. U řetězce i antiřetězce zdůvodněte, proč nelze najít delší.

Hasseův diagram
  • Řešení

    Každý nejdelší řetězec má sedm prvků. Jeden z možných nejdelších řetězců je vyznačen silnou čarou. Největší antiřetězec je osmiprvkový, je pro toto částečné uspořádání jednoznačný a je vyznačený křížky.

    Uspořádání lze pokrýt celkem osmi řetězci (zbylých sedm je vyznačeno ovály na obrázku, z nich jsou čtyři jednoprvkové), proto nemůže obsahovat antiřetězec o devíti prvcích – dva prvky antiřetězce by ležely ve stejném řetězci a to není možné.

    Maximalita délky řetězce by se dokázala obdobně – uspořádání lze pokrýt sedmi antiřetězci, např. ‘vrstvami’ v diagramu. (‘Prostřední vrstva’ je zmíněný maximální antiřetězec vyznačený křížky.) Uvědomte si ale, že existují i jiná pokrytí sedmi antiřetězci a že ani není nutné, aby antiřetězce byly disjunktní.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze