2.5.6Некоторые свойства дерева

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

(Растущее) дерево определяется следующим образом:

1)это граф без циклов;

2)из корня не исходит ни одной дуги;

3)из всех остальных вершин исходит ровно по одной дуге.

Рассмотрим свойства редукции строгого порядка.

1.Так как редукция строгого порядка антитранзитивна, то граф hÁr; Mi не содержит циклов.

2.Так как корень – наибольший элемент, то из него не исходит ни одна дуга.

3.Из всех остальных вершин исходит ровно по одной дуге: по теореме (??) в древесном порядке для любого x, отличного

от корня, существует единственный y, для которого выполняется xAry.

4.Любой подграф дерева – тоже дерево (поддерево).

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

За м е ч а н и е. Если в определении древесного порядка отказаться от существования наибольшего элемента, то для конечного M получим вместо дерева объединение нескольких попарно непересекающихся деревьев (лес). I

Вспомним определение совершенного строгого порядка: отношение A – строгий порядок и для любых x; y либо xAy, либо yAx.

Граф редукции Ar отношения A совершенного строгого порядка обладает (кроме указанных) таким свойством: в любую вершину (кроме наименьшего элемента) заходит ровно одна дуга.

В отношении совершенного строгого порядка существуют единственный минимальный и единственный максимальный

элементы, они же, соответственно, наименьший и наибольший.

Если A – совершенный строгий порядок, то его редукция Ar представляется в виде линейной цепочки. Поэтому совершенный строгий порядок называют также линейным порядком. Линейный порядок – частный случай древесного порядка. Иногда линейным порядком называют также и совершенный нестрогий порядок (главное условие – выполнение для любой пары x; y: либо x ¹ y, либо y ¹ x). Но для нестрогого порядка редукция пуста: A n A2 = ?, так как для рефлексивного и транзитивного отношения A2 = A.

Примеры 2.30.

1. Граф редукции древесного порядка. p

pp

2.Генеалогическое дерево.

3.Иерархические структуры:

²структуры данных;

²классы в биологии;

²классы в объектно-ориентированном программировании;

²бюрократические структуры (идеальные).

4.Линейный порядок:

²конечное подмножество натуральных чисел;

²словарный (лексикографический) порядок, если омонимы считать одним входом. J

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

З а м е ч а н и е. Пусть A – линейный порядок (строгий Á или нестрогий 4) на конечном M.

S = Sm Mi – множество i-кортежей над M с элементами

i=1

вида:

ha1; a2; : : : ; api,

hb1; b2; : : : ; bqi, p 6 q

Отношение < на S называется лексикографическим порядком , т.е. для кортежей выполняется соотношение

ha1; a2; : : : ; api < hb1; b2; : : : ; bqi, если выполнено одно из условий:

1) существует такое целое j, что

ai = bi при i < j, и ajAbj, (например, aj Á bj). 2) ai = bi, 1 6 i 6 p и p 6 q. I

2.5.7Анализ отношений порядка

1.Проверка на строгий порядок.

Для того чтобы проверить, является ли данное отношение A строгим порядком, достаточно убедиться, что:

¢ \ A = ? – A антирефлексивно; A2 µ A – A транзитивно.

2. Проверка на линейный (совершенный строгий) порядок

КРИТЕРИЙ 1. Пусть A – строгий порядок на конечном M, jMj = n.

A линейный порядок тогда и толькотогда, когда

Ai 6= ?; i < n; An = ?.

Д о к а з а т е л ь с т в о . Пусть A – линейный порядок.

1. (Базис индукции). Пусть n = 2; i = 1; выполнение xAy ) A1 6= ?. Пусть A2 =6 ?, т.е. выполняются соотношения xAz ^ zAy.

Так как A транзитивное и антирефлексивное, то x; y; z – разные. Этого не может быть, так как n = 2.

2. (Шаг индукции). Пусть утверждение справедливо для n ¡ 1. Докажем его справедливость для n.

An¡2 6= ?; An¡1 6= ? (по индукции).

Значит имеется цепочка

z1Az2; z2Az3; : : : ; zn¡2Azn¡1; An¡1 6= ?.

Добавление еще одной степени равносильно добавлению одной лишней вершины в графе. An = ?, так как все zi – разные.

КРИТЕРИЙ 2. Пусть A – линейный порядок на конечном M, jMj = n. Образуем множества

M1 = fyjyAxg; M2 = fyjxAyg,

где M1 – множество элементов M, из которых дуги заходят в x, а M2 – множество элементов M, в которые заходят дуги из x, и назовем jM1j степенью захода в x, а jM2j – степенью

исхода из x.

Тогда для всех x, если

jM1j + jM2j = jMj ¡ 1, то порядок линейный; в противном случае порядок не линейный.

Пример 2.31. Пример графа линейного порядка представлен на рисунке 2.14.

Рис. 2.14. Линейный порядок

Пусть множество A упорядочено (частич- Решетки но) отношением 4 и пусть ? ½ B µ A.

Определение. Элемент a 2 A называется верхней (нижней) гранью (границей) B тогда и только тогда, когда b 4 a (a 4 b) для всех b 2 B.

Наименьший (наибольший) элемент множества всех верхних (нижних) граней B называется точной верхней (нижней) гранью (границей) множества B и обозначается sup B (inf B).

Пример 2.32.

1. Пусть множество B(f1; 2; 3g) упорядочено (частично) отношением µ и пусть B1 = ff1g; f2gg, B2 = ff1g; f1; 2gg.

B(f1; 2; 3g) = f?; f1g; f2g; f3g; f1; 2g; f1; 3g; f2; 3g; f1; 2; 3gg.

Множество верхних граней для B1 есть ff1; 2g; f1; 2; 3gg; sup B1 = f1; 2g. Нижняя грань для B1 есть ?: inf B1 = ?. Ни одна из граней не принадлежит B1.

Для B2 множество верхних граней есть ff1; 2g; f1; 2; 3gg, множество нижних граней — f?; f1gg; sup B2 = f1; 2g, inf B2 = f1g.

2. Пусть множество A = fa; b; cg упорядочено по отношению тождества ´. Единственные подмножества A, имеющие верхнюю и нижнюю грани есть fag; fbg; fcg. Например, supfag = inffag = a. J

Определение. Пусть 4 — некоторый порядок (частичный) на множестве M. Элемент z 2 M называется непосредственно следующим за элементом x 2 M тогда и только тогда, когда x 4 z и не существует такого y 2 M, что x 4 y 4 z.

Для строгого порядка Á, например, непосредственно следующим за x является элемент z из редукции xÁrz.

Пусть задано упорядоченное множество h4; Mi. Представим каждый элемент x 2 M точкой на плоскости. Рассмотрим все упорядоченные пары hxi; xji 2 M £ M. Поме-

стим точку xj над точкой xi только тогда, когда xi 4 xj и соединим точки xi; xj линией, если xj непосредственно следует за xi.

В результате получится диаграмма, в которой существует маршрут от точки xm к точке xn, если xm 4 xn. Такие диаграммы по имени их автора называют диаграммами Хассе.

Примеры 2.33.

1. Для упорядоченного множества h6; Ai, где A = f1; 2; 3; 4g, диаграмма Хассе представлена на рис. 2.15, a.