св-ва бинарных отношений: рефлексивность, симметричность, интисимметричность, транзитивность

Свойства:

1. R – рефлексивно, если "а: (а;а)ÎR

Тогда в матрице отношения R на главной диагонали стоят только единицы: "i c_ii=1

2. R – не рефлексивно, если $а: (а;а)ÏR

На главной диагонали матрицы есть хотя бы один ноль.

3. R – антирефлексивно, если "а: (а;а)ÏR

Тогда на главной диагонали матрицы стоят только нули: "i c_ii=0.

4. R – симметрично, если "а,b: (a;b)ÎR Þ (b;a)ÎR.

Тогда в матрице отношения "i,j: c_ij=с_ji=1_. Значит, матрица симметрична относительно главной диагонали.

5. R – не симметрично, если $a,b: (a;b)ÎR и (b;a)ÏR

6. R – антисимметрично, если "a¹b. (a;b)ÎR Þ (b;a)ÏR, т.е. ни для каких различных a и b (a¹b) не выполняется одновременно (a;b)ÎR и (b;a)ÎR. Если же (a;b)ÎR и (b;a)ÎR, то a=b. Тогда в соответствующей матрице отношения ни для каких i,j: i¹j не выполняется Cij=Cji=1. Таким образом, отсутствуют единицы, симметричные относительно главной диагонали.

7. R – транзитивно, если того, что "a,b,c: (a,b)ÎR и (b,c)ÎR следует, что (a,c)ÎR.

В матрице такого отношения должно выполняться след условие: если c_ij=1 и c_jk=1 "i, j, k

Говорят, что в М задано бинарное отношение Т, если М´М есть декартово произведение и в М´М выделено произвольное подмн-во Т. Таким образом, произвольное подмн-во ТÌМ´М есть бинарное отношение.

Мы будем говорить, что эл-т a находится в отношении Т к эл-ту b в том и только в том случае, когда пара (а,b) принадлежит мн-ву Т. Для этого возможны два равносильных способа обозначения: аТb или (а,b)ÎТ.

21. Понятие подграфа. Реберно-порожденный подграф. Основные операции над графами. Подграфом G1=(V1, А1) графа G =(V, А) наз часть графа, кот сама явл графом. G =(V, А). Пусть V1Ì V и А1Ì А; G1=(V1, А1). G1 явл подграфомóдля " (Xi, Xj)ÎА1 $ верш, инцид ему и Î V1 Граф G1=(V1, А1) наз реберно-порожд. подграфом графа G, когда V1 содержит все вершины графа G, инцидентные ребрам из А1. Операции над графами:

1) Объединение двух графов G1=(V1, A1) и G2=(V2, A2) есть граф S=(V1ÈV1,A1ÈA2).На рисунке 1 показано объединение двух графов.

2) Пересеч. двух графов G1=(V1, A1) и G2=(V2,A2) есть граф S=(V1∩V2,A1∩A2).

3) Кольцевая сумма двух графов G1ÅG2 есть граф, не имеющий изолированных вершин и состоящий только из ребер, присутствующих либо в G1, либо в G2, но не в обоих графах одновременно. Т.о. это Е1ÅЕ2 реберно-порожденный граф. G1ÅG2=(G1 \ G2)È(G2 \ G1)

4) Разностью графов G1=(V1, А1) и G2=(V2, А2) наз-ся граф G =(V, А) где А=А1 А2 и G явл реберно-порожд. подграфом графа G1.

5) Дополнение графа G наз-ся граф G1 с теми же вершинами, что и граф G и с ребрами, кот-е надо добавить к графу G чтобы получить полный граф. Полный граф – все его вершины смежны между собой.

9. Отношение эквивалентности, определения, примеры. Теоремы о связи разбиения множества и отношением эквивалентности на нем Бинарное отношение ТÌМ´М называется отношением эквивалентности, заданном на мн-ве М, тогда и только тогда, когда оно удовлетворяет следующим трем усл-виям: "a, aÎM Þ (a,a)ÎT, т.е. отношение Т удовлетворяет усл-вию рефлексивности "a"b, aÎM, bÎM если (a,b)ÎT, то (b,a)ÎT, т.е. отношение Т удовлетворяет усл-вию симметричности "a"b"c, aÎM, bÎM, cÎM если (a,b)ÎT и (b,c)ÎT, то (a,c)ÎT, т.е. отношение Т удовлетворяет усл-вию транзитивности Таким образом, эквивалентность есть бинарное отношение, удовлетворяющее усл-виям рефлексивности, симметричности и транзитивности. Отношение равенства чисел есть отношение эквивалентности, т.к. является рефлексивным, симметричным и транзитивным. А бинарное отношение «<» для чисел не явл отношением эквивалентности, т.к. оно не удовлетворяет условию симетричности. Разбиение множества. Пусть А — произвольное множество. Семейство непустых и попарно не пересекающихся множеств называют разбиением множества А, если объединение множеств семейства равно А, то есть Для любого отношения эквивалентности на множестве А множество классов эквивалентности образует разбиение множества А. Обратно, любое разбиение множества А задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения. отношение эквивалентности P на множестве A определяет некоторое разбиение этого множества. Убедимся вначале, что любые два класса эквивалентности по отношению P либо не пересекаются, либо совпадают.   Пусть два класса эквивалентности [X]p и [Y]p имеют общий элемент . Тогда и . В силу симметричности отношения P имеем , и тогда и . В силу транзитивности отношения P получим X P Y. Пусть , тогда . Так как , то и, следовательно, . Обратно, если , то в силу симметричности получим и в силу транзитивности — , то есть . Таким образом, . Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого справедливо (поскольку ), т.е. каждый элемент множества A принадлежит некоторому классу эквивалентности по отношению P, то множество всех классов эквивалентности по отношению P образует разбиение исходного множества A. Таким образом, любое отношение эквивалентности однозначно определяет некоторое разбиение. Теперь пусть — некоторое разбиение множества . Рассмотрим отношение P, такое, что имеет место тогда и только тогда, когда X и Yпринадлежат одному и тому же элементу данного разбиения: Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых и имеет место и , то и в силу определения отношения принадлежат одному и тому же элементу разбиения. Следовательно, и отношение P транзитивно. Таким образом, P — эквивалентность на A.       31Отношения нестрогого порядка, определения, примеры. Говорят, что отношение нестрогого порядка задано на мн-ве М, если Т есть бинарное отношение, подчиненное следующим трем усл-виям: 1) "а, аÎМ Þ (а,а)ÎТ, т.е. отношение Т удовлетворяет условию рефлексивности 2) "a"b, aÎМ, bÎМ, если (a,b)ÎТ и (b,a)ÎТ, то a=b, т.е. отношение Т удовлетворяет условию антисимметричности 3) "a"b"c, aÎМ, bÎМ, cÎМ, если (a,b)ÎТ и (b,c)ÎТ, то (a,c)ÎТ, т.е. отношение Т удовлетворяет условию транзитивности Таким образом, отношение нестрогого порядка есть бинарное отношение, удовлетворяющее усл-виям рефлексивности, антисимметричности и транзитивности. Пример 1. Отношение «£» для чисел есть отношение нестрогого порядка. Действительно, для любых действительных чисел a,b,c выполняются все три условия: а£а; если а£b и b£a, то a=b; если a£b и b£c, то a£c. Пример 2. Отношение «быть подмн-вом» также явл отношением нестрогого порядка, т.к. любое мн-во явл подмн-вом самого себя, а также, если АÌВ и ВÌА, то А=В, и, наконец, если АÌВ и ВÌС, то АÌС. Отношения строгого порядка, определения, примеры. Говорят, что на мн-ве М задано отношение строгого порядка Т, если есть бинарное отношение, подчиненное следующим трем усл-виям: 1) "a, aÎM Þ (a,a)ÏT, т.е. отношение Т удовлетворяет усл-вию антирефлексивности 2) "a"b, (a,b) и (b,a) не могут принадлежать Т одновременно, т.е. отношение Т удовлетворяет усл-вию несимметричности 3) "a"b"c, aÎM, bÎM, cÎM если (a,b)ÎT и (b,c)ÎT, то (a,c)ÎT, т.е. отношение Т удовлетворяет усл-вию транзитивности Таким образом, отношение строгого порядка есть бинарное отношение, удовлетворяющее усл-виям антирефлексивности, несимметричности и транзитивности. Пример 1. Отн-е «<» для чисел есть отн-е строг порядка. Так, про любое действит число a нельзя сказать, что a<a, для любых 2х действит чисел a,b либо a<b, либо b<a, и значит, они не могут иметь место одновременно. А для любых 3х чисел: если a<b и b<c, то a<c. Пример 2. Отн-е между людьми «один старше др» также явл отн-ем строгого порядка. 22. Числовые характеристики графа: цикломатическое число, хроматическое число. Раскраска графов. Цикломатическим числом ν(G) графа G наз. наименьшее число ребер, удаление которых приводит к графу без циклов; ν(G) =m-n+k. где т - число ребер, n - число вершин, k - число компонент связности графа G. Хроматическим числом χ(G) наз. наименьшее количество цветов, которыми можно раскрасить вершины графа G так, чтобы любые смежные вершины были окрашены разными цветами. Правила раскраски графов: 1) Раскрашиваем вершины графа 2) 2 смежные вершины – разного цвета 3) Экономим краски. 4) Начинаем раскрашивать с….   10. Упорядоченные мн-ва, определения, примеры. Два эл-та aÎM и bÎM являются сравнимыми в данном порядке TÌM´M, если про них можно сказать, что (a,b)ÎT или (b,a)ÎT, или a=b. Мн-во М с введенным порядком Т является упорядоченным (линейно упорядоченным), если любые два эл-та этого мн-ва являются сравнимыми. Про мн-во М, на котором просто введен некоторый порядок Т, т.е. в котором существуют сравнимые эл-ты, говорят, что оно частично упорядоченно. Св-вом упорядоченности обладает мн-во всех точек на действительной числовой прямой R, т.к. любые два действительных числа можно сравнить между собой. Для отношения «быть собственным подмн-вом» это св-во не имеет места, т.к. по отношению включения можно сравнить далеко не все подмн-ва. Например, числовой интервал (-2,5) нельзя сравнить с отр-ком [0,7] по отношению включения. Таким образом, это мн-во является частично упорядоченным. Среди линейно упорядоченных мн-в выделяют вполне упорядоченные мн-ва. Для его определения введем определение усл-вия минимальности. Говорят, что мн-во М удовлетворяет усл-вию миним-ти для некот отн-ния порядка Т, если в люб его непуст подмн-ве XÌM существует такой эл-т a, что "x xÎX, имеет место: аТх. Итак, мн-во назыв вполне упоряд-ым, если оно явл лин упоряд-ым и удовлетворяет усл-вию миним-ти. Например, мн-во натур чисел явл вполне упоряд-ым, а мн-во действит чисел не явл вполне упорядоченным, т.к. для интервалов не сущ-ет минимального эл-та. Обратим внимание на то, что одно и то же мн-во может быть линейно упорядоченным относительно одного порядка и лишь частично упорядоченным относительно другого. Например, мн-во людей с введенным отн-ем старшинства явл лин упоряд-ным (роль рав-ва играет отн-ние «быть ровесниками»), а это же мн-во с отн-нием «быть предком» не явл лин упоряд-ным, т.к. про любых 2х людей нельзя сказать, что один явл-ся предком другого. 34 Операции над бинарными отношениями Так как отношения на Х задаются подмножествами rНXґY, для них определимы те же операции, что и над множествами: 1. Объединение r1Иr2: r1Иr2={(х, у)| (х, у)Оr1 или (х, у)Оr2}. 2. Пересечение r1Зr2: r1Зr2={(х, у)| (х, у)Оr1 и (х, у)Оr2}. 3. Разность r1\r2: r1\r2={(х, у)| (х, у)Оr1 и (х, у)П r2}. 4. Дополнение : . 5. Обратное отношение r -1: х r -1 у тогда и только тогда, когда уrх, r -1={(x, y)| (y, x)Оr}. Пример 13. Если r - «быть моложе», то r -1 – «быть старше». 6. Составное отношение (композиция) r1 · r2. Пусть заданы множества М1, М2 и М3 и отношения R1 Н М1 ґ М2 и R2 Н М2 ґ М3. Составное отношение действует из М1 в М2 посредством R1, а затем из М2 в М3 посредством R2, то есть (a, b) О R1·R2, если существует такое с О М2, что (а, с) О R1 и (a, c) О R2. 7. Транзитивное замыкание r°. Транзитивное замыкание состоит из таких и только таких пар элементов а и b из М, то есть (a, b)Оr°, для которых в М существует цепочка из (k+2) элементов М, kі 0, что а, с1, с2, …ck, b, между соседними элементами которой выполняется r. Другими словами а r с1, с1 r с2, …, сk r b. Пример 14. Для отношения «быть сыном» транзитивным замыканием является отношение «быть прямым потомком по мужской линии».