- •Дискретна матЕматика
- •1. Зліченні та незліченні множини. Теореми Кантора.
- •2. Відношення та їх властівості. Відношення еквівалентності та часткового порядку. Фактор-множіна.
- •Операції над відношеннями:
- •3. Зв’язність і планарність графів. Методи перевірки зв’язності і критерій планарності графів.
- •Перевірка зв’язності графів.
- •Плоскі та планарні графи.
- •4. Сполуки, перестановки, розміщення. Поліноміальна теорема.
- •5. Канонічні форми бульових функцій. Алгебра Жегалкіна.
- •6.Повнота і замкненість сістем бульвих функцій. Теорема Поста.
- •Чудові класи замкнених ф-цій
Операції над відношеннями:
1) також як над мн-нами;
2) R-1 наз. Оберненням, до відношення R, якщо а R-1 в тоді і тількі тоді, коли
в R а
3) Композицією відношень R1*R2 наз. R, таке що а R в тоді і тількі тоді, коли існує сМ: (а,с) R1 і (с,в) R2
4) R* – транзитивне замікання від-ня R на М,а R* в тоді і тількі тоді, коли існує (а1,а2,а3,....,аn М) що а1=a, аn=в і а1 R а2, а2 R а3, ...,аn-1 R аn.
Тоді R-транзітівне тоді і тількі тоді, коли R*=R
Озн. 1) Від-ня R наз рефлексивним, якщо для будь-якого аМ а R а
2) Від-ня R наз. антірефлексивним або іррефлексивним, якщо для всіх елементів виконується (а,а)R.
3) Від-ня R наз. симетричним, якщо а R в, тоді в R а;
4) Від-ня R наз. антісиметричним, якщо а R в і в R а, тоді а=в;
5) Від-ня R наз. транзитивним, якщо а R в і в R с, тоді а R с
Відношення еквівалентності:
Озн. Від-ня R наз від-ням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.
Фактор – мн-на:
Нехай Sa={x, що xM, a R x} i bM, bSa: Sb={x, що xM, b R x}.
{Sa, Sb,...} – розбиття М, тоді мн-на {Sa, Sb,... } наз. фактор–мн-ною мн-ни М за від-ням R.
Теорема: Існує взаємнооднозначна відповідність між усіма еквівалентностями на мн-ні М і всіма розбиттями мн-ни М.
Відношення часткового порядку:
Озн. Від-ня R наз від-ням часкового порядку, якщо воно рефлексивне, антіси-метричне і транзитивне.
Мн-на М наз часково впорядкованною, якщо на ній задано часковий порядок.
Мн-на М в якій 2 елементи порівняні наз лінійновпорядкованою або ланцюгом.
Ланцюг М наз цілком впорядкованним, якщо його непорожня підмн-на А має найменшій елемент.
3. Зв’язність і планарність графів. Методи перевірки зв’язності і критерій планарності графів.
Озн. Двійка G=(V,E) наз. графом, якщо V — м-на вершин, а E — м-на ребер на м-ні V.
Озн. Послідовність ребер еі1, еі2,...еік є Е наз. шляхом або маршрутом, якщо кожна пара сусідніх ребер цієї послід. має спільну вершину.
Озн. Шлях наз. ланцюгом, якщо кожне ребро в ньому зустріч. не більше 1 разу.
Озн. Циклічний шлях наз. циклом, якщо він є ланцюгом; простим циклом, коли він є простим ланцюгом(серед його вершин нема однакових).
Озн. Вершини v1 і v2 наз. зв’язними, якщо між ними існує шлях, де v1— початок, v2— кінець.
Озн. Gi , Gi=( Vi,Ei) Gi наз. компонентами зв’язності графа G
Ei= E Vi(2), Vi(2) —м-на двовалентних м-н.
Озн. Граф наз. зв’язним, якщо всі його вершини зв’язні між собою.
Теорема. Довіл. неорієнтов. граф однозначно представляється у вигляді прямої суми зв’язних компонент.
Теорема. Для довіл. неорієнтов. граф G або він або його доповнення є зв’язним.
Теорема. Нехай G — зв’язний граф, G=(V,E) ,e є E, розглянемо G1=(V,E\{e}):
1) Якщо ребро е належало деякому циклу, то G1 також буде зв’язним.
2) Якщо ребро е не належ. ніякому циклу, то G1—незв’язний і має 2 компоненти зв’язності.
Перевірка зв’язності графів.
Методи, які спираються на матрицю суміжності.
Теорема. Нехай А — матриця суміжності графа G=(V,E) з кількістю верщин w, тоді аіj(к) - ел-т Ак дорівнює кількості шляхів із і в j довжини к в графі G
Доведення: Індукцією за к.
1) База індукції к=1, аіj(1)= аіj — 1, якщо є шлях довжини 1 з і в j; 0, якщо нема шляху довж. 1.
Розглянемо окремий доданок цієї суми аіt(m-1) аtj(1). за припущенням індукції перший множник — к-сть шляхів з і в t, другий— з t в j довжини 1, тоді їх добуток— це к-сть шляхів з і в j.
Озн. Граф наз повним, якщо між довільною парою вершин є ребро.
Озн. А*— матриця суміжності графа G*. Граф G буде зв’язним тоді і тільки тоді, коли в А* нема нульових ел-тів.
А*— матр. досяжності, зв’язності, зв’язку для G
ПОБУДОВА А*.
Звести до побудови М(n). простіше буде:
1) С&D логічне (бульове) множення матриць, С— матр. із 0 і 1
Здійснюється моження за законом: fij= (cit dtj). Отримуємо або 0 або 1. Доведення, як у попередньої теореми.