2.5. Отношения порядка

8. Удаляем из B последнее включенное в него множество, а именно A13; p := 1; в блоке 1 больше нет подмножеств – на Шаг 4.

ченное на итерации 5, есть оптимальное решение; стоп. J

Пример 2.25. Организации требуются переводчики с иностранных языков, приведенных в таблице. На должность переводчиков претендуют пять человек – A; B; C; D; E, каждый из которых знает несколько языков. Каких из переводчиков нужно принять на работу, чтобы обеспечить перевод со всех нужных языков и минимизировать суммарную зарплату (предполагается что оклады у всех переводчиков одинаковые)?

2.5 Отношения порядка

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

Определение. Отношение hA; Mi называется отношением строгого порядка (строгим порядком), если оно антирефлексивно и транзитивно.

Отношение строгого порядка будем также обозначать символами Á или Â.

Примеры 2.26.

1. Отношения строгого порядка < и > для целых и действительных чисел.

2.Отношение включения ½ есть отношение строгого порядка для множеств.

3.Отношения “быть предком “быть потомком” также являются примерами отношения строгого порядка. J

2.5.2 Свойства строгого порядка

Теорема 2.23 Отношение строгого порядка асимметрично.

Д о к а з а т е л ь с т в о (от противного). Напомним, что свойство A \ A¡1 = ? является определением асимметричности.

Пусть A \ A¡1 =6 ?, т.е. существуют такие x; y, что выполняются соотношения xAy и xA¡1y, или xAy и yAx. Из транзитивности отсюда следует: xAy ^ yAx ) xAx, что противоречит антирефлексивности. £

Итак, отношение строгого порядка A на M обладает следующими свойствами:

1. 8x 2 M [hx; xi 62A]. 2. xAy ^ yAz ) xAz.

3. xAy ) hy; xi 62A или hx; yi 2 A ) hy; xi 62A.

Первые два свойства – определение строгого порядка, а третье – следствие (теорема 2.23).

Граф, соответствующий отношению строгого порядка, не содержит ориентированных циклов (контуров). Ориентированный цикл (орцикл, контур) в ориентированном графе (орграфе) – это такая последовательность вершин (и дуг) x0; x1; : : : ; xk, что xk = x0 и от вершины xi к вершине xk+1 идет дуга. Частным случаем контура является петля.

Определение. Множество M с заданным на нем отношением строгого порядка Á называется упорядоченным множеством и обозначается hÁ; Mi.

Определение. Отношение строгого порядка A называется совершенным строгим порядком, если для любой пары несовпадающих элементов x 6= y из M верно либо xAy, либо yAx.

Теорема 2.24 Если на конечном непустом M задан совершенный строгий порядок Á, то существует единственный

элемент x 2 M такой, что для любого y 2 M, не совпадающего с x (y =6 x), выполняется соотношение x Á y.

Элемент x, обладающий этим свойством называется наименьшим элементом в упорядоченном множестве hÁ; Mi.

Д о к а з а т е л ь с т в о . Возьмем любой y0 2 M. Если y0 – наименьший, то существование искомого элемента доказано.

Если нет, то поскольку Á – совершенный строгий порядок, существует элемент y1 =6 y0 такой, что y1 Á y0. Снова, либо y1 наименьший, либо существует y2 =6 y1 такой, что y2 Á y1.

Продолжим этот процесс. Пусть уже выбрано n + 1 элементов, для которых

yn Á yn¡1; yn¡1 Á yn¡2; : : : ; y1 Á y0.

Из транзитивности следует, что yi Á yj при i > j. Из антирефлексивности следует, что выбранные элементы попарно не равны. Ввиду конечности M процесс выбора элементов должен оборваться на некотором конечном шаге. Элемент yn, выбранный на последнем шаге будет, очевидно, искомым.

Итак, для любого z 6= yn выполнено yn Á z. Покажем, что этот элемент – единственный. Пусть существует другой элемент y0n, такой, что для любого z =6 y0n; y0n Á z. Тогда одновременно выполняются соотношения yn Á y0n и y0n Á yn, что невозможно из-за асимметричности £

З а м е ч а н и е. Если на M задан совершенный строгий порядок Á, и Q µ M; Q =6 ?, то hÁ; Qi есть также совершенный строгий порядок и в Q существует единственный наименьший элемент. I

Следствие. Пусть на M задано отношение совершенного строгого порядка. Тогда можно выбрать такую нумерацию элементов M = fx1; : : : ; xng, что соотношение xi Á xj будет выполняться, когда i < j.

Д о к а з а т е л ь с т в о . Выберем x1 – наименьший элемент множества M. Через M1 обозначим M n fx1g. В M1

снова найдем наименьший элемент x2 и снова из M1 удалим x2, и так далее. Перебирая последовательно все элементы из M, получим цепочку

или y Á x (равенство в данном случае обозначает идентичность элементов, т.е. x и y – это один и тот же элемент). Определение. Пусть на M задано отношение Á строгого порядка. Подмножество Q µ M называется максимальным совершенным, если

1)отношение Á задает на Q совершенный строгий порядок;

2)на любом подмножестве R µ M; Q ½ R (для которого Q – собственное подмножество), отношение Á уже не является совершенным строгим порядком.

Теорема 2.25 Пусть hÁ; Mi – упорядоченное множество. Для любого элемента y 2 M существует максимальное совершенное подмножество Q µ M, содержащее y.

Д о к а з а т е л ь с т в о (для конечного M). Пусть Q1 = fyg. Отношение Á на Q1 является совершенным строгим поряд-

ком (отношение пусто). Если Q1 максимальное совершенное подмножество, то теорема доказана.

Пусть мы построили Qn – совершенно строгий порядок с отношением Á. Если Qn максимально, то теорема доказана. Если нет, то в M существует элемент, сравнимый со всеми элементами из Qn. Присоединим его к Qn и получим Qn+1 ¾ Qn с совершенным строгим порядком. Из-за конечности M этот процесс оборвется на конечном шаге и мы получим максимальное совершенное подмножество Q 3 y. £

Теорема 2.26 Пусть Á – отношение строгого порядка на конечном M. Для любого элемента y 2 M существует минимальный элемент x 2 M, такой, что x Á y или x = y.

До к а з а т е л ь с т в о . Если y – минимальный элемент, то x = y. В противном случае существует такой элемент z 2 M, что z Á y. Если z – минимальный элемент, то x = z. В противном случае существует такой u 2 M, что u Á z, и так далее. Так как M конечное, то через конечное число шагов убывающая цепочка : : : u Á z Á y оборвется на искомом элементе. £

Глава 2. Бинарные отношения

Определение. Отношение hA; Mi называется отношением нестрогого порядка

(нестрогим порядком), если его можно представить в виде

A = A1 [ ¢ (4 = Á [¢),

где A1 – строгий порядок, ¢ – диагональное отношение.

Нестрогий порядок часто обозначают как 4 или <.

Из определения следует, что нестрогий порядок рефлексивен (¢ µ A).

Проверим его транзитивность (A2 µ A):

(A1 [ ¢)2 = A21 [ A1¢ [ ¢A1 [ ¢2 µ A1 [ A1 [ A1 [ ¢ = A1 [ ¢

(так как ¢A = A¢ = A; ¢2 = ¢).

В отличие от строгого порядка Á отношение ¹ не асимметрично, а только антисимметрично. Более того,

A \ A¡1 = ¢. Действительно,

A \ A¡1 = (A1 [ ¢) \ (A¡1 1 [ ¢) =

= (A1 \ A¡1 1) [ (A1 \ ¢) [ (A¡1 1 \ ¢) [ ¢ = ¢

(из антирефлексивности и асимметричности A1).

Таким образом, отношение нестрогого порядка ¹ рефлексивно, антисимметрично и транзитивно. Обратно, если отношение A рефлексивно, антисимметрично и транзитивно, то A – нестрогий порядок. Действительно,

A = (A n ¢) [ ¢, а A n ¢ – строгий порядок.

Итак, нестрогий порядок можно было определить аксиоматически как рефлексивное, антисиммтричное и транзитивное отношение. Ни одно из этих свойств не следует из других.

Определение. Нестрогий порядок назовем совершенным, если для любой пары hx; yi выполняется одно из соотношений: x 4 y, либо y 4 x.

Из антисимметричности нестрогого порядка следует, что одновременное выполнение x 4 и y 4 x означает совпадение x = y.

Теорема 2.27 Если A – совершенный нестрогий порядок, то A1 = A n ¢ – совершенный строгий порядок.

Обратно, если A1 – совершенный строгий порядок, то A = A1 [ ¢ – совершенный нестрогий порядок.

До к а з а т е л ь с т в о . 1. °) A1 = A n ¢ = A \ ¢. Покажем, что A1 – совершенный строгий порядок. 1) A1 антирефлексивно:

¢ \ A1 = ¢ \ (A \ ¢) = A \ ¢ \ ¢ = ?.

2)A1 асимметрично: (A\¢)\(A\¢¡1 = A\¢\A¡1 \¢¡1 = = A \ A¡1 \ ¢ \ ¢¡1 µ ¢ \ ¢ \ ¢¡1 = ?.

3)A1 транзитивно:

где A2 – строгий порядок.

Все сравнимые в A элементы сравнимы и в A2, т.е. A1 – совершенный строгий порядок.

2. °( Пусть теперь A1 – совершенный строгий порядок и

A = A1 [ ¢.

1)A рефлексивно : ¢ µ A.

2)A антисимметрично:

(A1 [ ¢) \ (A1 [ ¢)¡1 = (A1 [ ¢) \ (A¡1 1 [ ¢¡1) =

= A1 \ A¡1 1) [ (¢ \ A¡1 1) [ (¢¡1 \ A1) [ (¢ \ ¢¡1) = ¢

т.к. A1 \ A¡1 1 = ?; ¢ \ A¡1 1 = ?; ¢¡1 \ A1 = ?. 3) A транзитивно:

(A1 [ ¢)2 = A21 [ A1¢ [ ¢A1 [ ¢2 = A1 [ A1 [ A1 [ ¢ = A1 [ ¢

(из рефлексивности и транзитивности A1). £

Квазипорядок является обобщением эквивалентности и нестрогого порядка одновременно.

Теорема 2.28 Если отношение A есть одновременно эквивалентность и нестрогий порядок, то A – отношение равенства.

Д о к а з а т е л ь с т в о (от противного). Пусть выполнены соотношения xAy и x =6 y. Тогда из симметричности эквивалентности верно yAx. Из антисимметричности нестрогого порядка yAx не выполняется. Из противоречия (и рефлексивности) y = x. £

Из определения Ar следует, что соотношение xAry выполняется тогда и только тогда, когда выполнено само соотношение xAy, но не существует такого "промежуточного” z, что xAz и zAy. Отношение xAry означает "непосредственное подчинение” элемента x элементу y (или непосредственное следование элемента x за элементом y).

Редукция отношения строгого порядка содержит всю информацию о нем, но изображается более простым графом.

За м е ч а н и е. Для любого отношения A

1.Ar µ A – из определения Ar.

A3 [ ¢ ¢ ¢ [ An [ ¢ ¢ ¢ ) µ A. I

Теорема 2.29 Если A – строгий порядок на конечном M, то

Ar = A

Пусть выполняется соотношение xAy. Если выполнены соотношения

xAz1; z1Az2; : : : ; zk¡1Azk; zkAy, ( ? )

то из-за антиантирефлексивности и транзитивности строгого порядка A и конечности M все элементы в цепочке x; z1; : : : ; zk; y различны.

Рассмотрим все возможные цепочки элементов z1; : : : ; zk (k ¸ 0), такие, что выполняется ( ? ).

Так как M конечно, таких цепочек конечное число. Значит среди них есть цепочка наибольшей длины (возможно и не одна). Выберем любую из цепочек наибольшей длины. Из ( ? ) и из того, что цепочка z1; : : : ; zk имеет наибольшую длину следует выполнение

c c

Оба эти включения и определяют равенство. £

Эта теорема означает для строгого порядка A: на конечном M по редукции можно однозначно восстановить отношение A. Более того, редукция Ar есть минимальное отношение, позволяющее восстановить A.

З а м е ч а н и е. Для нестрогого порядка 42 = 4, поэтому 4r = 4 n 42 = ?. Следовательно, о восстановлении 4 по редукции не может быть и речи. I

Напомним определение антитранзитивного отношения:

Определение. Отношение B называется антитранзитивным, если

B \ Bn = ?; n > 2

Иначе говоря, если выполняется цепочка соотношений xBx1; x1Bx2; : : : ; xnBy,

Определение. Отношение строгого порядка Á на множестве M называется отношением древесного порядка (древесным порядком), если

1)из того, что x Á y и x Á z следует, что y и z сравнимы (т.е. либо y Á z, либо z Á y).

2)на множестве hÁ; Mi существует наибольший элемент.

Определим множество Mx следующим образом: Mx состо-

ит из x 2 M и из всех y таких, что y Á x Mx = fxg [ fyjy Á xg.

Теорема 2.31 Если A – древесный порядок на M, то на Mx отношение A также задает древесный порядок

Д о к а з а т е л ь с т в о . Первое условие определения древесного порядка выполняется для любого подмножества M. Наибольшим элементом в Mx является сам x. £

Теорема 2.32 Если A – древесный порядок на конечном множестве M, то для всякого x, отличного от корня x0, существует ровно один y, для которого выполнено xAry.

Д о к а з а т е л ь с т в о . 1. Предположим сначала, что существуют такие y и z (y 6= z), что xAry и xArz. По определению древесного порядка, из выполнения xAy, xAz и x 6= y следует yAz или zAy. Положим для определенности yAz. Получается, что выполнены соотношения xAy и yAz. Следовательно, невозможно xArz.

Итак, мы показали, что не может быть двух разных элементов, “непосредственно старших"чем данный x.

2. Предположим теперь, что для x не существует такого y, что xAry. Так как Ar µ A, то из невыполнения xAry следует и невыполнение xAy, т.е. не существует такого y, что xAy. Значит, x = x0, т.е. x – максимальный и наибольший элемент. £

Это означает, что из каждой вершины графа редукции Ar исходит не более одной дуги, т.е. Ar является деревом: в нем не только нет орциклов, но и (неориентированных) циклов.