Částečné uspořádání
Úloha číslo: 3664
Mějme šachovnici \(4\times 4\) a v jejím levém dolním rohu postaveného jezdce. Na políčkách šachovnice zavedeme relaci \(\preceq\), kde \(a \preceq b\) znamená, že políčko \(a\) leží na některé z nejkratších cest jedcem z levého dolního rohu na políčko \(b\).
Kolik má \(\preceq\) maximálních prvků?
- 2
- 3
- 4
Řešení
Prohledáváním do šířky zjistíme, že nejdelší cesty končí v rozích – protilehlý roh ve vzdálenosti 2, zbylé dva rohy ve vzdálenosti 5. Ostatní políčka leží na nejkratších cestách délky 5.
Odpověď
Správná odpověď je b.