18. Метод математической индукции
![]()
|
7. Декартово пр-ние мн-в и его св-ва. Геометр интерпретация декарт пр-ний. Декартовым или прямым пр-нием мн-в А и В называют мн-во АВ всех упорядоченных пар эл-тов (a,b), где aA, bB, т.е. АВ=С= ![]() Если одно из мн-в А или В пусто, то произв-нием АВ будет пустое мн-во. Известным примером явл-ся мн-во декартовых координат в прямоугольной сис-ме корд-т. Св-ва декартова пр-ния:
Для док-ва этих фактов достаточно привести примеры, когда коммутативность и ассоциативность не выполняются: Пример 1. Пусть A={1}, В={2,3}, тогда АВ={(1,2),(1,3)}, BA={(2,1),(3,1)}. Обратим внимание, что в случае, когда А=В, переместительный закон имеет место. П ![]() Декартовым произведением явл плоскость. Например, А=[0,1] и В=[1,2), тогда АВ: Если А=В, то АВ =А2. Если одно из множеств является , то АВ= | 21. Компоненты связности, мосты. Критерий моста. Граф G наз связным, если для любых 2-х его вершин сущ путь, связ-й их, иначе граф наз несвязным. несвязн граф распад-ся на связные подграфы,кажд из кот явл компонентой связности. Компонента связности – максимально связный подграф. Подграфом G1=(V1, А1) графа G=(V, А) наз часть графа, кот сама явл графом. G=(V, А). Пусть V1 V и А1 А ; G1=(V1,А1). G1 явл подграфомдля (Xi, Xj)А1 верш, инцид ему и V1. Несвязный граф облад. таким св-вом, что люб. верш. не связана ни с одной верш. другой компоненты никаким путем. Мостом наз такое ребро, при удалении кот-го число комп. связности увел-ся. Т(критерий моста): Ребро графа G явл мостом оно не ни 1 из циклов. Док-во => от противного. Предпол. что сущ цикл, кот ребро (Хi,Хj) явл. мостом. При удал. (Хi,Хj) число комп. связн. увелич. (по опр. моста), и для Хk, Хn из разных комп-т нет пути, их соединяющего, а до удал. (Хi,Хj) путь был, содержал (Хi,Хj) и имел путь: {(Xк, Xк+1)…(Xi,Xj)… (Xn-1, Xn)}). заменив (Хi,Хj) на обходной путь (т.к. ребро циклу) получ новый путь из Хk в Хn. Получ. противоречие. Док-во <= Предполож, что такое ребро (Хi,Хj), кот не явл-ся мостом и не ни одному из циклов. Тогда удалим (Хi,Хj). Т.к. (Хi,Хj) – не мост, то число компонент связности не изменилось, путь из Хi в Хj {Xi,Xi+1,…Xj-1,Xj}. Восстановив ребро (Хi,Хj) получ. цикл. Противоречие. Ч.т.д. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
8. Понятие бинарного отношения, способы задания отношений интерпритация графа, как бин отн-гий, задание графа с помощью матрицы Отношение – бинарное отношение – любое подмножество вида АА. Пусть A=R, в этом случае отношение “<” означает множество пар декартовой плоскости, расположенное левее биссектрисы 1 и 3 координатных углов. пример А{123456}, R{(ai;aj)(ai:.aj)}
8. св-ва бинарных отношений: рефлексивность, симметричность, интисимметричность, транзитивность. Свойства:
Тогда в матрице отношения R на главной диагонали стоят только единицы: i cii=1
На главной диагонали матрицы есть хотя бы один ноль.
Тогда на главной диагонали матрицы стоят только нули: i cii=0.
Т ![]()
В матрице такого отношения должно выполняться след условие: если cij=1 и cjk=1 i, j, k Говорят, что в М задано бинарное отношение Т, если ММ есть декартово произведение и в ММ выделено произвольное подмн-во Т. Таким образом, произвольное подмн-во ТММ есть бинарное отношение. Мы будем говорить, что эл-т a находится в отношении Т к эл-ту b в том и только в том случае, когда пара (а,b) принадлежит мн-ву Т. Для этого возможны два равносильных способа обозначения: аТb или (а,b)Т. | 21. Понятие подграфа. Реберно-порожденный подграф. Основные операции над графами. П ![]() Граф G1=(V1, А1) наз реберно-порожд. подграфом графа G, когда V1 содержит все вершины графа G, инцидентные ребрам из А1. Операции над графами:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
9. Отношение эквивалентности, определения, примеры. Теоремы о связи разбиения множества и отношением эквивалентности на нем Бинарное отношение ТММ называется отношением эквивалентности, заданном на мн-ве М, тогда и только тогда, когда оно удовлетворяет следующим трем усл-виям: a, aM (a,a)T, т.е. отношение Т удовлетворяет усл-вию рефлексивности ab, aM, bM если (a,b)T, то (b,a)T, т.е. отношение Т удовлетворяет усл-вию симметричности abc, aM, bM, cM если (a,b)T и (b,c)T, то (a,c)T, т.е. отношение Т удовлетворяет усл-вию транзитивности Таким образом, эквивалентность есть бинарное отношение, удовлетворяющее усл-виям рефлексивности, симметричности и транзитивности. Отношение равенства чисел есть отношение эквивалентности, т.к. является рефлексивным, симметричным и транзитивным. А бинарное отношение «<» для чисел не явл отношением эквивалентности, т.к. оно не удовлетворяет условию симетричности. Разбиение множества. Пусть А — произвольное множество. Семейство ![]() ![]() ![]() Для любого отношения эквивалентности на множестве А множество классов эквивалентности образует разбиение множества А. Обратно, любое разбиение множества А задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения. отношение эквивалентности P на множестве A определяет некоторое разбиение этого множества. Убедимся вначале, что любые два класса эквивалентности по отношению P либо не пересекаются, либо совпадают. Пусть два класса эквивалентности [X]p и [Y]p имеют общий элемент ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Обратно, если ![]() ![]() ![]() ![]() ![]() ![]() Итак, любые два не совпадающих класса эквивалентности не пересекаются. Так как для любого ![]() ![]() ![]() Теперь пусть ![]() ![]() ![]() ![]() ![]() Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 31Отношения нестрогого порядка, определения, примеры. Говорят, что отношение нестрогого порядка задано на мн-ве М, если Т есть бинарное отношение, подчиненное следующим трем усл-виям:
Таким образом, отношение нестрогого порядка есть бинарное отношение, удовлетворяющее усл-виям рефлексивности, антисимметричности и транзитивности. Пример 1. Отношение «» для чисел есть отношение нестрогого порядка. Действительно, для любых действительных чисел a,b,c выполняются все три условия: аа; если аb и ba, то a=b; если ab и bc, то ac. Пример 2. Отношение «быть подмн-вом» также явл отношением нестрогого порядка, т.к. любое мн-во явл подмн-вом самого себя, а также, если АВ и ВА, то А=В, и, наконец, если АВ и ВС, то АС. Отношения строгого порядка, определения, примеры. Говорят, что на мн-ве М задано отношение строгого порядка Т, если есть бинарное отношение, подчиненное следующим трем усл-виям:
Таким образом, отношение строгого порядка есть бинарное отношение, удовлетворяющее усл-виям антирефлексивности, несимметричности и транзитивности. Пример 1. Отн-е «<» для чисел есть отн-е строг порядка. Так, про любое действит число a нельзя сказать, что a Пример 2. Отн-е между людьми «один старше др» также явл отн-ем строгого порядка. |