WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Бинарное отношение на множестве называется отношением нестрогого частичного порядка (отношением порядка, отношением рефлексивного порядка), если имеют место

Множество , на котором введено отношение частичного порядка, называется частично упорядоченным. Отношение нестрогого частичного порядка часто обозначают знаком .

Варианты

Отношение частичного порядка называется линейным порядком, если выполнено условие

.

Множество , на котором введено отношение линейного порядка, называется линейно упорядоченным, или цепью.

Отношение , удовлетворяющее только условиям рефлексивности и транзитивности, называется предпорядком, или квазипорядком.

Строгий порядок

Если условие рефлексивности заменить на условие антирефлексивности:

,

то получим определение строгого, или антирефлексивного частичного порядка (обозначается обычно символом ).

Замечание. Одновременная антирефлексивность и транзитивность отношения влечёт асимметричность, которое является более сильным условием, чем антисимметричность. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.

В общем случае, если  — транзитивное, антисимметричное отношение, то

 — рефлексивный порядок
 — строгий порядок.

Примеры

  • На множестве вещественных чисел отношения «больше» и «меньше» являются отношениями строгого порядка, а «больше или равно» и «меньше или равно» — нестрогого.
  • Отношение делимости на множестве целых чисел являются отношением нестрогого порядка.

Размерность Душника — Миллера

Размерность Душника — Миллера (англ.) (иногда называемая просто размерность) частичного порядка — это наименьшее количество отношений линейного порядка, пересечение которых равно данному частичному порядку. Задача распознавания того, превосходит ли размерность данного конечного частичного порядка число принадлежит к классу P при но является NP-полной при [1]

История

Знаки и изобретены Хэрриотом.

См. также

Ссылки

  1. Yannakakis, Mihalis (1982), «The complexity of the partial order dimension problem», SIAM Journal on Algebraic and Discrete Methods 3 (3): 351—358

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии