Частичный циклический порядок - Partial cyclic order

Эта статья может быть расширен текстом, переведенным с соответствующая статья На французском. (Ноябрь 2019 г.) Щелкните [показать] для получения важных инструкций по переводу. Машинный перевод нравится DeepL или же переводчик Google является полезной отправной точкой для переводов, но переводчики должны исправлять ошибки по мере необходимости и подтверждать точность перевода, а не просто копировать и вставлять машинно переведенный текст в английскую Википедию. Не переводите текст, который кажется ненадежным или некачественным. Если возможно, сверьте текст со ссылками, приведенными в статье на иностранном языке. Ты должен предоставлять авторское право в редактировать резюме сопровождая ваш перевод, предоставив межъязыковая ссылка к источнику вашего перевода. Сводка редактирования атрибуции модели Содержимое этого редактирования переведено из существующей французской статьи в Википедии на [[: fr:]]; см. его историю для атрибуции. Вам также следует добавить шаблон {{Переведенная страница}} в страница обсуждения. Для получения дополнительной информации см. Википедия: Перевод.

В математике частичный циклический порядок - тернарное отношение, обобщающее циклический порядок так же, как частичный заказ обобщает линейный порядок.

Определение

По данному набору частичный циклический порядок - это тернарное отношение ${ displaystyle R}$ то есть:

• циклический, т.е. это инвариантный под циклическая перестановка: ${ Displaystyle R (х, y, z) Rightarrow R (y, z, x)}$
• асимметричный: ${ Displaystyle R (х, y, z) Rightarrow not R (z, y, x)}$
• переходный: ${ Displaystyle R (х, y, z)}$ и ${ Displaystyle R (x, z, u) Rightarrow R (x, y, u)}$^[1]

Конструкции

Прямая сумма

Прямой продукт

Мощность^[2][3]

Завершение Дедекинда – МакНила

Расширения

линейное расширение, Теорема Шпильрайна о продолжении

стандартный пример

Отношения между частичным и полным циклическими порядками более сложны, чем отношения между частичным и полным линейными порядками. Начнем с того, что не каждый частичный циклический порядок можно расширить до полного циклического порядка. Примером может служить следующее отношение первых тринадцати букв алфавита: {acd, bde, cef, dfg, egh, fha, gac, hcb} ∪ {abi, cij, bjk, ikl, jlm, kma, lab, mbc}. Это отношение является частичным циклическим порядком, но его нельзя расширить ни с помощью abc или же cba; любая попытка приведет к противоречию.^[4]

Вышеприведенный пример был относительно мягким. Можно также построить частичные циклические порядки с препятствиями более высокого порядка, так что, например, любые 15 троек могут быть добавлены, а 16-я - нет. Фактически, циклический порядок НП-полный, поскольку он решает 3СБ. Это резко контрастирует с проблемой распознавания линейных порядков, которую можно решить в линейное время.^[5][6]

Примечания

Рекомендации

дальнейшее чтение