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ší.
Ř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í.
