шпаргалка по дискретной математике

1 Понятие множества, подмножества, пустого множества. Диаграммы Вейля. Мн-во неопределенное понятие, которое характеризуют перечисление его свойств. Подмн-во А мн-ва В мн-во, состоящее из элементов, обладающих следующим св-вом , т.е. А В. Если мн-во А явл. подмн-вом В и мн-во В явл подмн-вом А, то А В. Если мн-во А явл подмн-вом В и при этом они не равны, то мн-во

А называют собственным подмн-вом мн-ва В. Мн-во, которое не содержит эл-тов, называется пустым мн-вом и обозначается символом . Рисунки вида называются диаграммами Вейля. Они графически отображают множества. 17 Отношение эквивалентности, определения, примеры. Бинарное отношение Т М М называется отношением эквивалентности, заданном на мн-ве М, тогда и только тогда, когда оно удовлетворяет следующим трем усл-виям 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, т.е. отношение Т удовлетворяет усл-вию транзитивности Таким образом, эквивалентность есть бинарное отношение, удовлетворяющее усл-виям рефлексивности, симметричности и транзитивности.

Отношение равенства чисел есть отношение эквивалентности, т.к. является рефлексивным, симметричным и транзитивным. А бинарное отношение lt для чисел не явл отношением эквивалентности, т.к. оно не удовлетворяет условию симметричности. 2 Оп-ции об-ния, перес-ния мн-в, опр-ние и св-ва ком-ти и ассоц-ти. Суммой или объединением 2х мн-в А и В называется мн-во С, состоящее из всех элементов, принадлежащих хотя бы одному из мн-в

А и В, т.е. А В Пересечением 2х мн А и В наз-ся мн С, сост из всех эл-тов, принадл-их как мн А, так и мн-ву В, т.е. А В . мн А и В не имеют общ эл-тов их перес-ем явл пуст мн. Аналогично определяется об-ние и перес-ние любого конеч или бесконеч числа мн-в. Если Ai произвол мн-ва, то их сумма объединение А есть совокупность элементов, каждый из которых принадлежит

хотя бы одному из мн-в Ai. Это обозначается . Пересечением люб конеч или бесконеч числа мн-в Ai называется совокупность А элементов, принадлежащих каждому из мн-в Ai. Это обозначается . Оп-ции объед-ния и перес-ния ком-ны, т.е. для них выполняется переместит закон А В В А А В В А Также эти операции ассоциативны, т.е. для них выполняется сочетательный закон А В С А В С А В С А В С Эти св-ва операций следуют из их определения.

18 Отношения нестрогого порядка, определения, примеры. Говорят, что отношение нестрогого порядка задано на мн-ве М, если Т есть бинарное отношение, подчиненное следующим трем усл-виям 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. Отношение быть подмн-вом также явл отношением нестрогого порядка, т.к. любое мн-во явл подмн-вом самого себя, а также, если А В и В А, то А В, и, наконец, если А В и В С, то А С. 3 Взаимная дистрибутивность операций пересечения и объединения.

Операции пересечения и объединения взаимно дистрибутивны, т.е. для них выполняется распределительный закон А В С А С В С 1 А В С А С В С 2 Док-ва этих теоретико-множественных равенств проводятся в обе стороны, т.е. для док-ва того, что А В, показывают, что с одной стороны А В, а с другой стороны А В. Док-во 1 . А В С А С В С , x, x А В С x A или х В и х С х А и х С или х В и х

С х А С или х В С х А С В С А В С А С В С док-ся аналогично, все стрелки можно обернуть. Док-во 2 . А В С А С В С , x, x А В С x A и х В или х С х А или х С и х В или х С х А С и х В С х А С В С А В С А С В С док-ся аналогично, все стрелки можно обернуть. 19 Отношения строгого порядка, определения, примеры.

Говорят, что на мн-ве М задано отношение строгого порядка Т, если есть бинарное отношение, подчиненное следующим трем усл-виям 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. Отн-е lt для чисел есть отн-е строг порядка. Так, про любое действит число a нельзя сказать, что a lt a, для любых 2х действит чисел a,b либо a lt b, либо b lt a, и значит, они не могут иметь место одновременно.

А для любых 3х чисел если a lt b и b lt c, то a lt c. Пример 2. Отн-е между людьми один старше др также явл отн-ем строгого порядка. 4 Операция вычитания мн-в, отсутствие коммутативности и ассоциативности. Разностью 2х мн-в А и В называется совокупность тех эл-тов мн-ва А, кот. не содер-ся в мн-ве В, т.е. С А В . В не может быть подмн-вом мн-ва

А. Обратим внимание на то, что операция вычитания некоммутативная и неассоциативная, подобно операции вычитания чисел в арифметике. Если отсутствие коммутативности практически очевидно и , то отсутствие ассоциативности нуждается в док-ве. Покажем, что А В С sup1 А В С . Мн-во, стоящее в лев части, состоит из эл-тов мн-ва А, не являющихся при этом эл-тами ни мн-ва В, ни мн-ва

С, т.е. совпадает со мн-вом А В С . Мн-во, стоящее в прав части, состоит из эл-тов мн-ва А, не являющихся при этом эл-тами мн-ва В, но при этом эл-ты, являющиеся пересечением мн-в А, В и С, входят в это мн-во, т.е. это мн-во совпадает с мн-вом А В А В С . 20 Упорядоченные мн-ва, определения, примеры. Два эл-та 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х людей

нельзя сказать, что один явл-ся предком другого. 5 Симметрическая разность, определения и св-ва. Симметрической разностью 2х мн-в А и В называется сумма разностей А В и В А , т.е. С АDВ А В В А . Заметим, что АDВ А В А В , т.к. симметрическая разность состоит из тех эл-тов мн-в А и В, которые не принадлежат А и В одновременно. Док-во

АDВ А В А В , x, x А В В А x A B или х В А х А и х В или х В и х А 1 х А и х А В, 2 х В и х А В х А В А В в обратную сторону аналогично. Операция является и коммутативной, и ассоциативной АDВ ВDА, АDВ DС АD ВDС . 6 Операция дополнения мн-в, принцип двойственности. Дополнением к мн-ву А является мн-во не А , которое дополняет мн-во

А до универсума основного мн-ва S , т.е Принцип двойственности для 2х мн-в 1 2 Док-во 2 , х, х х А В х А и В одновременно х А или х В х или х х Док-во 1 аналогично. Принцип двойств-ти состоит в том, что из люб рав-ва, состоящего из с-м подмн-в осн мн-ва С, может быть получено двойственное рав-во путем замены кажд рассматриваемого мн-ва его дополнением, объединений мн-в их пересечениями, а пересечений объединениями.

21 Деревья, лексикографический порядок, определения, примеры. Имеем некот алфавит. Заметим, что его мощность должна быть не меньше, чем макс число ветвлений в некот вершине дерева. Не ограничивая области, возьмем латин алфавит. Дерево в мате-ке строится сверху вниз. Пусть корень начальная вершина дерева назыв a. Тогда в 1ом ярусе самая лев вер-на есть аа, след ab, затем ac и т.д во 2ом ярусе вер-ны, выход из вер-

ны aa, имеют названия aaa, aab, aac и т.д вер-ны, выход из вер-ны ab, имеют названия aba, аbb, аbc и т.д. Таким образом, вер-на, находящаяся в n-м ярусе, имеет названия длины n. Если из вер-ны не выходит ни одной ветви, то она называется концевой. Пример. В дереве естественным образом устанавливается отн-ние предшествования одна вер-на предшествует др, если ее имя явл префиксом имени 2ой вер-ны. Так, вершина aa предшествует вер-не aabab.

В этом порядке сравнимые вер-ны на 1ой ветви та, которая находится выше, предшеств той, кот находится ниже. Такой порядок графич иллюстрирует соотн-ние между людьми быть предком вер-ны, располож выше, изображают предка, а вер-ны, располож ниже потомков. Если рассматривать дерево на рис как генеал-кое, то аа есть прадед aabab. Разумеется, в этом порядке вер-ны дерева не представляют собой упоряд мн-ва, а лишь частич упоряд мн-во, т.к. вер-ны aaa и ababb не сравнимы. 1 если имя 1ой является префиксом имени 2ой.

2 Если все буквы, кроме последней, в них совпадают, а последняя буква в 1ом слове расположена в алфавите раньше, чем последняя буква во 2ом слове. В дереве на рис вер-на ab предш-ет вер-не ababb, а вер-на ababaa предш-ет вер-не ababab. В этом порядке число вер-н по-прежнему не явл упоряд-ым мн-вом к примеру, вер-ны aabb и abab не явл сравнимыми, но теперь можно сравнивать вер-ны, выходящие из одной и той же вер-ны. В отн-ях между людьми это можно интерпретировать как отношение быть или предком, или старшим

братом . Иногда такой порядок называют деревянным . Если для некот целей нужно, чтобы все вер-ны дерева были упорядоченными, то порядок можно определить следующим образом. Одна вершина предшествует другой в 2х случаях 1 если имя первой явл префиксом имени 2ой 2 выделяется макс общ префикс 2х имен и далее, если след за макс общ префиксом буква имени 1ой вер-ны расположена раньше, чем такая же буква имени 2ой вершины.

Этот порядок называется лексикографическим, алфавитным или словарным. 7 Разбиение мн-ва, покрытие мн-ва, примеры в математике и информатике. Представление заданного мн-ва в виде объединения системы мн-в, не имеющих попарно общих точек, называется разбиением. Таким образом, если есть мн-во А, такое что , где для люб Bi и Bj, Bi Bj , то с-ма Bi есть разбиение мн-ва А .

Очевидно, что мн-ва могут обладать различными разбиениями. Пример. Мн-во цел чисел можно представить в виде об-ния мн-ва чет чисел и мн-ва нечет чисел с одной стороны, а также в виде об-ния мн-ва чисел, кратных трем, мн-ва чисел, имеющих при дел на 3 в остатке 1, и мн-ва чисел, имеющих при делении на 3 в остатке 2. Любое мн-во подмн-в мн-ва А, объединение которых есть мн-во

А, называется покрытием мн-ва А. Сл-но, если есть мн-во А, такое что , то система Bi есть покрытие мн-ва А . Таким образом, разбиение есть частный случай покрытия, т.е. это покрытие, в котором мн-ва Вi не пересекаются. Пример. Мн-во натур чисел можно представить в виде об-ния мн-ва нечет чисел, мн-ва чисел, не дел на 3, и мн-ва чисел кратных 6. Очевидно, что эти подмн-ва пересекаются, на пример,

число 7 принадлежит и мн-ву нечетных чисел, и мн-ву чисел, не делящихся на 3. 8 Определение алфавита, буквы, слова, равенства слов, операции приписывания, св-ва операции приписывания. Набор знаков данного языка называется его алфавитом, а сами знаки буквами этого языка. Из букв можно составить слова. Слово определяется следующим образом - любая буква есть слово - если А слово и В слово, то АВ также слово - пустое слово слово, не содержащее букв есть слово.

Таким образом слова строятся с помощью операции приписывания, т.е. к слову А приписывается справа слово В. Операцию приписывания также называют конкатенацией. Если два слова А и В построены из одинаковых букв, расположенных в одинаковом порядке, то в дальнейшем мы будем говорить, что слова А и В графически равны, т.е. А В. Число букв в слове А будем называть его длиной, т.е.

А . Очевидно, что если два слова графически равны, то они имеют одинаковую длину. Пустое слово имеет длину, равную 0. При приписывании слова В к слову А получаем слово с длиной А В . Основные св-ва операции приписывания 1 Операция приписывания некоммутативная АВ sup1 ВА 2 Ассоциативность АВ С А ВС 3 Если слова А, В и С таковы, что

АС ВС, то А В 4 Если слова А, В и С таковы, что СА СВ, то А В Последние два св-ва называют также правилами сокращения. 22 Св-ва отображения, ф-ции графики. Ф-ции как част случай бинар отношений. Функцией называется функциональное соответствие. Если функция устанавливает соответствие между множествами А и В, то говорят, что функция имеет тип А В обозначается

А В . Каждому элементу а из области определения функция ставит в соответствие элемент b из области значений. Это обозначается а b. Элемент а аргумент функции, элемент b значение функции на а. Отображением. А в называется всюду определ нная функция. А В. Отображением А на В называется всюду определ нное и при этом сюръективное функциональное соответствие А В. Отображением типа А А часто называют преобразованием множества

А. Функция типа А А, являющаяся отображением А на А, называется перестановкой на А. Функции и g равны, если - Их области определения одно и то же множество А - Для любого а А а g а . Функция типа А1 А2 Аn B назывется n-местной. В этом случае принято считать, что функция имеет n аргументов а1 аn b, где а1 А1, аn An, b B. Если соответствие, обратное к функции

А В, является функциональным, то оно называется функцией, обратной к обозначается -1 . Для функции А В обратная функция существует тогда и только тогда, когда является взаимно однозначным соответствием между своими областями определения и значений. Способы задания функции - Графиком - Таблицей - Формулой, описывающей функцию, как суперпозициюдругих исходных функций Рекурсивной вычислительной процедурой.

Например, функция х 1 2 3 . х 1 х х! Описывается рекурсивной вычислительной процедурой, задаваемой следующими правилами 0 1 х 1 х х 1 Если элемент а принадлежит множеству М, то соответствующий ему элемент d a называется его образом. Каждый элемент а может иметь единственный образ, при этом для b может существовать не один элемент из М, образом котрого он является. Совокупност всех тех эл-тов а из

М, образом которых является данный элемент b из N, называется прообразом или полным прообразом элемента b и обозначается -1 b . 9 Определение префикса и его св-ва. Сл В называется началом сл А или его префиксом , если сущ-ет слово С, такое что А ВС Св-ва префикса 1 Любое слово есть префикс самого себя. Это очевидно, т.к. сущ-ет пустое слово, и любое пустое слово есть конкатенация самого себя и пустого

слова. 2 Пустое слово есть префикс любого слова. док-во в 1ом св-ве 3 Если А префикс В, а В префикс С, то А префикс С св-во транзитивности префиксов . Док-во если А префикс В, то сущ-ет слово D, такое что B AD, т.к. В префикс С, то сущ-ет такое слово Е, что С ВЕ, тогда С АDE и А префикс С. 4 Если А и В суть префикс слова

С, то А есть префикс В или В есть префикс А закон двух начал . Имеем С АD и С ВЕ. Далее, если А длиннее, чем В, то В есть префикс А, иначе А есть префикс В. 11 Определение суффикса и его св-ва Сл С называется концом сл А или его суффиксом , если сущ-ет слово В, такое что А ВС Св-ва суффикса 20. Любое слово есть суффикс самого себя.

Это очевидно, т.к. сущ-ет пустое слово, и любое пустое слово есть конкатенация пустого слова и самого себя. 21. Пустое слово есть суффикс любого слова. док-во в 1ом св-ве 22. Если А суффикс В, а В суффикс С, то А суффикс С св-во транзитивности суффиксов . Док-во если А суффикс В, то сущ-ет слово D, такое что B DА, т.к. В суффикс С, то сущ-ет такое слово Е, что

С ЕВ, тогда С ЕDА и А суффикс С. 23. Если А и В суть суффикс слова С, то А есть суффикс В или В есть суффикс А закон двух концов . Имеем С DА и С ЕВ. Далее, если А длиннее, чем В, то В есть суффикс А, иначе А есть суффикс В. 24 Декарт пр-ние n мн-в, n-арные отн-ния, классич операции над отношениями. Кортеж или n-ка посл-ть эл-тов, т.е. мн-во, в котором каждый эл-т занимает определенное

место. Обозначается кортеж как a1,a2, ,an , а a1,a2, ,an суть его эл-ты, которые называются компонентами кортежа, их число длина кортежа. Декар пр-ние A1 A2 An мн-в A1,A2, ,An представляет собой мн-во всех упоряд n-к эл-тов a1,a2, ,an , где a1 A1, a2 A2, , an An. В этом случае а1 назыв 1ой корд-той и т.д. В частности, декартово пр-ние R R R, где R мн-во действительных чисел, определяет трехмерное геометрич

пр-во, где эл-ты a x,y,z явл точками трехмер евклидового пр-ва. N-арным или n-местным отношением называется любое подмн-во Т декартова пр-ния n-й степени T Mn. Точками отношения T являются посл-ти вида a1,a2, ,an , где ai M. Для n-арных отношений операции вводятся аналогично бинарным отношениям. Таким образом, если T и S суть n-местные отношения в мн-ве

M, то n-местными отношениями в М будут также следующие подмн-ва T S, T S, M T, T S, TDS. 12 Определение собственного суффикса и его св-ва. А собственный суффикс В, если А суффикс В и А В Св-ва собственного суффикса 1 Если А и В суть собственные суффиксы слова С, то А есть собственный суффикс В или В есть собственный суффикс А. 2 Слово А тогда и только тогда есть суффикс

ВС, когда имеет место одно из двух А собственный суффикс слова С или А имеет вид DС, где D суффикс С. 25 Реляционные операции над отн-ми операции выбора, проекции и соединения. В реляционных операциях рассматриваются только одноэлементные отношения. Пусть Т отношение над множеством А со схемой отношений М M1,M2, Mn . А Выбор по атрибуту Мi со значением а осуществляется следующим образом те стоки, в которых

в i-ом столбце нет элемента а, выч ркивается. Свойства операции выбора 1. Операция выбора является унарной операцией 2. Она не меняет схемы отношений и следовательно его формата 3. При применении операции выбора арность не увеличивается 4. 963 Мi b 963 Мi a T 963 Мi a 963 Мi b T i j i sup1 j Операция обобщ нного выбора 963 m x T осуществляется выбором тех строк, у которых значение атрибута

Мi линий в выбранном подмножестве х, при этом остальные строки зач ркиваются. Б операция проекции p х R T где R схема отношения осуществляется выбором столбцов, принадлежащих х, при этом остальные столбцы выч ркиваются и при этом из одинаковых строк оста тся лишь одна. Таким образом формат отношения при операции проекции уменьшается, а не увеличивается. В Операция соединения бинарная операция, т.е. она применяется к 2 отношениям и в результате получаем

новое отношение. Оно обозначается T 9658 9668 S. Пусть схема отношения Т равна R1, а схема отношения S равна R2, тогда схема отношения T 9658 9668 S есть R R1UR2. Соед-ем отн-ний T и S будет мн-во таких картежей q, что для q существует два картежа qT и qS, что если вычеркнем из картежа q атрибуты, не входящие в Т, то получим картеж qT, а если вычеркнем из картежа q атрибуты.

Не входящие в S, то получим картеж qS. 13 Определение подслова, собственного подслова и его св-ва, число подслов. Слово С есть подслово слова А, если сущ-ют такие слова В и D, что А имеет вид ВСD. Соответственно слово С есть собственное подслово слова А, если сущ-ют такие слова В и D, что А имеет вид ВСD и хотя бы одно В или D не пусто. 14 Определение кода. Кодом называется такое мн-во слов, которое само может играть

роль алфавита. Более строгое определение кода следующее Мн-во слов b1,b2, ,bn в алфавите П a1,a2, ,am называется кодом, если не сущ-ет такой перестановки i1,i2, ,in символов 1,2, ,n , что b1b2 bn bi1bi2 bin. Таким образом, какую бы перестановку символов 1,2, n не взяли, b1b2 bn sup1 bi1bi2 bin. 15 Декартово пр-ние мн-в и его св-ва. Геометр интерпретация декарт пр-ний. Декартовым или прямым пр-нием мн-в

А и В называют мн-во А В всех упорядоченных пар эл-тов a,b , где a A, b B, т.е. А В С . Эл-ты a и b называют при этом компонентами или координатами пары a,b . Соответственно, a называют 1ой координатой пары, а b 2ой корд-той пары. Если одно из мн-в А или В пусто, то произв-нием А В будет пустое мн-во. Известным примером явл-ся мн-во декартовых координат в прямоугольной сис-ме корд-

т. Св-ва декартова пр-ния 1 декартово пр-ние не коммутативно А В sup1 В А 2 декартово пр-ние не ассоциативно А В С sup1 А В С . Для док-ва этих фактов достаточно привести примеры, когда коммутативность и ассоциативность не выполняются Пример 1. Пусть A 1 , В 2,3 , тогда А В 1,2 , 1,3 , B A 2,1 , 3,1 . Обратим внимание, что в случае, когда

А В, переместительный закон имеет место. Пример 2. Пусть A 1 , B 2 , C 3 , тогда A B C 1,2 ,3 , т.е. декартово пр-ние состоит из одной пары, 1ая коорд-та которой есть пара 1,2 , а 2ая эл-т 3. В то же время A B C 1, 2,3 , т.е. декартово пр-ние состоит из одной пары, 1ой коорд-той которой явл число 1, а 2ой пара 2,3

Декартовым произведением явл плоскость. Например, А 0,1 и В 1,2 , тогда А В Если А В, то А В А2. Если одно из множеств является , то А В 28 Метод математической индукции. Математическая индукция Неполная индукция. Например n, 2 8804 n 8804 15, что n явл простым или пр-нием не более 3х простых чисел док-во 2 прост, 3 прост, 4 2 2, 5 прост, 6 2 3, 7 прост,

8 2 2 2, 9 3 3 3 и т.д. Полная индукция 6. база индукции Ф 1 проверяем истинность утверждения при n 1 7. индукционное предположение Ф к предполагаем, что утверждение истина при n k 8. индукционный шаг Ф к Ф к 1 . Докажем, что из истинности утверждения при n k истинность при n k 1 4. индукционный вывод 30 Понятие графа, примеры. Графом называется совокупность 2х мн-в

V p1,p2,p3,p4,p5,p6 мн-во вершин и A p1,p2 p1,p3 p1,p4 p2,p3 p2,p5 p3,p6 p4,p5 p4,p6 p5,p6 мн-во ребер, и обозначается G V A Если пара вершин xi,xj не упорядоченная, то она называется ребром, если упорядоченная, то она называется дугой. 16 Понятие отношений, св-ва бинарных отношений рефлексивность, симметричность, интисимметричность, транзитивность. Отношение бинарное отношение любое подмножество вида А А. Пусть A R, в этом случае отношение lt означает множество пар декартовой плоскости, расположенное

левее биссектрисы 1 и 3 координатных углов. Свойства 1. R рефлексивно, если а а а R Тогда в матрице отношения R на главной диагонали стоят только единицы i cii 1 2. R не рефлексивно, если а а а R На главной диагонали матрицы есть хотя бы один ноль. 3. R антирефлексивно, если а а а R Тогда на главной диагонали матрицы стоят только нули i cii 0. 4.

R симметрично, если а,b a b R b a R. Тогда в матрице отношения i,j cij сji 1. Значит, матрица симметрична относительно главной диагонали. 5. R не симметрично, если a,b a b R и b a R 6. R антисимметрично, если a sup1 b. a b R b a R, т.е. ни для каких различных a и b a sup1 b не выполняется одновременно a b R и b a R. Если же a b R и b a R, то a b. Тогда в соответствующей матрице отношения ни для каких i,j

i sup1 j не выполняется cij cji 1. Таким образом, отсутствуют единицы, симметричные относительно главной диагонали. 7. R транзитивно, если того, что a,b,c a,b R и b,c R следует, что a,c R. В матрице такого отношения должно выполняться след условие если cij 1 и cjk 1 i, j, k Говорят, что в М задано бинарное отношение Т, если М М есть декартово произведение и в М М выделено произвольное подмн-во

Т. Таким образом, произвольное подмн-во Т М М есть бинарное отношение. Мы будем говорить, что эл-т a находится в отношении Т к эл-ту b в том и только в том случае, когда пара а,b принадлежит мн-ву Т. Для этого возможны два равносильных способа обозначения аТb или а,b Т. 32 Ориентированный граф, примеры. Если граф состоит только из дуг в нем не встречается ребер , то

он называется ориентированным. 34 Числовые характеристики графа хроматическое число. Раскраска графов. Пусть G неориентированный граф, имеющий n ребер, m вершин и r компонент связности, тогда C G n-m r Минимальное число используемых красок называется хроматическим числом графа. Вершины, исходящие из одной вершины и соединенные между собой не могут быть одного цвета. 35 Алгоритм построения эйлерова цикла. Цикл называется эйлеровым, если ему принадлежат все ребра и

ни по одному ребру нельзя пройти дважды выбрать произвол вел-ну а выбрать произвольно некоторое ребро, инцидентное а, и присвоить ему 1 каждое пройденное ребро вычеркивать и присваивать ему номер, на единицу больший номера предыдущего ребра находясь в некоторой вер-не х, не выбирать ребра, инцидентного а, если есть возможность другого выбора находясь в вер-не х, не выбирать мостов После того, как все ребра занумерованы m 1,2, ,n есть путь, образующий эйлеров цикл.

33 Пути и циклы в графах. Компоненты связности, мосты. Путем графа из вершины xi в вершину xj называется такая последовательность ребер, у которой 1ая вершина 1го ребра xi, а 2ая вершина последнего ребра xj и при этом 2ая вершина предыдущего ребра совпадает с 1ой вершиной следующего ребра и никакое ребро не встречается дважды. Путь называется циклом, если 1ая вершина 1го ребра совпадает со 2ой вершиной последнего ребра.

Путь цикл называется простым, если ни одна вершина не будет встречаться более одного раза на первом месте. Граф G называется связным, если 2х его вершин путь, их связывающий. Любой несвязный граф явл совокупностью связных графов, кот образуют его, каждый из которых называется компонентой связности. Теорема 1. Для того, чтобы граф G представлял собой простой цикл необходимо и достаточно, чтобы степень каждой его вершины равнялась

двум. Ребро a называется мостом графа G, если при его удалении число компонент связности увеличивается. Теорема 2. Ребро графа G называется мостом тогда и только тогда, когда оно не принадлежит ни одному из циклов. 36 Определение кода, моноида, группы, полугруппы. Множество объектов произвольной природы с введ нной на них бинарной операцией называется группой G, если оно удовлетворяет следующим свойствам 1 замкнутость относительно введ нной бинарной операции

a b a G b G a b G 2 ассоциативность операции a b a G b G c G a b c a b c 3 существует нейтральный элемент е e G a e a 4 для любого элемента группы существует обратный элемент a b a G b G a b е Пример - lt Z gt - группа - lt Z - gt - не является группой, т.к. не выполняется условие ассоциативности lt N gt - не является группой Множество объектов произвольной природы с введ нной н

м бинарной операцией называетс моноидом, если оно удовлетворяет условиям 1 замкнутость относительно введ нной бинарной операции a b a М b М a b М 2 ассоциативность операции a b a М b М c М a b c a b c 3 существует нейтральный элемент е e М a e a 4 Ai Aj Ai j i j lt 5 A0 A1 A2 A3 A4 A0 A0 A1 A2 A3 A4 A1 A1 A2 A3 A4 A0 A2 A2 A3 A4 A0 A1 A3

A3 A4 A0 A1 A2 A4 A4 A0 A1 A2 A3 Ai j 5 i j sup3 5 Группа по модулю 5 5 Ai Aj Ai j i j lt 5 Ai j 5 i j sup3 5 Мн-во объектов произв природы П с введ нной на них бинар оп-цией назыв подгруппой , если оно удовл-ет след св-вам 1 замкнутость относительно введ нной бинарной операции a b a П b П a b П 2 ассоциативность операции a b a П b П c

П a b c a b c Подмн-во G1 группы G называется подгруппой группы G, если оно само является группой. Мн-во М1 моноида М называется моноидом моноида М, если оно само является моноидом Понятиие кода Пусть дан конечный алфавит П a1, am Множество слов в алфавите П b1, ,bn называется кодом, если не существует такой перестановки символов 1,2 n , что b1, ,bn bi1,

bin, где 1 2 . n Sn i1 i2 .in Пример 1 a, ab код 2 a, aa, ab 3 ab, bab, aab aab sup1 aba a.aa.ab aa.a.ab ab.aab.bab.ab.ab aabaaaabaab Пример не кода b1 abaa.ba.abaa b2 ba.abaa.ba.abaa.ba b3 abaa b1b2b3 b3b2b1 abaa.ba.abaa.ba.abaa.ba.abaa.ba.abaa b1b2b3 b3b2b1 10 Определение собственного префикса и его св-ва. А собственный префикс В, если А префикс В и А В Св-ва собственного префикса

Если А и В суть собственные префиксы слова С, то А есть собственный префикс В или В есть собственный префикс А. Слово А тогда и только тогда есть префикс ВС, когда имеет место одно из двух А собственный префикс слова В или А имеет вид ВD, где D префикс С. 23 Свойства функций инъективность, сюрьективность, биективность. Функция одно из основных понятий в математике. Пусть

M и N два произвольных множества. Говорят, что на М определена функция , принимающая зхначения из N, если каждому элементу х М поставлен в соответстие по определ нному закону один и только один элемент у N, т.е. у х