Částečné cyklické pořadí - Partial cyclic order

tento článek lze rozšířit o text přeložený z odpovídající článek francouzsky. (Listopad 2019) Kliknutím na [zobrazit] zobrazíte důležité pokyny k překladu. Strojový překlad jako DeepL nebo Google Překladač je užitečným výchozím bodem pro překlady, ale překladatelé musí podle potřeby revidovat chyby a potvrdit, že překlad je přesný, spíše než jednoduše kopírovat strojově přeložený text do anglické Wikipedie. Nepřekládejte text, který se jeví jako nespolehlivý nebo nekvalitní. Pokud je to možné, ověřte text pomocí odkazů uvedených v cizojazyčném článku. Vy musí poskytnout přisuzování autorských práv v upravit souhrn doprovázející váš překlad poskytnutím mezijazykový odkaz ke zdroji vašeho překladu. Souhrn úprav atribuce modelu Obsah této úpravy je přeložen z existujícího článku francouzské Wikipedie na [[: fr:]]; viz jeho historii pro atribuci. Měli byste také přidat šablonu {{Přeložená stránka}} do diskusní stránka. Další pokyny najdete v části Wikipedia: Překlad.

V matematice, a částečný cyklický řád je ternární vztah, který zobecňuje a cyklický řád stejným způsobem jako a částečná objednávka zobecňuje a lineární pořadí.

Definice

Přes danou množinu je částečný cyklický řád ternárním vztahem ${ displaystyle R}$ to je:

• cyklický, tj. je neměnný pod cyklická permutace: ${ displaystyle R (x, y, z) Rightarrow R (y, z, x)}$
• asymetrický: ${ displaystyle R (x, y, z) Rightarrow ne R (z, y, x)}$
• tranzitivní: ${ displaystyle R (x, y, z)}$ a ${ displaystyle R (x, z, u) Rightarrow R (x, y, u)}$^[1]

Stavby

Přímý součet

Přímý produkt

Napájení^[2][3]

Dokončení Dedekind – MacNeille

Rozšíření

lineární prodloužení, Věta o rozšíření Szpilrajn

standardní příklad

Vztah mezi částečnými a celkovými cyklickými řády je složitější než vztah mezi částečnými a celkovými lineárními řády. Za prvé, ne každý dílčí cyklický řád lze rozšířit na celkový cyklický řád. Příkladem je následující vztah k prvním třinácti písmenům abecedy: {acd, bde, cef, dfg, egh, fha, gac, hcb} ∪ {abi, cij, bjk, ikl, jlm, kma, laboratoř, mbc}. Tento vztah je částečný cyklický řád, ale nelze jej rozšířit ani na jeden abc nebo cba; každý pokus by vedl k rozporu.^[4]

Výše uvedené bylo relativně mírným příkladem. Lze také vytvořit dílčí cyklické řády s překážkami vyššího řádu tak, že lze přidat například libovolných 15 trojic, ale 16. nikoli. Ve skutečnosti je cyklické řazení NP-kompletní, protože to řeší 3SAT. To je v příkrém kontrastu s problémem rozpoznávání lineárních objednávek, který lze vyřešit v lineární čas.^[5][6]

Poznámky

Reference

Další čtení