Способы описания бинарного отношения
Бинарное отношение Â как любое подмножество может быть представлено в виде перечисления, через указания свойства или через порождающую процедуру. Но наиболее часто используется представление матрицей, в котором учитывается специфика множества. Столбцам и строкам матрицы сопоставлены элементы базового множества A, значение элемента матрицы (ai,aj) равно 1, если (ai,aj)Î Â, в противном случае значение соответствующего элемента равно 0.
Виды бинарных отношений
Бинарное отношение называется рефлексивным, если "(ai)Î A
(ai,ai)Î Â.
Если отношение является рефлексивнымое, то в каждой клетке главной диагонали стоят единицы.
Бинарное отношение антирефлексивно, если "(a i)Î A (ai,ai) Ï Â.
В антирефлексивном отношении главная диагональ не содержит ни одной единицы.
Бинарное отношение называется симметричным, если из того, что (ai,aj)Î Â, следует (aj,ai)Î Â.
Для симметричного отношения таблица симметрична относительно главной диагонали.
Бинарное отношение антисимметрично, если из того, что (ai,aj)Î Â, следует, что(aj,ai)Ï Â.
Бинарное отношение называется транзитивным, если из того, что (ai,aj) Î Â и (aj,ak) Î Â, следует (a i, ak)Î Â.
Эквивалентность
Бинарное отношение называется отношением эквивалентности, если оно одновременно рефлексивно, симметрично и транзитивно.
Два элемента связаны отношением эквивалентности, если они имеют одинаковое свойство из множества альтернативных свойств. Примерами таких отношений являются принадлежность студентов к одной учебной студенческой группе, отношение родства или отношение «иметь одинаковый цвет волос». Альтернативность предполагает, что случаи, когда один студент принадлежит к нескольким группам или один человек имеет разноцветные волосы, из рассмотрения исключаются (иначе не выполнялась бы транзитивность). Тогда множество разбивается на непересекающиеся подмножества элементов, удовлетворяющие свойству, которые при объединении покрывают все множество. Последнее обеспечивается свойством рефлексивности, когда для каждого элемента находится элемент, с которым он находится состоит в отношении - (по крайней мере, с самим собой). Эти подмножества называются классами эквивалентности.
Справедливо утверждение: любому отношению эквивалентности однозначно сопоставляется разбиение множества и, обратно, любому разбиению множества однозначно сопоставляется отношение эквивалентности.
Отношение порядка
Говорят, что отношение Â отвечает свойству дихотомии, если из того, что (ai,aj)Ï Â, следует, что (aj,ai)Î Â. Значит, если выполняется свойство дихотомии, то в множестве любые два элемента находятся в данном отношении. Примером дихотомии может служить отношение «быть по возрасту не старше» между людьми. Здесь, если Иван старше Петра, то, значит, Петр не старше Ивана.
Отношение Â называют отношением порядка, если оно антисимметрично и транзитивно. Если при этом отношение рефлексивно, то оно называется отношением нестрогого порядка, если антирефлексивно – то отношением строгого порядка.
Отношение нестрогого порядка между элементами ai и aj обозначается, ai £ aj, отношение строгого порядка – ai < aj.
Приведенное выше отношение «быть не старше» является отношением нестрогого порядка, так как оно является и рефлексивнымое, и антисимметричнымое, и транзитивным транзитивное. Примером отношения строгого порядка будет определенное на множестве людей отношение «быть старше», так как любой человек не может быть старше себя.
И, наконец, если ввести в отношение необходимость дихотомии, то получим соответственно отношение полного нестрогого или полного строгого порядка.
Если в отношении условия дихотомии не выполняются, то отношение называется отношением частичного порядка.
Если на множестве людей определить отношение «быть начальником по службе» и если считать, что начальник моего начальника является моим начальником (выполняется транзитивность), то это есть частичный порядок, ибо люди, работающие в разных организациях, в этом отношении не находятся. Строгий это порядок или нет, определится тем, считаем ли мы себя начальниками по службе для самих себя или нет.
Элемент ai непосредственно следует за aj, если ai < aj и не найдется такого ak, что ai < ak < aj. Значит, для любых элементов ai и aj,таких, что
ai < aj, найдется цепочка элементов между ai и aj, в которой любой элемент непосредственно следует за предыдущим. Все такие цепочки определяют схему транзитивного отношения.
Для полного множества, когда любая пара элементов находится в отношении, цепочка будет единственной. Если множество А конечно, то при полном порядке всегда найдется единственный элемент а max такой, что " а Î А а max > a. Этот элемент называют максимальным.
Аналогично для конечного множества в этом случае найдется минимальный элемент, меньший любого элемента из А.
Для частичного порядка в конечном множестве минимального и максимального элементов может и не быть. Назовём наибольшим элементом такой элемент, для которого не найдется в А элемента, большего его. Точно так же определим как наименьший такой элемент, для которого в А нет меньших его. Наибольших элементов (как и наименьших) может быть несколько, они образуют верхнюю (нижнюю) грань множества по данному отношению.
Рассмотрим схему отношения на примере.
Пусть на множестве А ={1,2,3,4,5,6} задано отношение {(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5)(2,6),(3,4), (3,5),(3,6), (4,5), (4,6)}. Тогда цепочками схемы будут (1,3,4,5), (1,3,4,6), (2,3,4,5), (2,3,4,6), что определяет схему, которую удобно представить в виде рис.2.21.
В этом примере элементы 1 и 2 – наибольшие, элементы 5 и 6 – наименьшие. Они образуют соответственно верхнюю и нижнюю грани множества по отношению.
Отношения, в которых есть антисимметрия, но нет транзитивности, называют предпорядком или отношением доминирования. Примером такого отношения может служить заданное на множестве футбольных команд отношение «победа в игре». Действительно, из того, что УРАЛМАШ победил РОТОР, а РОТОР победил ДИНАМО, не следует,
что УРАЛМАШ победит ДИНАМО, то естьт.е. свойство транзитивности здесь не выполняется.
Рис.2.21
Замыкание отношений
Пусть на множестве А задано два отношения RR и S S. Определим отношение Q как результат операции транзитивного продолжения отношений R R на SS, если(ai,ak)Î Q)Î Q тогда и только тогда, когда (ai, aj)Î R)Î R и (aj,ak)Î S.)Î S. Обозначим это Q = R°S. = R°S. Если RR = S, S, то обозначим S°S = SS° S = S 2, и, по аналогии, введем k-ю степень транзитивного продолжения как последовательное выполнение (k+1) раз операции °. Обозначим S как SS 1.
Пример Пример. Пусть на множестве всех людей задано бинарное отношение Â R «быть отцом». Тогда ÂR 2 будет соответствовать бинарное отношение «быть отцом отца» или, что то же самое, «быть дедом по отцу».
Транзитивным замыканием (или просто замыканием) отношения Â называется бесконечное объединение ÈÂRi . Обозначим замыкание как R *, т.е. R =ÂÈ*= R È ÂR 2 È...È Â È...È R k = Â * .
Пример Пример. Пусть на множестве целых чисел N задано отношение Â ={(R ={(x,y) | y=x +1}. Тогда замыканием Â * R * будет отношение {(x x, y) | x < y }.
Основные понятия комбинаторики
Пусть задано декартово произведение R = A1xA2x … x xA n. Элементы этого множества назовём n-выборкой.
Чаще всего все сомножителия произведения равны, то естьт.е. R = A n. Элемент этого множества называют ещё упорядоченной n-выборкой или размещением из m элементов по n. Здесь m - – число элементов в множестве А.
Число элементов в An (число размещений из m элементов по n) равно mn. Эта величина обозначается Pnm.
Два размещения равны, если попарно равны все их компоненты.
Если n=m, то это размещение называют перестановкой m элементов. Число различных перестановок равно mm.
Пример Пример. Пусть множество A = {1,2,3,4} и n=2. Тогда A n=
{(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3), (4,4)}. Число элементов в A n =16.
Число упорядоченных n-выборок без повторения элементов в выборках (размещений из m элементов по n без повторения) равно m!/(m-n)!.Эту величину принято обозначать Anm или (m/n).
Пример Пример. Построим все размещения по 2из 4 элементов множества А рассмотренного примера по 2, получим {(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)}. Это множество содержит 12 элементов (4!/2!=(4×3×2)/2).
При n = m Amnm= m! – число перестановок из m элементов.
Если в n-выборке не учитывать порядок компонент, то выборка называется неупорядоченной выборкой или сочетанием из m элементов по n.
Две неупорядоченные n-выборки равны, если каждая из них состоит из одних и тех же компонент из А, взятых одно и то же число раз.
Число неупорядоченных n выборок из m элементов без повторения (сочетаний без повторения), обозначаемое как N(m,n)= Anm/n! = C C nm, где C C nm – коэффициенты из биномиальной теоремы, получаемые по треугольнику Паскаля. C C nm= m! / (n!×(m-n)!)
Пример Пример. Множество всех возможных сочетаний из 4 элементов по 2 будет {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}.
Число элементов в этом множестве (4×3×2/2×2) =6.
Число неупорядоченных n - выборок из m с повторением будет C C nm+n-1 Пример Пример. Множество неупорядоченных 2 - выборок из 4 будет {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}. Их число равно (5×4×3×2/3×2×2).
Задачи комбинаторики.
Выделяют следующие задачи в комбинаторикеи:
1. Задача пересчёта. Сколько элементов из заданного множества имеют некоторое свойство.?
2. Задача перечисления. Перечислить элементы, обладающие заданным свойством.
3. Задача классификации. Если пересчёт приводит к большим числам, то элементы классифицируются с помощью какого-то соотношения.
4. Задача минимизации. На множестве элементов вводят задана некоторую некоторая функциюфункция, необходимо найти элементы с экстремальными значениями этой функции.
| Табл.2.1 | |||||
| Таблица 2.1 | |||||
Рассмотрим эти задачи на примере. Пусть задан квадрат, разделённый на kхk клеток (например, 5х5, см.табл.2.1).
Необходимо разместить в нём k единичек так, чтобы в каждой строке и каждом столбце было по одной единичке.
1. Задача пересчёта. Сколько вариантов решения существует? Для заданного примера это число будет k!, или: 5!=120.
2. Задача перечисления. Перечислить все 120 вариантов.
3. Задача классификации. Будем рассматривать квадрат как матрицу смежности ориентированного графа. Тогда приведенному в табл. 2.1 квадрату будет соответствовать граф рис 2.2.
Будем классифицировать варианты по одинаковости этого графа с точностью до имен его вершин. Сколько типов графов здесь возможно и каковы они?
| Табл. 2.2 | |||||
| Таблица 2.2 | |||||
4. Задача минимизации. Сопоставим каждой клетке графа целое число (табл. 2.2). Задача заключается в выборе варианта, для которого сумма чисел в отмеченных единичками клетках будет максимальна. Эта задача может быть представлена как задача построения максимального совершенного паросочетания в двудольном графе, описанном данной матрицей. Эта задача будет рассмотрена в следующей главе.
Пояснение. Биномиальные коэффициенты C C kn определяют коэффициенты при k-ой степени a при разложении выражения (1+ a)n. Здесь 1 соответствует a 0. Тогда C C 01=1 и C C 11=1, C C 02=1, C C 12=2, C C 22=1.
Паскаль предложил считать коэффициенты C C kn рекурсивно по следующему треугольнику (треугольник Паскаля, рис.2.3.). Здесь вершины расположены по горизонтальным рядам – ярусам. Ярусы нумеруются сверху вниз последовательно 1, 2, 3 и т.д.. Номер яруса определяет число n. Числа у вершин нижнего яруса получаются как сумма чисел вершин верхнего яруса, от которых к ней идут стрелки. Номер вершины в ярусе (число k) равен месту вершины в ярусе, начиная слева.
2.7. Контрольные вопросы и задания
Свойства бинарных отношений.
Докажите или опровергните следующие утверждения
1: Если отношения А и В рефлексивны, то рефлексивны и отношения
А È В, А Ç В.
2: Если отношения А и В симметричны, то симметричны и отношения
А È В, А Ç В.
3: Если отношение А асимметрично, то пересечение А Ç В асимметрично при любом В.
4: Если отношения А и В антисимметричны, то антисимметрично и отношение А Ç В.
5: Если отношения А и В транзитивны, то транзитивно и отношение
А Ç В.