- •2. Элементы комбинаторики
- •2.1. Основные понятия
- •2.2. Виды комбинаторных задач
- •2.3. Основные правила комбинаторики
- •Базис индукции
- •Решение
- •Решение
- •2.4. Размещения и сочетания
- •Определение
- •Рассмотрим примеры сочетаний
- •2.5. Разбиения множеств на части
- •2.6. Формула включений-исключений
- •Рассмотрим пример
- •Упражнение
- •3. Отношения
- •3.1. Определение и примеры отношений
- •3.2. Представление отношений
- •Табличное задание отношений
- •3.3. Операции над отношениями
- •Определение
- •3.4. Бинарные отношения на множестве
- •3.5. Отношения эквивалентности определение
- •Определение
- •Доказательство
- •Построение разбиения, порождаемого отношением .
- •3.6. Отношения порядка
- •Определение
- •Определение
3.6. Отношения порядка
ОПРЕДЕЛЕНИЕ
Рефлексивное, антисимметричное и транзитивное отношение на некотором множестве называется отношением порядка.
Отношение порядка на некотором множестве А можно интерпретировать как отношение старшинства или подчиненности между элементами A.
Например, если A множество сотрудников некоторого учреждения, то отношение "руководить" является отношением порядка на этом множестве. То есть, если обозначить данное отношение как , то соотношение a b означает, что сотрудник a руководит сотрудником b, или, что то же самое, a является начальником b.
Упражнение. Показать, что если это отношение порядка, то отношение 1 также отношение порядка.
Множество A, на котором задано отношение порядка, называется упорядоченным. Для обозначения множества A с заданным на нем отношением порядка применяется запись (A, ).
Элементы a и b упорядоченного множества (A, ) называются сравнимыми, если выполняется одно из двух соотношений: a b или b a.
Если (A, ) это упорядоченное множество и множество A конечное, то возможно наглядное представление отношения в виде специальной диаграммы. На таких диаграммах элементы A изображаются точками. Из точки, соответствующей a, проводится дуга в точку, соответствующую b в том и только в том случае, когда выполняется условие: a b и не существует такого элемента c, отличного от a и b, что a c и c b. Кроме того, концы всякой дуги соединяют только пары разных вершин.
Такое представление отношений в виде диаграмм отличается от определенного ранее способа представления отношений. Отличие состоит в удалении ребер, соединяющих вершины, которые могут быть соединены цепочкой последовательно идущих ребер, а также петель, начинающихся и заканчивающихся в одной и той же вершине.
Из транзитивности отношения порядка следует, что это отношение может быть восстановлено по своей диаграмме.
Действительно, справедливость соотношения a b означает, что в диаграмме существует цепочка ребер, ведущая из a в b. Если a = b, то такая цепочка пустая.
Упражнение.
1. Предложите способ визуального представления симметричных отношений с помощью изображений, подобных диаграммам.
3. Докажите, что если транзитивное и рефлексивное отношение на A, то является отношением порядка тогда и только тогда, когда в диаграмме для этого отношения нет последовательностей дуг, образующих циклы.
2. Докажите, что рефлексивное и транзитивное отношение является отношением эквивалентности, если любые две вершины диаграммы либо не связаны цепочкой дуг, либо лежат на некотором цикле.
Среди элементов упорядоченного множества (A, ) особый интерес представляют элементы, находящиеся в отношении со всеми элементами A.
Определение
Элемент a называется наибольшим (наименьшим) в отношении , если b A(a b) ( a A(b a)).
Понятно, что всякое упорядоченное множество имеет не более одного наибольшего (наименьшего) элемента. Например, если A это множество возможных ситуаций или вариантов, из которых требуется выбрать оптимальный, и отношение предпочтения одних вариантов перед другими, представляющее собой отношение порядка, то наибольший и наименьший элементы упорядоченного множества (A, ) представляют соответственно наилучший и наихудший варианты.
В общем случае упорядоченное множество может не иметь наибольшего или наименьшего элементов. Например, это так для отношения порядка, диаграмма которого приведена на рис 3.2.
a b
c d
e f g
Рис. 3.2.
Здесь элементы a и b не являются наибольшими, обладают свойством максимальности для всех тех элементов A, с которыми они находятся в отношении .