Шпарнгалка по "Дискретной математике"

1.Мн-ва. Обычно под понятием мн-ва подразумевают совокупность, набор объектов объединенных по какому-либо признаку.  Ex: А= . Условие того, что a A,  т.е. элемент а принадлежит мн-ву А. Идея построения теории мн-в возникла в 19веке ее основателями считаются Больцано и Кантор. Их идея заключалась в том, чтобы вся математика строилась на теории мн-в. Парадокс Рассела: будем говорить, что мн-во является хорошим если оно не содержит самого себя в качестве элементов, и нехорошим если содержит самого себя. Рассел предложил рассмотреть мн-во всех хороших множеств. М= .

1)Пусть  М – хорошее мн-во  а) ММ(по определению М), б) М М (по определению «хорошее») Получили противоречие это условие не верно.

2) Пусть  М – не хорошее мн-во  а) М М (по определению М), б) М М (по определению «хорошее») Получили противоречие это условие не верно.

Для того чтобы избежать возникновение парадоксов были созданы наборы аксиом при выполнении которых теория множеств становится не противоречивой.

Операции  над множествами. Будем говорить что мн-во (А В) если (а А=>а В). Будем говорить что А=В(по определению)=> А В В А. В качестве операции над множеством будем рассматривать: А В; А В; А\В;

Справедливы следующие свойства: 1)А В А; 2)А В А; 3) А В А В; 4) (А В)∩С= (А∩С) ( В∩С); 5) (А∩В) С= (А С)∩( В С). Пусть А некоторое конечное множество т.е множество содержащее конечное число элементов тогда =булеан= . Не трудно показать, что А конечное множество содержащее n-элементов, то его булеан будет содержать элементов аналогично определяется булеан бесконечного множества. Количество элементов множества будем обозначать

|А|, | |= если А- конечно.  

4 Отображение, образ  и прообраз. Биекция.  Рассм произ А и В и нек отнош R принA*B будем говорить что R явл отображением из А в В если указ-е правило обе

спечив  единственость каждого y для кажд x.отобрах обознач f:А->В. f(x)-будем наз образом отображ, а элемент x- прообразом.f(А)=В.Св-ва отображ:1-

Отображ наз биективным если оно сюрьективно и инъективно.Отображ сюрьект: отображ инъект:

Обратным  отображ для отображ f будм наз отображ f^-1:А->В дейст по след правилу f^-1(y)=x след-но f(x)=y. Связь м\у св-ми отображ и обрат отображ:

2.Декартово  произведение мн-в.  Пусть есть два множества произвольной природы А и В. Декартовым произведением множеств А В будем называть множество всех упорядоченных пар вида (а, b) где а А, в В .  Отношение эквивалентности: будем говорить, что в мн-ве А задано отношение R если задано некоторое подмножество из декартового квадрата R A A. 1. Отношение равенства: Пусть А=R  {0,5=0,5; 0,5 0,6} задать отношение равенства на множ-ве R это эквивалентно тому чтобы выписать пары всех одинаковых чисел. 3. А={1,2,3} R={(1,2), (1,3), (2,3)}-оно только транзитивно R=”отношение <” В случае если отношение R удовлетворяет условиям рефлексивности, симметричности, транзитивности оно наз-ся отношением эквивалентности. Будем говорить что элемент a находится в отношении R к элементу b если пара (a,b) R. Заметим что важную роль играет порядок элементов. Будем говорить, что отношение R на мн-ве А явл-ся отношением порядка если оно обладает следующими 3 св-ми: 1) Рефлексивность aRa; 2) Антисимметричность   aRb bRa a=b; 3) Транзитивность aRb bRс aRс. Будем говорить что задано отношение эквивалентности R если выполняются 3 св-ва: 1. Рефлексивность  aRa; 2. Симметричность  aRb bRa; 3. Транзитивность  aRb bRc aRc. n-местным отношением P на мн-ах называется любое подмножество прямого произведения Другими словами, элементы x1,x2,..,xn (где x1 ) связаны соотношением P (sign P(x1,..,xn)) тогда и только тогда когда (x1,..,xn) P. Наиболее часто встречаются двухместные отношения (n=2). Они называются бинарными отношениями или соответствиями. Т.о. соответствием P м/у мн-ми А и В явл-ся подмножество мн-ва А*В. Если P А*В и (x,y) P, то пишут также хPy. Отношение P называется n-местным на мн-ве А. Упорядоченное мн-во –это мн-во с введенным отношением порядка. Если 2 любых элемента находятся в отношении порядка - то линейно, если не любые то частично. 

3.Разбиение  мн-в. Фактор мн-ва. Примеры. Пусть на А задано такое отношение эквивалентности, тогда оно пораждает такое разбиение мн-ва, что  а~в что и наоборот  люб разбиение мн-ва пораждает отношение эквивалентности. Замечание: будем говорить что на А задано разбиение если 1 i≠j пустое мн-во 2 Док-во: рассмотрим 2 случ.1 А  пустое, теорема очевидна. 2 если А не пустое мн-во тогда обозначим <a>={x принадлежитA|x~a} Док-ем 2 св-ва: 1 а принадлежит <a>. 2 два мн-ва либо не пересек либо совпад. <a>объед<b>непустое либо <a>=<b>.

Док-во:1 а~а=>a принадлежит <a>. 2 пусть есть <а> и <b>≠пуст мн-ву, существует x <а> и x <в> => x~а, x~b след-о а~x, b~x. выберем произ y <а>: y~а, а~x след-о y~x; x~b след-о y~b след-о y прин<b> след-о<а> <в>. Аналогич <а> <в> след-о <а>=<в>. и наоборот.

Мн-ва <а> <в> введ в теор наз классами эквивал мн-ва А. Отнош эквивал автоматич поражд на классы эквивал кот пересек либо совпад.  Совокуп всех классов эквивал-ти наз фактор мн-ва А/~. 
 
 

6 Теорема о мощности  промежуточного множества. А В С, |A| |C| |A| |B| |C|. Док-во: Пусть -есть некоторое взаимооднозначное соответствие м/у А и С. Каждому элементу С в этом соответствии отвечает некоторый элемент А. В частности те элементы А, которые отвечают элементам В, образуют определенное мн-во D А. Т.О  В связано взаимооднозначным соответствием с D. Но А В, значит те элементы D, которые при этом отвечают элементам А, образуют определенное мн-во Е D. Теперь поскольку D А; А и Е связаны взаимооднозначным соответствием , можно образовать мн-во У Е и состоящее из тех элементов Е, которые отвечают эл-ам D. Продолжая этот процесс , мы получим последовательность мн-в: С В А Д Е У … , такую, что:   С А, В D, А Е, Д У….  Отметим при этом, что справедливы и такие соотношения . Вытекающие из самого определения мн-в . Пусть Q=СВАДЕУ…, легко видеть, что С=( )+(В-А)+( )+(Д-Е)+( )+…+Q;  В=(В-А)+( )+(Д-Е)+( )+…+Q. Причем отдельные слагаемые каждой из строк не пересекаются. В силу (*) одинаково подчеркнутые слагаемые обеих сумм эквивалентны друг другу. Но прочие слагаемые этих сумм попарно тождественны, откуда и вытекает эквивалентность С и В. 

11.Суграф, подграф, часть графа. Примеры.Мультиграф G’=(X’,Г’) является суграфом графа G=(X,Г),если множества X и X’ совпадают, a Г’ Г

Мультиграф  G’ является подграфом графа G, если X’ X, Г’=Г пересеч(X’ X’ N)

Мультиграф  G’ является частью графа G, если X’ X, Г’ Г

Представим, что все вершины графа раскрашены в несколько цветов. При этом будем считать, что в этой теме мы рассматриваем только неориентированные графы без кратных ребер. Будем говорить, что граф G правильно раскрашен λ-красками, если каждая его вершина раскрашена одной из λ-красок и вершины одного цвета не смежны. Говорят, что задана правильная раскраска λ-красками.

Граф  G будем называть λ-хроматическим, если существует правильная раскраска графа G λ-красками. Минимальность таких чисел – хроматическое число графа.

7 теорема Кантора.

любое множество А конечное и бесконечное  всегда имеет мощность строго меньше, чем ее булеан. Д-во 1 покажем, что │А│≤│2^А│ 2 покажем, что │А│≠│2^А│

А│≤│В│  ↔ существует f _ин: А->В. f:А->2^А следующим образом, любое а*€А. f(а)={а}€2^А. Данное отображение инъективно, т.к два множества совпадают только тогда, когда они состоят из одних и тех же элементов.  2) методом от противного. Пусть существует   │М│=│2^М│тогда по определению должно существовать биективное отображение Т: 2^М . Любое х€М→Т(х) с М, в таком случае х=”хор” если х€Т(х) х=”нехор” если х≠Т(х). Обозн.через Ω мн-во всех ”нехор” элеметов мн-ва М. Поскольку отображ. биект., а Ω – подмн-во М, значит существует элемент х₀€М, кот. Ω=Т(х₀), если х₀=”хор”, то х₀€Ω→что х₀=”нехор”. Если х₀=”нехор”,то х₀≠ Ω→что х₀=”хор”.Противоречие. данная теорема по сути утверждает о существовании мн-в сколь угодно большой мощности. Действительно, мн-во N-∞, однако по теореме Кантора        │N │<│2^N│<│2^2N│<… 

8 счётные множества.

мн-во счётное, если оно равномощно мн-ву N, т.е если А-счётно→ существует φ биект.: N->А, таким образом каждый элемент множества представим а=φ(n) n € N, a_n€N, т.е А-счётное, если все его элементы можно расположить в виде последов-ти {а1, …аn}=A, поэтому в кач-ве процедуры проверки мн-ва на счётность достаточно найти алгоритм, пересчит-ий элем этого мн-ва. Из теоремы Кантора – существуют бесконечные мн-ва, кот не являются счёт. пример: (0,1)-не счёт. д-во: пусть (0,1) –счёт., тогда все числа можно записать

 y≠x1=0,x11,x12,…  

 y≠x2=0,x21,x22,… 

………

 y≠xn=0,xn1,xn2…

по  допущению здесь    присутствуют все R от (0,1). рассмотрим число у=0, у11, у12,…

у1≠0; 9; x11,  y2≠0; 9; x22,  ….. yn≠0; 9; xnn ….

из  этого следует, что допущение  неверно → список составить нельзя. Все мн-ва равномощные мн-ву R в (0,1) обладают , как говорят, мощность континуума. Обозн.: b. Пусть мощность счётных мн-в │N│=a , 2^a =b , это значит │2^a │=│(0,1)│ 

5 Конеч и бесконеч  мн-ва. Счётные мн-ва Будем говорить что А не превосх по мощности  В если сущ инъектив отображ fин: :А->В на яз мощности: Принято говорить что А конечно если оно состоит из конечного мн-ва эл-ов, в против случ мн-во наз бесконечн. Однако 2 бесконеч мн-ва не обязат равномощны. Мн-во наз счётным если оно равномощно мн-ву N т.е мн-во счётно если все его эл-ты можно распол в виде послед-ти А=(а1, а2,…, аn) В качестве проверки на счётность достаточн найти алгоритм пересчитывающии все эл-ты этого мн-ва. Для более удобного различения равномощ мн-в вводится понятие мощность, идея в след: рассм мн-во всех мн-в, на нём введено отнош равномощн кот явл отнош эквивал, как люб отнош эквивал оно разбив мн-во на классы эквивал-ти, каждый класс наз мощностью.  Данное утвержд нельзя наз определением т.к.оно базируется на понятие мн-ва, а это понятие приводит к парадоксам (Рассела). Теор Кантера-Бернш.|A|=|B| ттт |A|≤|B| и |B|≤|A|. Док-во: пусть f:A->B g:B->A равнознач отображ. 
 
 
 
 
 
 
 
 
 
 

12 Функция π(G,λ).

Для определения  хроматического числа графов существуют и другие теоретические способы. Для вычисления хроматического числа используется функция π(G,λ), которая дает число правильных раскрасок графа G при помощи λ-цветов.

Построение  функции π(G,λ) представляет собой очень трудоемкий процесс. В частности существует специальная формула: ,

где S0=|X|, µ(u_i,…)- количество раскрасок графа G при котором концы ребер u_i, u_j, …, u_l раскрашены одним цветом.

Естественно, формула (*) при больших значениях  S0 применима только для компьютерных расчетах. Для вычисления функции π непосредственно, существует определенная процедура, применимая для достаточно малых значениях S0.

Обозначим через p(s,c) число суграфов графа G, включаемых s-ребер и содержащих с-компонентов связности.