Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Цепи и антицепи, и их свойства.

Читайте также:
  1. Культуральные свойства.
  2. Отношения частичного порядка. Линейно- упорядоченные множества. Максим.(миним.) наимен(наибольш.) элементы частично упорядоченного множества и их свойства.
  3. Отношения частичного порядка. Линейно- упорядоченные множества. Максим.(миним.) наимен(наибольш.) элементы частично упорядоченного множества и их свойства.

Линейно упорядоченное множество или цепь ― частично упорядоченное множество, в котором для любых двух элементов a и b имеет место или .

Важнейший частный случай линейно упорядоченных множеств ― вполне упорядоченные множества.

Формулировка теоремы Дилуорса

Пусть n — наибольшее количество элементов антицепи (англ. antichain) данного конечного частично упорядоченного множества M. Тогда M можно разбить на n попарно непересекающихся цепей.

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

 

Булевы кубы и их характеристики. Расстояние между его элементами и их нумерация. Код Гроя.

В={0,1}

n-мерный булев куб — это множество Bn (с заданным частичным порядком)

Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.


Дата добавления: 2015-09-06; просмотров: 112 | Нарушение авторских прав


Читайте в этой же книге: Множества и действия над ними. Свойства операций над множествами. | Размещение с повторением | Принцип включения и исключения и его применение к решению комбинаторных задач на примере задачи о беспорядках. | Рекуррентные соотношения, соответствующие им рекуррентные уравнения и их решения. Понятие характеристического многочлена. | Отношения на множествах. Свойства отношений. Отношение эквивалентности и классы эквивалентности. Разбиение множеств. | Преобразование кода Грея в двоичный код | Использование матриц смежности. | Степени матрицы | Подразделение графа. | Полные, двудольные и полные двудольные графы. |
<== предыдущая страница | следующая страница ==>
Отношения частичного порядка. Линейно- упорядоченные множества. Максим.(миним.) наимен(наибольш.) элементы частично упорядоченного множества и их свойства.| Следствие

mybiblioteka.su - 2015-2018 год. (0.01 сек.)