Дискретна математика для програмістів
Ознайомлення з історією виникнення теорії множин. Способи опису характеристичних властивостей множин. Декартовий добуток та бінарні відношення. Ін’єктивні, сюр’єктивні та бієктивні відображення. Поняття та властивості бінарної алгебраїчної операції.
| Рубрика | Математика |
| Вид | лекция |
| Язык | украинский |
| Дата добавления | 28.10.2014 |
| Размер файла | 2,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Рисунок 2.8 - Властивості відображення
Для скінченних множин Х та Y сюр'єктивнiсть відображення f : X > Y означає, що | Х | ? | Y |. Наприклад; f: {1, 2, 3, 4} > {y1, y2, y3}, f = - сюр'єктивне, a f = - не сюр'єктивнe.
Якщо Х і Y скінченні, то ін'єктивність відображення означає, що | Х | ? | Y |.
Наприклад, нехай Х = {l, 2, 3}, Y = {y1, y2, y3, y4}. Якщо f (1) = y1, f (2) = y2, f (3) = y3, то f : X > Y ін'єктивнe.
При скінченних X та Y бієктивнiсть відображення f : X > Y означає, що | X | = | Y |.
Наприклад, X = (1, 2, 3), Y = {y1, y2, y3}, відображення f = - бієктивне.
2.6.4 Композиція відображень
Нехай задано два відображення: f : X > Y та g: Y > Z. Тоді композицією відображень f і g (позначаємо символом g _ f) будемо називати відображення з множини X в множину Z, визначене виразом g _ f (x) = g(f (x)) для всіх елементів x з множини X. Прийняте правило, згідно з яким у композиції g _ f треба починати з відображення f, розташованого праворуч.
Наприклад, нехай маємо множини Х = {l, 2, 3, 4}, Y = {а, b, c}, Z = {u, v}та два відображення
f : Х > Y, , g : Y > Z,
Тоді композиція заданих відображень g _ f: Х > Z,
Композиція відображень асоціативна, тобто якщо маємо три відображення f : X > Y, g: Y > Z, h: Z > U, то (h _ g) _ f = h _ (g _ f) = h _ g _ f.
Відображення g: Y > X називається оберненим до відображення f : X > Y, якщо виконуються такі умови f -1 _ f = IX (IX - тотожне відображення на множині X), f _ f -1 = IY (IY - тотожне відображення на множині Y).
Для відображення f існує обернене відображення f -1 тоді і тільки тоді, коли відображення f бієктивне. Обернене відображення f -1 також є бієктивним.
Якщо f :X > Y - бієкція й g: Y > Z - бієкція, то g _ f - бієкція з Х в Z, а її обернена бієкція дорівнює f -1 _ g -1.
Наприклад, нехай задані множини Х ={l, 2, 3}, Y = {а, b, c} та відображення f : Х > Y, . Це відображення є бієктивним, і тому до нього існує обернене f -1: Y > X, . Дійсно, f -1 _ f == IX та f _ f -1 == IY.
2.7 Функції
Визначення. Функцією називається таке відношення , ніякі два різних елементи якого не мають однакових перших координат. Тобто є функцією тоді й тільки тоді, коли вона задовольняє наступним умовам:
_ елементами є упорядковані пари;
_ якщо упорядковані пари і _ елементи функції , то .
Отже, відношення на називається функцією з в і позначається як .
Якщо функція і , то говорять, що .
Визначення. Множина називається областю визначення функції і позначається , а множина _ областю потенційних значень. Якщо , то множина називається образом множини . Образ усієї множини називається областю значень функції і позначається .
Приклад. Які із представлених відношень є функціями:
а) ; б) ;
в) ; г) .
Розв'язання:
а) відношення не є функцією, тому що два елементи і мають однакову першу координату;
б) відношення є функцією, тому що перший елемент кожної впорядкованої пари зустрічається рівно один раз;
в) відношення є функцією, графіком якої буде парабола;
г) відношення не є функцією, тому що його елементами є, наприклад, і , і .
Приклад. Знайти область визначення і область значень функції:
а) ;
б) .
Розв'язання:
а) область визначення функції , а область значень _ ;
б) область визначення _ , а область значень _ .
Визначення. Функція називається ін'єктивною, або ін'єкцією, якщо з прямує (рис. 2.9,а). Функція називається "відображенням на", сюр'єктивною функцією, або сюр'єкцією, якщо для кожного існує деяке таке, що (рис. 2.9,б). Функція, що є одночасно і ін'єктивною і сюр'єктивною, називається бієктивною або взаємнооднозначною (рис. 2.9,в).
Рисунок 2.9 - Властивості функцій
Можна привести ще одне визначення взаємнооднозначної функції.
Визначення. Функція називається взаємнооднозначною, якщо вона переводить різні елементи в різні. Тобто з умови прямує .
Якщо _ обернене відношення до взаємнооднозначного функціонального відношення , то визначає функцію , яку називають оберненою до функції .
Ін'єктивна функція має обернену функцію .
Функція , обернена до бієктивної, є відображенням не на множину , а в множину .
Взаємноодназначність функції зручно доводити виходячи з міркувань: "з умови прямує ".
Приклад. Чи є функція взаємнооднозначною?
Розв'язання:
; .
З умови прямує;
.
Отже і функція є взаємноодназначною.
Визначення. Нехай _ функція із множини в множину , тобто . Обернене відношення визначається як . При цьому називається перетворенням функції , або її оберненою функцією.
Приклад. Знайти функцію, обернену до даної: .
Розв'язання:
Обертаючи функцію, одержуємо , але це те ж саме, що і . Вирішуючи рівняння відносно , одержуємо .
Тобто, якщо , то .
Відповіді на питання, чи є представлене відношення функцією і чи є функція взаємнооднозначною, можна легко одержати за допомогою його графічної ілюстрації.
Відповідно до визначення функції, ніякі два різних елементи відношення не можуть мати однакових перших координат. Отже, промінь, спрямований паралельно осі , повинен перетинати графік відношення не більше одного разу. Тому що взаємнооднозначні функції переводять різні елементи в різні, то промінь, спрямований паралельно осі , повинен перетинати графік відношення теж не більше одного разу.
Приклад. З'ясувати, чи є дані відношення функціями? Якщо так, то чи будуть вони взаємнооднозначні? У випадку позитивної відповіді, знайти обернені функції:
а) ; б) ;
в) .
Розв'язання:
а) відношення не є функцією, тому що існує два різних елементи, що мають однакові перші координати (рис. 2.10, а);
б) відношення є функцією, тому що не існує елементів, що мають однакові перші координати. Дана функція не є взаємнооднозначною, тому що існують елементи, що мають однакові другі координати (рис. 2.10, б);
в) відношення є функцією. Дана функція є взаємнооднозначною, тому що переводить різні елементи в різні (рис. 2.10, в). Знайдемо функцію, обернену до даної:
;
;
;
.
Рисунок 2.10 - Види відношень
Визначення. Нехай дані дві функції і , де _ довільні множини. Функція визначена на і приймає значення на , а функція визначена на і приймає значення на . Якщо для кожного найдеться такий елемент , що , то така відповідність між множинами і називається композицією або суперпозицією функцій і і позначається (рис. 2.11).
Рисунок 2.11 - Композиція функцій
Приклад. Функції і задані на множині дійсних чисел. Знайти композицію функцій і .
Розв'язання:
;
.
3. Алгебраїчні системи
3.1 Поняття бінарної алгебраїчної операції
Кожна математична теорія вивчає множини, на яких введені певні відношення. Алгебра вивчає множини, на яких визначені відношення, що мають назву алгебраїчних операцій. З прикладами алгебраїчних операцій ми зустрічалися ще в шкільному курсі математики, а також вивчаючи інші розділи вищої математики. Прикладами алгебраїчних операцій є додавання і множення чисел, многочленів, алгебраїчних дробів, додавання векторів площини, додавання матриць, об'єднання і переріз множин, додавання і множення функцій (наприклад, синусів і косинусів), композиція відображень тощо. Ці операції виконуються над парами елементів однієї і тієї ж множини: над парами чисел, многочленів, векторів, функцій. Тому їх називають бінарними алгебраїчними операціями або просто бінарними операціями. Дамо нижче загальне означення бінарної алгебраїчної операції, якому, зокрема, задовольняють перелічені вище операції.
Визначення. Нехай - довільна множина елементів . Бінарною алгебраїчною операцією (або законом композиції) на множині називається довільне (але фіксоване) відображення декартового квадрата в . Таким чином, будь-якій впорядкованій парі елементів однозначно ставиться у відповідність певний третій елемент тієї ж множини .
Іноді замість пишуть , а ще частіше конкретну бінарну операцію позначають спеціальним символом: +, *, , і т.д. Але коли вивчають загальні властивості бінарних операцій, тобто властивості, притаманні багатьом конкретним бінарним операціям, то кажуть про довільні операції, для позначення яких будемо користуватися символами і .
Із означення випливає: для того, щоб відображення було бінарною алгебраїчною операцією на множині , необхідно, щоб задовольняло вимоги:
1) було бінарним;
2) було завжди виконуваним, тобто завжди можна було б знайти результат виконання операції - елемент ;
3) було однозначним, тобто елемент був єдиним;
4) задовольняв би умову замкненості, тобто щоб обов'язково .
Приклад.
1. Нехай - відповідно множини цілих, раціональних, дійсних та комплексних чисел. Бінарними алгебраїчними операціями на цих множинах є, наприклад, дії додавання, віднімання та множення.
2. Нехай - множина всіх квадратних матриць порядку з дійсними елементами. Бінарними алгебраїчними операціями на множині є, наприклад, дії додавання, віднімання та множення матриць.
3. Дія знаходження модуля дійсного числа не є бінарною операцією на множині , оскільки не виконується вимога бінарності.
Звичайно бінарна операція на скінченній множині з елементів задається так званою таблицею Келі, яка являє собою квадратну -таблицю з двома входами, кожній клітинці якої відповідає впорядкована пара елементів даної множини, елемент стоїть у вибраному рядку, елемент - у вибраному стовпці.
Приклад. У множині задано бінарну операцію так, що є остачею від ділення добутку на число 4. Задати бінарну операцію таблицею Келі.
Розв'язання. Таблиця Келі для операції у множині має вигляд:
3.2 Властивості бінарних алгебраїчних операцій
Визначення. Операція на множині називається комутативною, якщо .
Приклади.
Додавання і множення чисел комутативні.
Віднімання і ділення чисел некомутативні.
Множення матриць некомутативне.
Операції перерізу і об'єднання множин комутативні.
Операція декартового добутку двох множин некомутативна.
Значення комутативності бінарної алгебраїчної операції полягає в тому, що вона дає можливість переставляти елементи, над якими виконується бінарна операція, і завдяки цьому спрощувати формули і твердження.
Таблиця Келі комутативної бінарної алгебраїчної операції симетрична відносно діагоналі.
Приклад. Операція у множині з прикладу 1 є комутативною, оскільки її таблиця Келі симетрична відносно діагоналі.
Визначення. Операція на множині називається асоціативною, якщо :.
Властивість асоціативності дозволяє опускати дужки у виразі .
Приклади.
Додавання і множення чисел асоціативні. Це дозволяє не ставити дужки у виразах і .
Віднімання чисел неасоціативне:
(Наприклад, )
Операції перерізу і об'єднання множин асоціативні.
Значення асоціативності бінарної алгебраїчної операції полягає в тому, що вона дає можливість визначити композицію трьох і взагалі будь-якого числа елементів множини, взятих у певному порядку.
Визначення. Операція на множині називається дистрибутивною зліва відносно операції , якщо
і дистрибутивною справа відносно операції , якщо
.
Якщо операція комутативна на множині , то поняття дистрибутивності зліва і справа збігаються. В цьому випадку просто кажуть, що операція дистрибутивна відносно операції .
Приклади.
Множення чисел дистрибутивне відносно додавання і зліва і справа:
і
Додавання недистрибутивне і зліва і справа відносно множення:
та .
Операції перерізу і об'єднання множин є взаємно дистрибутивними одна відносно одної.
Далі будемо припускати, що всі бінарні операції, які будуть розглядатися, асоціативні. В цьому випадку неважко визначити степінь елемента множини у такий спосіб: визначаємо , при покладаємо: . Тоді для будь-яких додатних цілих чисел виконуються співвідношення:
і .
Разом з бінарними алгебраїчними операціями не позбавлені інтересу більш загальні -арні операції, так само як і їх комбінації.
Визначення. -арною алгебраїчною операцією на множині називається відображення . Число називається арністю операції .
-арна алгебраїчна операція за елементами множини визначає -й елемент цієї ж множини. При будемо мати відповідно унарну, бінарну, тернарну і т.д. алгебраїчні операції.
Приклади.
1. Перехід до протилежного числа є унарною операцією.
2. Піднесення числа до квадрату є унарною операцією.
3. Знаходження абсолютної величини числа є унарною операцією.
4. Операція доповнення множини є унарною операцією.
3.3 Обернені бінарні операції
Нехай на множині визначена бінарна алгебраїчна операція .
Визначення. Якщо для будь-яких двох елементів і множини існує в множині одна і тільки одна пара елементів і таких, що і , то кажуть, що для визначеної на множині бінарної алгебраїчної операції виконується обернена операція, яку позначають .
Ясно, що якщо операція комутативна, то елементи і , про які йдеться в означенні, збігаються.
Приклади.
1. Операцію, обернену до комутативної операції додавання (множення) чисел називають відніманням (діленням). Елемент , який задовольняє умовам і ( і ), називають різницею (часткою) і записують ( або ).
Існують множини, в яких операції додавання і множення визначені, а обернені їм операції віднімання і ділення не виконуються. Такою множиною є, наприклад, множина натуральних чисел . Існують також множини, наприклад, множина цілих чисел , в яких визначена операція додавання і виконується обернена їй операція - віднімання, а також множини, як, наприклад, множина відмінних від нуля раціональних чисел, в яких визначена операція множення і виконується обернена їй операція - ділення.
Обернена операція , очевидно, не є новою незалежною операцією, вона - похідна від операції .
3.4 Елементи, виділені відносно бінарної операції
Визначення. Якщо існує елемент такий, що , то він називається ідемпотентним по відношенню до операції , або просто ідемпотентом.
Визначення. Якщо існує елемент такий, що , то він називається нейтральним відносно операції , або одиничним.
Приклади.
1. В множині 0 - нейтральний елемент відносно додавання +:
, а 1 - відносно множення :
2. В множині всіх квадратних матриць -го порядку нульова матриця є нейтральним елементом відносно додавання матриць, а одинична матриця - відносно множення матриць.
3. В множині всіх підмножин деякого універсуму - нейтральний елемент відносно об'єднання: , а - нейтральний елемент відносно перерізу: .
Теорема (про єдиність нейтрального елемента). Якщо відносно операції існує нейтральний елемент, то він єдиний.
Доведення. Припустимо, що існують два нейтральних відносно операції елементи та і , тобто
;
.
Тоді , оскільки - нейтральний елемент, і , оскільки - нейтральний елемент. Отже . Одержана суперечність доводить теорему.
Визначення. Елемент називається симетричним елементу відносно операції , якщо , де - нейтральний відносно операції елемент.
Приклади.
1. Нейтральний елемент , очевидно, симетричний сам собі.
2. В множині відносно додавання симетричним елементу є елемент , який називається протилежним до . Відносно множення симетричним елементу є елемент , який називається оберненим до .
3. В множині всіх квадратних матриць -го порядку відносно операції множення матриць симетричними є взаємно обернені матриці.
Теорема (про єдиність симетричного елемента). Якщо бінарна операція , визначена на множині , асоціативна, то для будь-якого елемента в ньому може існувати не більше одного симетричного елемента.
Доведення. Припустимо, що і - два різних симетричних елементу елемента, так що
, .
Тоді
.
Одержана суперечність доводить теорему.
Приклад. Визначити елементи, виділені відносно операції у множині з прикладу 1.
Розв'язання. Щоб визначити нейтральний елемент, знайдемо стовпець таблиці Келі, що цілком збігається з початковим. В таблиці для операції такий стовпець є, і йому відповідає елемент 1. Отже, елемент 1 є нейтральним відносно операції .
Щоб визначити існування симетричного елемента для даного, рухаємося по рядку, який відповідає даному елементу, до нейтрального елемента. Зверху, у початковому рядку, напроти нейтрального елемента знаходиться шуканий симетричний.
Для елемента 2 не існує симетричного, оскільки 20=22=0 і 21=23=2.
3.5 Поняття алгебраїчної структури
На непорожній множині може бути задано, взагалі кажучи, багато різних алгебраїчних операцій. Бажаючи виділити одну з них, використовують дужки: , і говорять, що операція визначає на алгебраїчну структуру. Якщо операція асоціативна чи комутативна, то такі ж назви привласнюються і відповідній алгебраїчній структурі. Природа елементів основної множини нас не цікавить, справжніми об'єктами вивчення є алгебраїчні операції. Ясно, що виділити можна не одну операцію, а декілька.
Визначення. Непорожня множина разом із заданою на ній сукупністю алгебраїчних операцій називається алгебраїчною структурою: .
Приклад. У множині цілих чисел, крім природних операцій +, * (додавання і множення), легко вказати "похідні" операції що виходять при допомозі + (або -) і : , і т.д. Ми приходимо до різних алгебраїчних структур , .
В процесі розвитку математики була виділена і детально досліджена невелика кількість основних типів алгебраїчних структур, алгебраїчні операції в яких за своїми властивостями більш-менш близькі до операцій додавання і множення. У зв'язку з цим при вивченні алгебраїчних структур застосовуються дві системи термінів або дві форми запису: адитивну і мультиплікативну. Нижче наводиться словник цих термінологій:
|
Адитивна термінологія |
Мультиплікативна термінологія |
||
|
Операція |
+ - додавання |
- множення |
|
|
Результат операції |
сума |
добуток |
|
|
Нейтральний елемент |
нуль 0 |
одиниця 1або е |
|
|
Симетричний елемент |
протилежний -а |
обернений або |
|
|
Обернена операція |
віднімання |
ділення |
|
|
Результат оберненої операції |
різниця |
частка |
|
|
Степінь елемента |
кратне |
степінь |
Крім операцій, на множині можуть бути визначені різні відношення.
Визначення. Непорожня множина разом із заданою на ній сукупністю алгебраїчних операцій і сукупністю відношень називається алгебраїчною системою: . Якщо алгебраїчна система не містить операцій, вона називається моделлю, якщо не містить відношень - алгеброю.
Приклади.
1. є алгебраїчною системою.
2. не є алгебраїчною системою, оскільки результат операції - не завжди є натуральним числом.
3. є алгебраїчною системою. Ця алгебраїчна система носить назву "арифметика".
4. Множина дійсних функцій однієї дійсної змінної, тобто функцій разом з унарною операцією диференціювання утворює алгебру
.
3.6 Основні типи алгебраїчних структур
Якщо визначити на деякій множині одну або дві бінарні операції і наділити їх певними властивостями, а також визначити наявність нейтральних і симетричних елементів відносно цих бінарних алгебраїчних операцій, можна дістати різні алгебраїчні структури.
1) Алгебраїчні структури з однією бінарною операцією: півгрупи і групи
Визначення. Півгрупою називається непорожня множина з однією бінарною алгебраїчною операцією , яка має тільки властивість асоціативності
.
Приклади.
1. - півгрупа.
2. - півгрупа.
Визначення. Групою називається непорожня множина , на якій визначена бінарна алгебраїчна операція , так, що виконуються наступні умови (аксіоми групи):
1) операція асоціативна:
;
2) в множині існує нейтральний елемент :
;
3) для кожного елемента існує симетричний елемент :
.
Позначається або просто .
Означення групи можна сформулювати ще й так:
Визначення. Групою називається півгрупа з одиницею, в якій для кожного елемента існує симетричний.
Група, в якій операція комутативна, тобто називається комутативною або абелевою. (на честь норвезького математика Нільса Хенріка Абеля (1802-1829)), який вивчав комутативні групи).
Визначення. Група, в якій всі елементи основної множини є степенями одного елемента, тобто є результатами k-кратного застосування операції (k=0,1,2,...), називається циклічною. Цей єдиний елемент називається твірним елементом циклічної групи. Циклічна група з твірним елементом позначається так: і є абелевою групою вигляду або в залежності від того, яка група розглядається - мультиплікативна або адитивна.
Число елементів групи називають її порядком.
Приклади.
1. - абелева група цілих чисел, нейтральний елемент 0, оберненим до елемента є .
2. - абелева група раціональних чисел, нейтральний елемент 1, оберненим до елемента є .
3. Множина невироджених матриць порядку відносно операції множення матриць є некомутативною групою.
4. Множина коренів -го степеня з 1 є циклічною групою.
2) Алгебраїчні структури з двома бінарними операціями:
кільця і поля
Визначення. Кільцем називається непорожня множина , на якій визначені дві бінарні алгебраїчні операція + (додавання) і (множення) так, що виконуються наступні умови (аксіоми кільця):
К1. - абелева група:
1) операція + асоціативна:
;
2) в множині існує нульовий елемент :
;
3) для кожного елемента існує протилежний елемент :
.
4) операція + комутативна:
.
К2. - півгрупа:
5) операція асоціативна:
;
К3. Операція (множення) дистрибутивна зліва і справа відносно операції+(додавання):
6) ;
;
Кільце позначається або просто .
Алгебраїчна структура називається адитивною групою кільця, а - його мультиплікативною півгрупою.
Визначення. Кільце називається комутативним, якщо операція (множення) є комутативною, тобто .
(На відміну від груп, комутативне кільце не прийнято називати абелевим).
Означення кільця можна сформулювати ще й так:
Визначення. Кільцем називається множина з двома операціями + і ., яка відносно + є групою, а відносно є півгрупою і дистрибутивна відносно +.
Приклад. - кільце цілих чисел.
Визначення. Полем називається непорожня множина , на якій визначені дві бінарні алгебраїчні операція + (додавання) і (множення) так, що виконуються наступні умови (аксіоми поля):
1) операція + асоціативна на :
;
2) в множині існує нульовий елемент :
;
3) для кожного елемента існує протилежний елемент :
.
4) операція + комутативна на :
.
5) операція асоціативна на
: ;
6) операція дистрибутивна зліва і справа відносно операції+:
;
7) операція комутативна на :
;
8) в множині існує одиничний елемент :
9) для кожного ненульового елемента існує в обернений до нього елемент :
.
Означення поля можна сформулювати ще й так:
Визначення.
Полем називається комутативне кільце, елементи якого, відмінні від нульового елемента утворюють групу відносно операції .
Приклад.
1. - поле раціональних чисел.
2. - поле дійсних чисел.
3. - поле комплексних чисел.
3.7 Ізоморфізми та гомоморфізми алгебраїчних структур
Визначення. Нехай - алгебраїчна операція, задана на множині , - алгебраїчна операція, задана на множині , - відображення множини в множину . Кажуть, що відображення зберігає алгебраїчну операцію , якщо для будь-яких елементів справедливо
.
Зміст цієї умови полягає в тому, що не має значення, чи здійснено спочатку операцію в , а потім виконане відображення , або спочатку виконане відображення , а потім здійснено операцію в .
Визначення. Дві алгебраїчні структури і називаються гомоморфними, якщо існує відображення , яке зберігає алгебраїчні операції. Відповідне відображення називається гомоморфізмом.
Визначення. Дві алгебраїчні структури і називаються ізоморфними, якщо існує взаємно однозначне відображення , яке зберігає алгебраїчні операції. Відповідне відображення називається ізоморфізмом.
Факт ізоморфізму алгебраїчних структур позначається символічно .
Визначення. Дві групи і називаються гомоморфними, якщо існує відображення , при якому зберігається групова операція, тобто таке, що .
Визначення. Дві групи і називаються ізоморфними, якщо існує взаємно однозначне відображення , при якому зберігається групова операція, тобто таке, що:
1) ;
2) - бієкція.
Визначення. Два кільця і називаються гомоморфними, якщо існує відображення , при якому зберігаються операції, тобто таке, що:
1) ;
2) ;
3)
,
.
Визначення. Два кільця і називаються ізоморфними, якщо існує гомоморфне взаємно однозначне відображення.
Визначення. Два поля і називаються ізоморфними, якщо вони ізоморфні як кільця.
3.8 Булеві алгебри
Визначення. Булевою алгеброю називається алгебраїчна структура з трьома операціями і двома виділеними елементами 0 і 1, така що дві її операції є бінарними і задовольняють наступним умовам:
1. , , - ідемпотентність;
2. : , - комутативність;
3. , - асоціативність
4. ??, - поглинання.
5. , ,
6. .
7. ,
- дистрибутивність,
а третя операція є унарною і задовольняє наступним умовам:
8. .
Приклад. Нехай заданий деякий універсум . Позначимо систему всіх його підмножин через . Множина разом з бінарними операціями і унарною операцією утворює алгебру . Алгебра підмножин є булевою алгеброю. Одиницею в ній є , нулем - .
Має місце
Теорема Стоуна. Будь-яка булева алгебра ізоморфна алгебрі підмножин множини, яка для неї підходить.
Таким чином, булеві алгебри цілком можуть бути зведені до алгебр підмножин. З теореми випливає, що операції булевих алгебр мають всі властивості операцій над множинами: ідемпотентність, комутативність, асоціативність, дистрибутивність, закони поглинання та інші.
4. Комбінаторний аналіз
Методи комбінаторики широко використовуються в теорії імовірностей, математичній логіці, теорії графів тощо. Вони є могутнім знаряддям при рішенні практичних задач, зв'язаних із перерахуванням, розподілом і розбиттям множин на класи еквівалентності.
Функції логіки в цьому відношенні не становлять собою виняток і в рамках задач синтезу нам доведеться часто застосовувати комбінаторні прийоми для їхнього рішення. При цьому будемо використовувати ряд класичних методів, характерних для цієї галузі математики: правила суми і добутку, формулу включення і вилучення та рекурентні співвідношення.
Перехід від теорії множин до комбінаторики пояснюється ще й тим, що в наступних розділах будемо зіштовхуватися не тільки з множинами чисел, але й з послідовностями чисел, їхніми наборами. Такі послідовності не можна розглядати як множини, по-перше, через те, що в послідовностях цифри можуть повторюватися, а в множинах елементи не повторюються, по-друге, у наборах важливий порядок цифр (<012> і <210> - різні набори), а в множинах порядок елементів ролі не грає. Тому, приступаючи до вивчення об'єктів, що описуються логікою, для їхнього опису потрібно ввести нове поняття для послідовності чисел. Таким у дискретному аналізі є поняття "кортеж", що визначається так.
Нехай наявні кілька множин Х1, Х2,..., Хk. Якщо тепер із кожної множини брати по одному елементу в порядку зростання номерів множин чи у якому-небудь іншому порядку, потім розташувати ці елементи в тому порядку, у якому ми їх вибирали (а1, а2,... аk), то ця послідовність і буде кортежем довжини k, складеним iз елементів множин Х1, Х2,..., Хk Елементи а1 а2,... аk називаються компонентами, чи координатами, кортежа.
Два кортежі називаються рівними в тому і тільки у тому випадку, коли вони мають однакову довжину, а на відповідних місцях розташовані ті самі елементи. У кортежах координати можуть повторюватися. Наприклад, кортеж може мати такий вид: (1, 2, 3, 4, 4, 6). Не вилучений і такий випадок, коли всі множини Х1, Х2,..., Хk збігаються.
4.1 Правило добутку
Візьмемо кілька скінченних множин Х1, Х2,..., Хk, що складаються з n1, n2, …, nk елементів, і знайдемо, скільки кортежів довжини k можна скласти з елементів цих множин. Спочатку знайдемо число кортежів довжиною 1, складених з елементів множини X1. Ясно, що їхнє число дорівнює n1. Візьмемо тепер один із цих кортежів (а1) і припишемо до елемента а1 праворуч по черзі всі елементи множини Х2. Отримаємо n2 кортежів довжиною 2, у яких перша координата дорівнює а1. Але замість а1 можна було б узяти будь-який інший елемент із Х1. Тому одержуємо n1 раз по n2 кортежу, а усього n1,n2 кортежів довжиною 2. Із кожної такої пари одержимо n3 трійок, приписавши до неї по черзі всі елементи множини Х3, а усього n1 n2 n3 трійок.
Продовжуючи цей процес, зрештою одержуємо n1 n2 … nk кортежів довжиною k, складених із елементів множин Х1, Х2,..., Хk.
Даний результат є одним з найважливіших у комбінаторному аналізі. На ньому базується вивід багатьох формул цієї й інших наук.
Оскільки для підрахунку числа всіляких кортежів приходиться перемножати числа n1 n2 … nk, то отриманий результат називається також правилом добутку. Сформулюємо це правило так:
Якщо елемент а1 можна вибрати n1 способами, то після кожного вибору цього елемента наступний за ним а2; можна вибрати n1 n2 способами. Якщо елемент аk вибирається nk способами, то кортеж (а1, а2,... аk) можна вибрати n1 n2 … nk способами.
Підрахуємо, наприклад, число різних наборів для випадку, коли . У цьому випадку на перше місце в нас k кандидатів, але після того як б1 вибрано, б2 можна вибрати також k способами тощо. Оскільки число місць дорівнює n, то одержуємо k k ... k - n раз, тобто kn .
4.2 Правило суми
Якщо елемент , а елемент і при цьому елемент Х1 може бути обраний n способами, а елемент Х2 - іншими m способами, то вибір "чи то Х1, чи то Х2" може бути здійснений n + m способами. Варто мати на увазі, що вибiр Х1, чи то Х2 є тут взаємовиключними. Інакше кажучи, необхідно стежити, щоб жоден зі способів вибору об'єкта Х1 не збігся з яким-небудь способом вибору об'єкта Х2. При наявності таких збігів правило суми незастосовне і результат дорівнює m + n - р, де р - число збігів.
4.3 Розміщення
4.3.1 Розміщення з повтореннями
Множини Х1, Х2,..., Хk, із елементів яких складаються кортежі, можуть мати спільні елементи. Зокрема , усі вони можуть збігатися з тією ж самою множиною Еk, що містить k елементів. Кортежі довжиною n, складені з елементів k множини Еkk, називаються розміщеннями з повтореннями з k елементів по n, а їхнє число (A із k по n); А - від слова arrangement - розміщення. Риска ставиться, щоб відрізнити їх від розміщень без повторень, про які мова йтиме далі. З огляду на приклад направила добутку, відразу одержуємо, що число розміщень с. повтореннями з k елементів по n дорівнює kn. Отже, доведена формула
= kn. (4.1)
4.3.2 Розміщення без повторень
Наявна множина Еk, що складається з k елементів. Визначити, скільки кортежів заданої довжини n можна скласти з елементів цієї множини, якщо всі елементи кожного кортежу повинні бути різними. Кортежі, що підпорядковані цій умові, називаються розміщеннями без повторень із k елементів по n, а їхнє число позначається .
Щоб обчислити , міркуємо так: на перше місце в нас k кандидатів. Після того як воно заповнено, на друге місце залишається k - 1 кандидатів, на третє k - 2 і т.д. На п-і місце наявні k - n + 1 кандидатів (після того як ми вибрали n - 1 елемент, залишається k- (n-1) = k - n +1 елементів). Застосовуючи правило добутків, одержуємо
= k (k - l) ... (k-n+1). (4.2)
Розміщення без повторень із k елементів по k складаються з тих самих елементів, розташованих у різному порядку.
Такі розміщення називаються перестановками з k-елементів і позначаються Рk.
Тоді за формулою (4.2) визначаємо
(4.3)
Тепер, використовуючи вирази (4.3) та (4.2) можна переписати в такому виді:
= (4.4)
Добуток виду k (k - 1) ... 1 часто зустрічається як у комбінаториці, так і в алгебрі, тому для нього уведена окрема назва k-факторіал, що позначається k!. (читається k-факторіал).
4.4 Перестановки
Перестановки з повтореннями.
Розглянемо перестановки з повтореннями з k елементів, специфікація яких n =k1 + k2 + ... +kn, причому n = k. Через збіг деяких елементів число таких перестановок виявляється меншим, ніж k!, тому що перестановка однакових елементів нічого не змінює. Елементи j-го класу допускають перестановку kj! способами, і в кожному класі такі операції здійснюються незалежно. Тому відповідно до правила добутку можна здійснити k1! k2!... kn! перестановок, що не змінюють дану перестановку. Але k чисел можна переставляти одне з одним k! способами. Тому число розміщень з повтореннями елементів, що мають склад (k1! k2!... kn!), у k1! k2!... kn! менше, ніж k!:
(4.5)
Якщо запас об'єктів k різних типів не обмежений, то кожне місце в можна заповнити k різними способами. Тому, відповідно до правила добутку, число перестановок з необмеженими повтореннями дорівнює kn. Це співвідношення визначає кількість різних n-розрядних чисел, записаних у позиційній системі числення з основою системи числення k.
4.5 Сполучення (комбінації)
Визначимо, скільки різних складів можуть мати кортежі довжиною n iз k елементів.
По-іншому цю ж задачу можна сформулювати так: назвемо два кортежі еквівалентними, якщо вони мають однаковий склад. Звідси формулювання: на скільки класів еквівалентності розбивається при цьому вся сукупність кортежів довжиною n із k елементів? Такі класи еквівалентності називаються сполученнями з повтореннями з k елементів по n, а їхнє число позначається .
Будь-який склад кортежа довжиною n із k елементів має вигляд , де - невід'ємні цілі числа, сума яких дорівнює n. Заміняючи кожне з чисел . відповідним числом одиниць і розділяючи нулями одиниці, що відповідають різним числам, одержуємо кортеж з k - 1 нулів і n одиниць. При цьому кожному складу відповідає один і тільки один запис за допомогою нулів і одиниць, а кожен такий запис задає один і тільки один склад. Тому число різних складів, що можуть мати кортежі довжиною n iз k елементів, дорівнює числу перестановок з повтореннями з k - 1 нулів і n одиниць, тобто .= Р (k - 1, n). Тоді
(4.6)
Покажемо, чому дорівнює потужність n-підмножин у k-множинi Еk Такі підмножини називаються сполученнями з k елементів по n і позначаються .
Задача про обчислення зводиться до задачі про число розміщень без повторень з k елементів по n, що буде в n! (число розміщень із k по n) разів менше, тобто
(4.7)
Справді, розставимо будь-як задані k елементів і зашифруємо будь-який вибір, n елементів кортежем довжиною k iз n одиниць по k - n нулів - якщо елемент вибирають, тo на його місце пишуть 1, а якщо ні, - тo 0.
Наприклад, вибір елементів а, c iз елементів a, b,c, d, e записується кортежем 10100. Кожному кортежу відповідає свій спосіб вибоpу елементів. Тому число n-підмножин у k-множинi дорівнює числу перестановок iз повтореннями із k -n п нулів i n одиниць, тобто дорівнює P(k-n, n) із (4.7).
Виходить
(4.8)
Наслідок. Рівності (4.6) і (4.7) показують, що
== (4.8)
Розглянуті способи доведення формул і базуються на заміні однієї множини іншою, елементи яких є у взаємнооднозначній відповідності і, отже, їхнє число в цих множинах однакове.
Властивості сполучень.
Оскільки числа показують, скільки n-підмножин міститься в даній k-множинi, то між ними існує цілий ряд залежностей, що відбивають різні залежності між підмножинами.
Ці залежності можна доводити різними способами. У деяких випадках найзручніше прямо скористатися формулою (4.7) для числа сполучень. Проте більш красивим і змістовнішим є інший спосіб, заснований на комбінаторних засадах. Спочатку підраховуємо число підмножин деякого виду і розбиваємо сукупність усіх таких підмножин на класи так, щоб жодна підмножина не потрапила в два різних класи. Після цього знаходимо, скільки підмножин входить у кожен клас. Складаючи отримані числа, знову одержуємо кількість підмножини обраного виду. Це і дає шукане співвідношення.
Властивість 1. Найбільш простим є співвідношення
= (4.9)
яке показує, що число n-підмножин у k-множинi збігається з числом (k - n)-множин тієї ж множини.
Доведення. Якщо з k-множини видалити n-підмножинy Y, то залишиться (k - n)-підмножина або доповнення до Y в X. Тому з n-підмножин і їхніх доповнень можна утворити пари такі, що кожна n-підмножина і кожна (k - n)-підмножина потраплять лише в одну пару. А це й означає, що таких підмножин однакова кількість, тобто = .
Властивість 2. Зафіксуємо тепер який-небудь із k елементів, наприклад а, і розіб'ємо всі сполучення з k елементів no n на два класи - , що містять елемент а і не містять цього елемента. Число сполучень першого класу дорівнює , тому що в цьому класі з тих, що залишилися k - 1 елементів треба вибрати ще n - 1 елемент. Число сполучень другого класу дорівнює . Треба вибрати n із всіх елементів, крім а. Але будь-яке сполучення відноситься чи то до першого, чи то до другого класу. Тому
(4.10)
4.6 Формула включень і вилучень
До тепер мова йшла про підрахунок числа підмножин, що утворяться шляхом вибірки об'єктів із деякої множини відповідно до умов, що визначають їхню кількість, упорядкованість і повторюваність. Не менше значення мають задачі перерахування, зв'язані з властивостями об'єктів.
Нехай наявні N об'єктів і деяка сукупність властивостей . Позначимо тощо кількість об'єктів, що мають властивості відповідно тощо. Очевидно, таких чисел буде стільки, скільки підмножин можна утворити з елементів множини Н, тобто 2n (деякі числа можуть дорівнювати нулю). Для об'єктів, що не володіють властивістю , уводиться позначення .
Звідси число об'єктів, що не володіють жодною із властивостей множини Н, визначається формулою включення і вилучення:
(4.11)
Основна формула випливає безпосередньо з визначення операції об'єднання множин
Дійсно, при відніманні від N об'єктів із властивостями об'єкти, що володіють двома властивостями та віднімаються двічі, і тому потрібно додати , де - попарні сполучення елементів з Н. Але при цьому двічі враховуються об'єкти, що володіють трьома властивостями і, отже, їх необхідно виключити, тобто відняти суму всіх , де - сполучення з властивостей по три. Цей процес включення і вилучення продовжується до останнього члена , що визначає число об'єктів із усіма n властивостями, знак якого залежить від парності n. Наведена формула відома під назвами символічний метод, принцип перехресної класифікації, метод решета та формула обертання.
Таким чином, у цьому розділі наведені основні відомості з комбінаторики, які згодом ми будемо неодноразово згадувати і икористовувати при викладі методів синтезу автоматів та структур та інших розділів дискретного аналізу.
5. Основи теорії графів
Графічне подання рішення різних прикладних задач нам добре відомо. До графічних подань у широкому змісті можуть бути віднесені малюнки, креслення, графіки, діаграми, блок-схеми і т.п. З їхньою допомогою наочно ілюструються залежності процесів і явищ, логічні, структурні, причинно-наслідкові і інші взаємозв'язки. Однак теорія графів має свою власну проблематику.
У дискретній математиці граф є найважливішим математичним поняттям. На основі теорії графів будуються моделі різноманітних задач, таких як маршрутизації, розподілу ресурсів, дискретної оптимізації, сіткового планування і керування, аналізу і проектування організаційних структур, аналізу процесу їх функціонування і багато іншого.
5.1 Основні визначення
Визначення. Графом називається сукупність двох множин точок і ліній, між якими визначене відношення інцидентності, причому, кожен елемент інцидентний рівно двом елементам .
Елементи множини називаються вершинами, а елементи множини _ ребрами графа.
Вершини і ребра графа називаються його елементами, тому найчастіше пишуть і .
Визначення. Якщо ребро з'єднує вершини , тоді вони є для нього кінцевими точками і називаються суміжними вершинами. Два ребра називаються суміжними, якщо вони інцидентні до загальної вершини.
Необхідно відзначити, що при зображенні графа не всі деталі рисунка мають значення. Так, наприклад, несуттєвою є довжина і кривизна ребер, взаємне розташування вершин на площині. Принциповим є тільки відношення інцидентності.
У деяких задачах інцидентні ребру вершини нерівноправні, а розглядаються в певному порядку. Тоді кожному ребру можна приписати напрямок від першої інцидентної вершини до другої.
Приклад. Моделі, зображені на рис. 5.1 а, б, в, з погляду теорії графів однакові.
Рисунок 5.1 - Графи
Визначення. Напрямлені ребра називають орієнтованими ребрами або дугами, перша по черзі вершина називається початком дуги, а друга - її кінцем. Граф, що містить напрямлені ребра, називається орієнтованим графом або орграфом (рис. 5.2, а), а граф, що не містить напрямлених ребер - неорієнтованим або н-графом (рис. 5.2, б).
Рисунок 5.2 - Орієнтований та неорієнтований граф
Визначення. Ребро, що з'єднує деяку вершину саму із собою, називається петлею (рис. 5.3,а).
Визначення. Ребра, інцидентні до однієї і тієї ж вершини, називаються кратними (рис. 5.3,б). Граф, що містить кратні ребра, називається мультиграфом, а граф, що містить кратні ребра і петлі - псевдографом.
Визначення. Граф називається кінцевим, якщо множина його вершин і ребер звичайна.
Множина ребер графа може бути порожньою (рис. 5.3,в). Такий граф називається порожнім або пустим.
Рисунок 5.3 - Види графів
Визначення. Граф без петель і кратних ребер називається повним, якщо кожна пара його вершин з'єднана ребром. Повний граф з вершинами позначається .
Приклад. На рис. 5.4 зображені повні графи , , , і відповідно:
Рисунок 5.4 - Повні графи
Визначення. Доповненням графа називається граф , що має ті ж вершини, що і граф і тільки ті ребра, які необхідно додати до графа , щоб він став повним.
Приклад. Доповненням графа , зображеного на рис. 5.5,а є граф , зображений на рис. 5.5,б. Для порівняння, повний граф зображений на рис. 5.5,в.
Рисунок 5.5 - Види графів
Визначення. Степенем вершини називається кількість ребер, інцидентних цій вершині. Вершина степеня 0 називається ізольованою. У графі з петлями петля дає внесок в 2 одиниці у степінь вершини.
Теорема 1. Сума степеней вершин графа завжди парна: , де _ кількість ребер графа.
Доведення: Тому що кожне ребро графа має два кінці, степінь кожного кінця збільшується на 1 за рахунок одного ребра. Тобто у суму степеней всіх вершин кожне ребро вносить 2 одиниці. Отже, сума ступеней вершин повинна у два рази перевищувати число ребер, тобто бути парною.
Теорема 2. У будь-якому графі кількість вершин непарного степеня парна.
Доведення: Доведемо від оберненого. Припустимо, є непарне число вершин непарного степеня. Сума вершин парного степеня - парна. Сума степенів всіх вершин графа є сума вершин непарного і парного степенів. Така сума завжди є число непарне. Тобто сума степенів всіх вершин графа буде непарною. Це суперечить умові теореми 6.1. Прийшли до протиріччя. Отже, кількість вершин непарного степеня в будь-якому графі парна.
Справедливість теорем 1 і 2 можна проілюструвати на наступному прикладі.
Приклад. Визначити степені вершин графа, зображеного на наступному рисунку.
Розв'язання: ; ; ; ; ; .
.
У розглянутому графі дев'ять ребер, а вершин непарного степеня дві: ; .
Визначення. Для орієнтованого графа визначаються дві степені вершин: _ кількість ребер, що виходять із вершини і _ кількість ребер, що входять у вершину . Петля дає внесок по одиниці в обидві степені.
В орграфі суми степенів всіх вершин і рівні між собою і дорівнюють кількості ребер цього графа:
.
Приклад. Визначити степені вершин орграфа, зображеного на наступному рисунку.
Розв'язання:
, ; ; ; ;
, ; ; ; ;
.
Визначення. Граф називається підграфом графа , якщо кожна вершина і кожне ребро графа є відповідно вершиною і ребром графа .
Визначення. Граф називається остов (каркас) графа , якщо містить всі його вершини. За визначенням він також є підграфом графа .
Приклад. На рис. 5.6(а,б,в) зображені підграфи графа, зображеного на рис. 5.6,г. Причому підграф (рис. 5.6,б) є його каркас.
Рисунок 5.6 - Підграфи графа
Один і той же граф можна зображувати по-різному. Різним образом можна розташовувати вершини на площині і ребра можна зображувати не тільки відрізками прямих (різної довжини) але і дугами. Тому порівнюючи графи, будемо спиратися на наступні визначення.
Визначення. Графи і рівні, якщо множини їхніх вершин і ребер, визначених через пари інцидентних їм вершин, збігаються. Наприклад, графи, зображені на рис. 6.1 рівні.
Задати граф - означає описати множини його вершин і ребер, а також відношення інцидентності. Коли граф _ кінцевий, для його опису досить занумерувати вершини і ребра.
Визначення. Граф називається повністю заданим у точному значенні, якщо нумерація його вершин і ребер зафіксована. Графи, що відрізняються тільки нумерацією, називаються ізоморфними.
Приведемо ще одне визначення ізоморфних графів.
Визначення. Графи і ізоморфні якщо їхні вершини можна пронумерувати таким чином, що ребро тоді і тільки тоді з'єднує вершини і у графі , коли ребро з'єднує вершини і у графі .
Приклад. Графи, зображені на рис. 5.7, (а), (б) _ ізоморфні.
Рисунок 5.7 - ізоморфні графи
Приклад. На рис. 5.8 зображені графи _ з п'ятьма вершинами в кожному. Порівняти графи.
Рисунок 5.8 - Порівняння графів
Розв'язання:
Графи _ _ неорієнтовані графи, а _ _ орієнтовані.
Графи і _ повні, причому = .
Граф не є повним, тому що незважаючи на то, що кожна пара вершин з'єднана ребром, є петля.
Графи і є мультиграфами, тому що містять кратні ребра.
Граф _ має порожню множину ребер, всі вершини графа є ізольованими.
Графи і є доповненням друг до друга.
Графи і не є рівними, тому що ребра 5 мають різний напрямок.
Граф _ орієнтований мультиграф, тому що має кратні ребра, у той час як граф не є мультиграфом, тому що ребра 8 і 9 по-різному орієнтовані.
5.2 Способи завдання графів
Як було сказано в п. 6.1 для завдання графа необхідно занумерувати вершини і ребра, а також задати відношення інцидентності. Відношення інцидентності будемо описувати трьома способами: матрицею інцидентності, матрицею суміжності, списком ребер графа. Опишемо докладно кожний з перерахованих способів.
Матриця інцидентності - це матриця розміром , де вертикально вказуються вершини , а горизонтально - ребра . На перетині -того і -того рядків число дорівнює:
а) у випадку неорієнтованого графа
б) у випадку орієнтованого графа
Матриця суміжності _ це квадратна матриця розміром , де вертикально і горизонтально вказуються вершини графа і . На перетинанні -того і -того рядків число дорівнює:
_ числу ребер, що з'єднують ці вершини у випадку неорієнтованого графа;
_ числу ребер з початком в -тій вершині і кінцем в -тій вершині у випадку орієнтованого графа.
Список ребер графа - це таблиця, що складається із трьох рядків. У першому перераховані всі ребра; у другому і третьому - інцидентні їм вершини:
_ у випадку неорієнтованого графа порядок вершин у рядку довільний;
_ у випадку орієнтованого графа першою записується вершина, де починається ребро (другий рядок); вершина, де закінчується ребро, записується у третій рядок.
Для нумерації вершин і ребер графа використовують різний символьний запис: римські, арабські цифри, латинські букви.
Якщо графи рівні, то їх матриці суміжності і інцидентності, а також список ребер, однакові.
Приклад.
Задати матрицями інцидентності і суміжності, а також списком ребер, неорієнтований граф, зображений на наступному рисунку.
Розв'язання:
Тут .
Список ребер
|
Ребро |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||
|
Вершини |
початок |
a |
b |
a |
c |
c |
d |
c |
d |
e |
e |
|
|
кінець |
b |
c |
c |
d |
d |
d |
e |
e |
f |
g |
Як бачимо, у кожному стовпці матриці інцидентності є тільки два елементи, відмінних від нуля (або один, якщо ребро - петля).
Матриця суміжності симетрична щодо головної діагоналі.
Список ребер є найбільш компактним способом завдання графів.
Кожний із наданих способів однозначно описує граф, зображений на рисунку.
Приклад. Задати матрицями інцидентності, суміжності, списком ребер орієнтований граф, зображений на наступному рисунку.
Розв'язання:
Список ребер
|
Ребро |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||
|
Вершини |
початок |
a |
a |
b |
b |
c |
c |
d |
f |
f |
f |
|
|
кінець |
a |
b |
a |
c |
d |
e |
e |
d |
e |
g |
Відмінність матриці інцидентності орієнтованого графа від неорієнтованого складається у вказівці початку і кінця ребер. Матриця суміжності губить свою симетричність. У списку ребер важливий порядок вказівки вершин, що з'єднують зазначеним ребром (від початку до кінця).
Як відзначалося вище, всі розглянуті способи завдання графів однозначно визначають граф. Виникає питання: чи можливо відновити граф по заданих матрицях інцидентності, суміжності або списку ребер? Очевидна позитивна відповідь.
По матриці інцидентності число ребер і вершин визначається з розмірності матриці: число ребер графа дорівнює числу стовпців , а число вершин _ числу рядків матриці.
По матриці суміжності число вершин визначається з розмірності матриці. Як було відзначено, матриця суміжності н-графа симетрична щодо головної діагоналі, і кількість ребер визначається верхнім правим трикутником матриці, розташованим над головною діагоналлю, включаючи останню. Тобто, число ребер н-графа дорівнює сумі елементів, розташованих на головній діагоналі і у верхньому правому трикутнику.
У матриці суміжності орграфа симетрія відсутня, а число ребер дорівнює сумі всіх елементів матриці суміжності.
Список ребер є скороченим варіантом матриці інцидентності. Кількість ребер очевидна, а кількість вершин дорівнює максимальному номеру всіх перерахованих вершин зі списку.
Тобто, матриця інцидентності і список ребер по суті, еквівалентні, то знаючи матрицю інцидентності можна записати список ребер, і навпаки.
Побудова матриці інцидентності за списком ребер. Кожен рядок списку ребер відповідає рядку в матриці инцидентности з тим же номером.
Для неорієнтованого графа в кожному рядку списку ребер зазначені номери елементів матриці инцидентности, рівні 1 (всі інші елементи - нулі).
Для орієнтованого графа першою вказується вершина, що відповідає початку ребра (у матриці инцидентности - елемент ), а другий - відповідному кінцю ребра (у матриці инцидентности - елемент 1).
При збігу елементів у рядку списку ребер, у відповідному рядку матриці инцидентности записується число, відмінне від , 0, 1, наприклад, 2. Така ситуація відповідає наявності у графі петель.
Приклад. Побудувати матрицю інцидентності неорієнтованого графа за списком ребер:
|
Ребро |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
|
Вершини |
початок |
a |
d |
e |
c |
a |
d |
b |
f |
|
|
кінець |
d |
f |
f |
e |
b |
c |
f |
f |
Розв'язання.
Матриця інцидентності, відповідно до списку ребер, має вигляд:
Приклад.
Запиcати список ребер відповідно до матриці інцидентності орієнтованого графа:
Подобные документы
Поняття множини. Операції над множинами. Об’єднання і переріз двох множин. Різниця і доповненя множин. Множини з відношеннями. Прямий (декартів) добуток множин. Бінарні відношення. Відношення еквівалентності. Відношення порядку. Предикати.
курсовая работа [239,3 K], добавлен 10.06.2007Означення теорії множин. Дії над множинами. Алгебра множин. Вектори і прямий добуток множин. Властивості відношень. Способи задання функції. Сукупність підстановок множини. Алгебраїчні операції та системи. Властивості рефлексивності та симетричності.
конспект урока [263,1 K], добавлен 28.06.2012Поняття про бінарні відношення, способи їх задання, існуючі операції, характерні властивості. Відношення еквівалентності, порядку, домінування й переваги. Поняття та значення R-оптимальності, найкращого, найгіршого, максимального й мінімального елементів.
реферат [1,3 M], добавлен 04.10.2015Теорія множин як абстрактно-теоретична наука про множини довільної природи, розгляд головних проблем. Загальна характеристика теореми Кантора-Берштейна. Знайомство з властивостями множин потужності континууму. Аналіз діяльності математика К. Геделя.
курсовая работа [325,6 K], добавлен 27.04.2016Основні засади комбінаторики та теорії множин на основі аксіоматики Цермело-Френкеля і використання правила суми й добутку. Знаходження кусково-постійних конфігурацій множин засобами мови програмування IDE C++ Builder з допомогою вбудованого GUI.
контрольная работа [539,5 K], добавлен 27.11.2010Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
задача [112,0 K], добавлен 23.06.2010Визначення та властивості упорядкованих множин, приклади діаграм. Дистрибутивні ґрати як один з основних алгебраїчних об'єктів. Поняття нижньої і точної грані, їх властивості та приклади, доказ лем. Застосування та суть топологічних стоунових просторів.
курсовая работа [288,0 K], добавлен 24.03.2011Виключення третього як фундаментальний принцип логіки, істинність і хибність як логічні значення пропозиції. Таблиці істинності, поняття тавтології і еквівалентності. Властивості функцій множин і запереченням гіпотези Гольдбаха в термінах квантифікаторів.
реферат [82,7 K], добавлен 03.03.2011Поняття сукупності предметів, об'єднаних за певною характеристичною ознакою. Основні загальноприйняті множини (геометрична фігура, ГМТ, область визначення та значень функції). Позначення множин, їх елементи, належність об'єктів та способи задання.
презентация [517,1 K], добавлен 19.01.2011Визначення метричного простору. Границя функції у точці. Властивості границь дійсних функцій. Властивості компактних множин. Розв’язок системи лiнiйних рівнянь. Теорема про існування i єдність розв’язку диференціального рівняння. Нумерація формул.
методичка [461,1 K], добавлен 25.04.2014
