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

Úloha číslo: 3408

U uspořádání daných následujícími Hasseho diagramy 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ší.
  • Varianta

    Hasseův diagram 1
  • Řešení

    Každý nejdelší řetězec má sedm prvků. Jeden z možných nejdelších řetězců je vyznačen modře.

    Nějdelší řetězec a pokrytí antiřetězci.

    Uspořádání lze pokrýt sedmi antiřetězci, vyznačenými červeně. V uspořádání nemůže být delší řetězec, protože by podle Dirichletova principu obsahoval alespoň dva prvky z nějakého antiřetězce a ty by musely být porovnatelné i neporovnatelné zároveň. Uvědomte si ale, že existují i jiná pokrytí sedmi antiřetězci a že ani není nutné, aby antiřetězce byly disjunktní.

    Největší antiřetězec je osmiprvkový, je pro toto částečné uspořádání jednoznačný a je vyznačený červeně v následujícím obrázku.

    Nějdelší antiřetězec a pokrytí řetězci.

    Maximalita délky řetězce se dokáže obdobně. Uspořádání lze pokrýt celkem osmi řetězci, vyznačených modře, z nichž čtyři jednoprvkové jsou zakroužkovány. Proto nemůže obsahovat antiřetězec o devíti prvcích, neboť dva prvky antiřetězce by ležely ve stejném řetězci a to není možné.

  • Varianta

    Hasseův diagram
  • Řešení

    Nejdelší řetězec délky 6 a pokrytí šesti antiřetězci je např:

    Nejdelší řetězec délky 6 a pokrytí šesti antiřetězci

    Nejdelší antiřetězec délky 10 a pokrytí desíti řetězci je např:

    Nejdelší antiřetězec délky 10 a pokrytí desíti řetězci
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze