1610906301-73dade1bb16d31c957842031de4c898c (Краткий конспект к экзамену)

Дискретная математика и Теория алгоритмовТема 1Теория множеств и математическая индукцияОпределение 1.1Семейство множеств R называется разбиением множества А если• ∀ x,y ⊊ R x≠y →x⋂y=∅• ∀ x⊊ R x≠∅• ∪R=AУпорядоченные пары (а,b)=(c,d) =>(a=c) ^ (b=d)Упорядоченные n-ки (a1,a2..an) (кортежи длины n)n-мерное отношение R⊊ A1 x A2 x A3 x A4Определение 1.2 (Метод математической индукции)Данный метод имеет две эквивалентных формулировки:1)Пусть утверждение P(x) верно при P(k), k∈N. Тогда если P(n) => P(n+1) то P верно для всех n.2)Пусть утверждение P(x) верно при P(k), k∈N.

Тогда если P(1)^(P2)^...^P(n-1) => P(n) то P вернодля всех n.Тема 2:ОтношенияКомпозиции отношений R1 o R2={(x,z)|∃ y: (x R1 y) ^(y R2 z)}рефлекcивность (x R x)симметричность x R y => y R xтранзитивность x R y ^ y R z => x R zантисимметричность (x R y) ^(y R x) => x = yотношенийОтношения эквивалентности: R называется отношением эквивалентности если оно рефлективносимметрично и транзитивно.Класс эквивалентности [x]R ={y|x R y}Если R Эквивалентность на А то {[x]R|x∈A} называется Фактор-множеством А по R(обозначается A/R)Теорема 1 (О разбиении множества)Фактор-множество А является его разбиением.Док-во:1)R рефлекcивно, следовательно любое [x]R ≠∅2)Произвольный x принадлежит своему же классу эквивалентности следовательно каждый x изА принадлежит множеству классов эквивалентности.3)Пусть элемент z связан отношением R с x и y.

Тогда возьмем произвольный t из [x}R. Заметимчто по определению класса эквивалентности xRt, но по свойству симметричности tRx. Далее потранзитивности xRz след tRz. Но по симметричности zRy следовательно по транзитивности tRyследовательно t лежит в [y]R. По аналогии для t из [y] получаем что классы эквивалентностисовпадают.Определение 2.1Отношение R⊊A x A называется частичным порядком, если R рефлексивно, антисимметрично итранзитивно.Определение 2.2Если R — частичный порядок ∀ x,y (x,y) ∈ R или (y,x)∈ R, то R — линейный порядокОпределение 2.3 Обратное отображение: Если R⊊AxB то R-1 ={(y,x)|(x,y)∈ R}Определение 2.4Отношение называется функциональным если (x R y1) ^ (x R y2) => y1=y2dom(F) — Область определения Frange/im(F) — область значений FЕсли F: A→B и range(F)=B то F:сюръекцияЕсли F:An → B, то F — n-арное отображение (обозначается F(a...an))Если ∀ x,y ∈A F(x)=F(y) => x=y то F инъекцияЕсли F — инъекция то F^-1 тоже инъекцияТема 3:Алфавиты и языкиОпределение 3.1Слово над алфавитом А — любая конечная последовательность символов А.А* - множество всех слов над А.Λ — Пустое слово|a| - длина слова аОпределение 3.2Язык над Алфавитом А* - Любое подмн-во А*Λ∈Пустому языку.Определение 3.3:Если a,b ∈ A* - то ab — конкатенация a и b.

(иногда обозначают a*b, a o b)Свойства:Конкатенация некоммутативна и ассоциативна.Λ*a=a*Λ=aПусть L0 и L1 — языки. Тогда L0*L1={w0*w1|w0∈ L0, w1∈ L1}Определение 3.4:Пусть b=yax , тогда y,a,x — подслова bПричем y — начальное подслово bслово в n степени b^n=b*b*b...b (n раз)Определение 3.5:Если L — язык, то L* - звезда Клини.L* ={w1..wn|n ∈N, w1..wn∈L} — всевозможные конечные конкатенации слов из языка L.Свойства звезды Клини (Доказывались на семинарах, в принципе можно будет потом записать)L* o L*=L*(L*)*=L*L0⊊L1 => L0*⊊L1*L*=∪{L^n|n=0,1..}, где L^n ={li|li∈L, |li|=n}Над языками можно проводить те же операции, что и над множествами:Пуcть L0={ab} а L1{ac, bc}тогда L0∪L1={ab,ac,bc}L0⋂L1=∅L0\L1={ab}Для выполнения операции дополнения должен быть определен Алфавит A над которымопределен язык L. L∈A*, !L=A*\LТема 4:Введение в теорию графов:Основные определения. Степень вершины.

Лемма о рукопожатияхОпределение 4.1:Граф: абстрактный математический объект, представляющий собой множество вершин и«ребер», их соединяющих|V| - порядок графа V (число элементов в V)Формально: G=(V,E), где V -множество вершин, а E — множество пар принадлежащих V.Если пара x,y лежит в Е то значит что x и y «соединены»Определение 4.2Неориентированный граф: G=(V,E) E={{x,y}|x,y ∈ V}e∈E является петлей если x=y.Ориентированный граф G=(V,E) E={(x,y)|x,y ∈ V}Если в графе p вершин и q ребер, то это (p,q) графОпределение 4.3:Вершины u и y называются смежными Если {u,v}∈E (соединены ребром).Дуги графа называются смежными если они имеют общую вершину и различны.Определение 4.4:Вершина u и ребро e называются инцидентными, если u лежит на одном из концов e.Определение 4.5:Степень вершины графа: число инцидентных ему ребер.Ориентированный граф — G=(V,E) E⊊VxVd-(V) — степень исхода вершины (число дуг, исходящих из вершины)d+(V) — степень захода вершины (число дуг входящих в вершину)Теорема 4.1 (Лемма о рукопожатиях):Для неориентированного графа:Сумма всех степеней вершин конечного графа равнаудвоенному числу реберДля ориентированного графа:сумма входящих и исходящих степеней ориентированного графаравна удвоенному числу реберДоказательство: Заметим что если добавить ребро между двумя вершинами степень обеихувеличится, таким образом одно ребро добавляет 2 в сумму степеней (в том числе если путь петля).Аналогично для ориент.

Графа: ребро увеличивает степень исхода одной и степень захода другойвершины, вновь добавляя 2 в сумму степеней.Определение 4.6:G0(V0,E0) называется подграфом графа G1(V1,E1) если V0⊊V1 и E0⊊E1.Определение 4.7:Пусть U — множество, U⊊V. и (V,E) — граф. Граф называется Порожденным множеством Uесли он имеет вид (U, E`), где E` - множество всех ребер, концы которых лежат в U.

(Граф такжеможет быть порожден множеством ребер W и иметь вид (V`, W), где V `- множества,инцидентные ребрам из W.Маршруты, циклы, деревья.Определение 4.8Пусть G(V,E) — граф. Последовательностьv0e0, v1e1...e(n-1)vn, где v0,v1,..vn∈V, e0,e1..e(n-1)∈E называется маршрутом если для всехi=0,1...n-1 ei — ребро соединяющее vi и vi+1Виды маршрутов:1. Замкнутый (если v0=vn)2. Цепь, если все его ребра (кроме, может быть, e0 и ek-1) попарно различны1. Простая цепь: цепь, у которой все вершины (кроме может быть первой ипоследней) попарно различны3. Цикл — цепь, у которой первая и последняя вершины совпадают1. Простой цикл: цикл, у которого все вершины кроме первой и последнейпопарно различны. (то есть никакие вершины не посещаются дважды)Определение 4.9Вершина А достижима из вершины B, если существует маршрут с началом в А и концом в BОпределение 4.10Неориентированный граф называется связным, если любая его вершина достижима из любойдругой.(Ориентированный граф называется сильносвязным, если для любых вершин а и b адостижима из b и b достижима из а и слабосвязным, если граф, полученный из исходногоудалением направлений стрелок связен)Определение 4.11Граф называется полным, или полносвязным если между любыми двумя его вершинами естьребро.Определение 4.12Дополнение графа G - граф, имеющий те же вершины что и G, но имеющий только те ребра,которые G не имеет (Дополняет граф G до полного графа) обозначается !GТеорема 4.2 (о связности)Пусть G — конечный граф, тогда G связен, либо его дополнение связно.Доказательство:Если G связен, то G связен.Если G несвязен, то существуют вершины a и b, между которыми нет маршрута.

Тогда в !G естьребро между a и b.Теперь докажем что в !G произвольная вершина x достижима из а (из этого следует что междулюбыми x и y существует маршрут). Пусть есть вершина x , тогда в G нет либо пути x→a либоx→b (так как если оба они есть, то между a и b есть путь) Тогда если в G нет пути из x→a то онесть в !G, что нам и нужно. Иначе если нет пути из x →b то он есть в !G как и путь из a → b,следовательно вновь существует путь из x в а, чтд.Определение 4.13Компонентой связности графа называется подграф, порожденный классом эквивалентности~:={x,y|x достижима из y}Определение 4.14Граф G называется деревом, если он не пуст, связен и не содержит нетривиальных Циклов(циклов, в которых есть хотя бы одно ребро).Теорема 4.3 (о вершинах и ребрах дерева):Связный конечный граф является деревом <=> B=P+1, Где B — число вершин графа, а P —число ребер.Доказательство:=>Докажем методом математической индукции.Для B=1 условие верноПусть условие верно для B=nТогда докажем для B=n+1Удалим из G висячую вершину и ребро, идущее к ней.

Получим G` (он все еще связен, так-какмы не трогали иные пути и удалили всего лишь одно ребро, по той же причине в графе нетциклов). Следовательно G` - дерево с n вершин и по предположению индукции B`=P`+1.Но B=B`+1 и P=P`+1Тогда B=B`+1=(P`+1)+1=P+1Чтд.<=Пусть G — связный граф и B=P+1, но в G есть нетривиальный цикл.В этом цикле число вершин ≤ числа ребер (равенство достигается в том случае если всевершины различны)Построим последовательность подграфов графа G: G0,G1…Где G0: Все вершины и все ребра циклаСтроим следующим образом:Берем произвольную вершину а∈G: a∉Gn и существует ребро хотя бы из одной вершины Gn в a.Тогда V(n+1):= все вершины из Gn+a и E(n+1) — все ребра Gn+ все ребра ведущие из Gn в а.Было Bn≤Pn. Так как мы добавляем ровно одну вершину и минимум одно ребро B(n+1)≤P(n+1).Так как граф конечен то для некоторого m мы не сможем построить G(m+1) (не сможем найтиточку а), но так как граф связен то до каждой вершины существует путь.

Следовательно если мыне можем взять а, то у нас кончились вершины. Значит V(m)=V исходного графа G.Но тогда B=Bm≤Pm≤PНо по условию B>P. Получаем противоречиеЗначит в графе нет нетривиальных циклов => граф — дерево.Двудольные графыОпределение 4.15Граф G называется двудольным если мн-во его вершин можно представить в виде A∪B ГдеА⋂B=∅ и E={{a,b}|a∈A, b∈B}Теорема 4.4 (Характеризация Кёнига двудольных графов)Следующие условия эквивалентны:1)G — двудольный граф2)G — не содержит замкнутых маршрутов нечетной длины.3)G — не содержит простых циклов нечетной длины.2 => 3Очевидно ( любой цикл — замкнутый маршрут)3=>2Докажем что любой замкнутый маршрут нечетной длины содержит простой цикл нечетнойдлины.

Тогда из отсутствия простых циклов будет следовать отсутствие замкнутых маршрутов(так как если бы таковой существовал, то он бы содержал простой цикл нечетной длины).Докажем индукцией по длине маршрута:База: пусть маршрут замкнут и имеет длину 3 (проходит через три ребра), тогда он, очевидноявляется простым циклом нечетной длины.Переход: пусть для маршрута длины 2k-1 утверждение верно. Докажем для (v0,v1...v2k+1) —маршрута длины 2k+1. Заметим что если все вершины в это маршруте, кроме последней ипервой различны то он является простым циклом. Иначе найдутся две совпавшие вершиныvi=vj, 0≤i,j≤2k. Без ограничения общности i<j.

Тогда имеем что два маршрута vi..vj иvj...v(2k+1)=v0 → vi оба являются замкнутыми, имеют длину <2k и при этом один из нихнечетен, поскольку в сумме их длины равны длине исходного маршрута. Таким образом поиндукционному предположению в замкнутом маршруте содержится простой цикл.Таким образом получаем описанное противоречие.1=>2Пусть G двудольный: его вершины можно разделить на два множества A и B.Пусть G содержит замкнутый маршрут нечетной длины: тогда он идет так:А→ B → А → BСледовательно через четное число ребер мы попадаем в А, а через нечетное в B. Но так-какмаршрут замкнутый, то мы должны попасть в вершину Из А.

Значит конечная вершина лежит ив B и в А, что по определению невозможно. Противоречие2=>1Пусть граф связен. Зафиксируем в нем вершину а. Тогда А:={x|существует маршрут четнойдлины из x в а}, B:={x|существует маршрут нечетной длины из x в а}Докажем что множества не пересекаются:Пусть существует x: x∈a ^ x∈B.