Дискретна математика для програмістів

Зміст

1. Основи теорії множин

.1 Коротка історична довідка

.2 Поняття множини

.3 Способи опису множин

.4 Операції над множинами

.4.1 Діаграми Ейлера-Венна

.4.2 Деякі операції над множинами

.5 Властивості операцій над множинами

.6 Доведення тотожностей

.7 Парадокси теорії множин

. Основи теорії відношень

.1 Декартовий добуток

.2 Поняття відношень. Завдання відношення

.3 Властивості бінарних відношень

.4 Відношення еквівалентності

.4.1 Фактор-множина

.4.2 Рівнопотужні множини

.4.3 Зчисленні множини

.4.4 Потужність континууму

.5 Операції над бінарними відношеннями

.5.1 Правила побудови матриць відношень

.6 Відображення

.6.1 Визначення і приклади

.6.2 Деякі часткові випадки

.6.3 Інєктивні, сюрєктивні та бієктивні відображення

.6.4 Композиція відображень

.7 Функції

. Алгебраїчні системи

.1 Поняття бінарної алгебраїчної операції

.2 Властивості бінарних алгебраїчних операцій

.3 Обернені бінарні операції

.4 Елементи, виділені відносно бінарної операції

.5 Поняття алгебраїчної структури

.6 Основні типи алгебраїчних структур

.7 Ізоморфізми та гомоморфізми алгебраїчних структур

.8 Булеві алгебри

. Комбінаторний аналіз

.1 Правило добутку

.2 Правило суми

.3 Розміщення

.3.1 Розміщення з повтореннями

.3.2 Розміщення без повторень

.4 Перестановки

.5 Сполучення (комбінації)

.6 Формула включень і вилучень

. Основи теорії графів

.1 Основні визначення

.2 Способи завдання графів

.3 Звязність графа. Маршрути, шляхи, ланцюги, цикли

.3.1 G - неорієнтований граф

.3.2 G - орієнтований граф

.4 Метрика на графах

.5 Ейлерів цикл. Ейлерів граф

.6 Шляхи і цикли Гамільтона

.7 Планарні графи

.8 Розфарбування графів

.9 Дерева і ліс

.10 Алгоритми пошуку найкоротших шляхів

.10.1 Алгоритм пошуку у глибину

.10.2 Алгоритм пошуку завширшки

.10.3 Алгоритм Дейкстри

.10.4 Алгоритм Флойда

Література

множина декартовий бінарний алгебраїчний

1. Основи теорії множин

Дискретна математика є розділом математики, що зародилася в давні часи. Її головною відмінністю є дискретність, тобто антипод неперервності. Дискретна математика включає традиційні розділи математики, які вже сформувалися (математичну логіку, алгебру, теорію чисел), і нові, що інтенсивно розвиваються.

У більш як двотисячорічній історії дискретної математики сучасний період є одним із найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера застосування, інтенсивно зростають обсяги нової інформації та кількість нових результатів. Якщо ще порівняно недавно ця наука була сферою інтересів лише вузького кола фахівців, то тепер вона перетворюється на наукову дисципліну, дуже важливу й потрібну для багатьох, а у сфері сучасної освіти - для всіх.

Масове використання обчислювальної техніки та інформаційних технологій значно розширює сферу прикладних досліджень, у яких все більше застосовується апарат дискретної математики.

Базовим розділом як дискретної математики, так і взагалі всієї математики, є теорія множин.

1.1 Коротка історична довідка

Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин.

Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей: так званих парадоксів або антиномій теорії множин. Виникла кризова ситуація. Одна частина математиків, посилаючись на штучність сформульованих антиномій, вважала за краще не помічати ці суперечності або не надавати їм великого значення. У той час як інша (скажімо, відповідальніша) група математиків зосередила свої зусилля на пошуках більш обгрунтованих та точних принципів і концепцій, на яких могла б бути побудована несуперечлива теорія множин.

У результаті було запропоновано кілька формальних (або аксіоматичних) систем, які служать фундаментом сучасної теорії множин, а значить, фундаментом всієї класичної математики. Важливість цих досліджень серед іншого підкреслює той факт, що значний внесок у становлення аксіоматичної теорії множин зробили такі видатні математики і мислителі XX століття, як Б. Рассел, Д. Гільберт, К. Гедель та ін.

Сьогодні теорія множин - це математична теорія, на якій грунтується більшість розділів сучасної математики, як неперервної, так і дискретної.

1.2 Поняття множини

Для наших цілей достатньо буде викладення основ так званої інтуїтивної або наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г. Кантора.

В інтуїтивній теорії множин поняття "множина" належить до первинних невизначальних понять, тобто воно не може бути означено через інші більш прості терміни або обєкти, а пояснюється на прикладах, апелюючи до нашої уяви та інтуіції. Такими поняттями в математиці є також поняття "число", "пряма", "точка", "площина" тощо.

Канторівський вираз: "Множина - це зібрання в єдине ціле визначених обєктів, які чітко розрізняються нашою інтуіцією або нашою думкою" - безумовно не може вважатися строгим математичним означенням, а є скоріше поясненням поняття множини, яке заміняє термін "множина" на термін "зібрання". Іншими синонімами основного слова "множина" є "сукупність", "набір", "колекція", "обєднання" тощо.

Прикладами множин можуть служити: множина десяткових цифр, множина літер українського алфавіту, множина мешканців Одеси, множина парних чисел, множина розвязків деякого рівняння та ін.

Визначення. Множиною називається сукупність визначених об'єктів, різних між собою, обєднаних за певною ознакою чи властивістю.

На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад, N - множина натуральних чисел, Z - множина цілих чисел, Q - множина раціональних чисел, R - множина дійсних чисел, C - множина комплексних чисел тощо.

Визначення. Якщо один з об'єктів множини , то говорять, що - елемент множини , або належить .

Елементи множин позначатимемо малими літерами латинського алфавіту. Той факт, що обєкт a є елементом множини M записується так: aÎM (читається: "a належить M" або "a є елемент M"). Для того, щоб підкреслити, що деякий елемент a не належить множині M, вживають позначення aÏM.

Запис a, b, c,...ÎM використовують для скорочення запису aÎM, bÎM, cÎM,....

1.3 Способи опису множин

Множини можуть задаватися наступними способами:

) Перерахуванням, тобто списком всіх своїх елементів. Такий спосіб завдання прийнятний тільки при завданні кінцевих множин. Позначення списку - у фігурних дужках. Порядок запису елементів множини при цьому позначенні є неістотним.

Наприклад, множина, що складається з перших п'яти простих чисел . Множина спортсменів університетської хокейної команди:

.

Слід пікреслити, що однією з основних ідей канторівської теорії множин був розгляд множини як нового самостійного обєкта математичного дослідження. Тому необхідно розрізняти такі два різні обєкти, як елемент a і множина {a}, яка складається з єдиного елемента a. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих невпорядкованих пар з елементів a, b і c (елементи в парі не співпадають) D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно.

2) Процедурою, що породжує і описує спосіб одержання елементів множини із уже отриманих елементів або з інших об'єктів. Цей спосіб задання множин грунтується на зазначенні загальної властивості або породжувальної процедури для всіх обєктів, що утворюють описувану множину.

У загальному випадку задання множини M має вигляд: M = {a | F(a)}.

Цей вираз читається так: "множина M - це множина всіх таких елементів a, для яких виконується властивість F", де через F(a) позначено властивість, яку мають елементи множини M і тільки вони.

Приклад.

S = { n | n - непарне число } або S = { n | n = 2k+1, kÎZ },= { x | x = pk, kÎZ },= { fi | fi+2 = fi+1 + fi, iÎN, f1 = f2 = 1 }.

Другий спосіб є більш загальним способом задання множин. Наприклад, введену вище множину D всіх невпорядкованих пар з елементів a, b і c можна задати так:

= { {x,y} | xÎ{a,b,c}, yÎ{a,b,c} і x ¹ y}.

Варто зазначити, що другий метод природним чином можна назвати методом породження чи конструктивним методом, що, по суті, починаючи з невеликих множин, які можна задати, наприклад, перерахуванням, шляхом виконання дозволених перетворень приводить до задання нової множини, що додається до попередньої множини і т.д.

Якщо припустити, що існує кілька множин опису алгоритмів, а в дійсності ситуація виглядає саме так, то повинна бути множина модифікацій для цього способу задання множин.

) Описом характеристичних властивостей, якими повинні володіти елементи множини. Так, множину , що складається з таких елементів , які мають властивість , позначимо в такий спосіб:

.

Так, розглянута вище множина всіх цілих чисел, що є степенями числа 2 може бути записана як . До А ще треба додати 1.

Третій спосіб задання множин дуже важливий, тому що дозволяє пов'язати поняття "властивість" і "множина" і тим самим за допомогою останнього формалізувати перше для комп'ютера. Наприклад, властивість предмета мати червоний колір для комп'ютера можна задати включенням предмета в певну множину, з елементами якої зв'язуються всі наслідки того, що вони мають червоний колір.

Далі будемо вважати, що кожна розумна властивість визначає деяку множину X елементів, що мають цю властивість, і, навпаки, будь-якій множині відповідає властивість її елементів бути елементами цієї множини.

Варто зазначити, що співвідношення "властивість" і "множина" може породити серйозні проблеми, пов'язані з тим, що можливе існування властивостей, які визначають множини, що, можливо, не існують. У всякому разі, для логіки прийняте співвідношення властивість - множина є найважливішим положенням.

Надалі будемо використовувати такі загальноприйняті позначення для числових множин, з якими часто зустрічаємось:={1,2,3,…} - множина натуральних чисел;={…,-2,-1,0,1,2,…} - множина цілих чисел;- множина раціональних чисел;- множина дійсних чисел;- множина комплексних чисел.

Визначення. Множина називається підмножиною (або включенням) множини , якщо кожен елемент множини є елементом множини , тобто, якщо , то .

Якщо і , то називається строгою підмножиною і позначається .

Визначення. Дві множини рівні , якщо всі їхні елементи збігаються. Множини і рівні, якщо і .

Множина, яка містить скінченну кількість елементів, називається скінченною, у протилежному випадку - нескінченною. Кількість елементів у скінченій множині називається потужністю множини і позначається .

Визначення. Множина, що не містить елементів, називається порожньою множиною, і позначається . Порожня множина є підмножиною будь-якої множини.

Приклад.

S = {x | x - непарне число, що ділиться на 2} = Æ;= {x | x Î R, x2 + 1 = 0} = Æ.

Це поняття відіграє дуже важливу роль при заданні множин за допомогою опису. Так, без поняття порожньої множини не можна говорити про множину відмінників студентської групи або про множину дійсних коренів квадратного рівняння, не пересвідчившись заздалегідь, чи є в студентській групі відмінники або чи має задане рівняння дійсні корені. Поняття порожньої множини дає змогу оперувати множиною відмінників групи, не турбуючись про те, чи є відмінники в групі, яка розглядається. Порожню множину умовно відносять до скінченних множин. Число елементів у ній рівне 0.

Таким чином, уведення порожньої множини дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні.

Визначення. Універсальна множина - це множина, що володіє такою властивістю, що всі розглянуті множини є її підмножинами.

Варто розрізняти поняття належності елементів множини і включення! Так, наприклад, якщо множина , то , , але , у той час як .

Приклад. Які з наведених визначень множин є коректними:

а) , б) , в) , г)?

Чи належить число 6 множині ?

Розвязання:

а) визначення множини перерахуванням елементів коректно.

б) відповідно до визначення множин, елементи її повинні бути різні, тому при перерахуванні елементів множини не слід указувати той самий елемент кілька разів. Коректне визначення множини виглядає в такий спосіб: .

в) визначення множини описом характеристичної властивості коректно.

г) визначення списком множини коректно: елементами множини є множини і , . Однак , тому що даний елемент не перерахований у списку.

Визначення. Множина всіх підмножин, що складаються з елементів множини , називається булеаном .

Приклад. Нехай . Визначити булеан множини . Яка потужність множини ?

Розвязання:

.

Потужність .

1.4 Операції над множинами

Якщо припустити, що існує кілька множин опису алгоритмів, а в дійсності ситуація виглядає саме так, то повинна бути множина модифікацій для цього способу задання множин.

У природі, суспільстві, навколишній реальності різні об'єкти формують множини різної природи, поєднуючись в різні ситуації. Більш того, у процесі проектування представлення про цільову ситуацію намагаються створити з наявних ситуацій, узагалі дослідник намагається виділяти подібні один одному сполучення об'єктів і встановити закономірності їхнього формування.

На цій основі вводиться поняття "операція над множинами", що фактично дозволяє реалізувати формальним чином породження різних ситуацій сполучень елементів.

1.4.1 Діаграми Ейлера-Венна

Для графічної ілюстрації відносин між множинами даної універсальної множини використовують діаграми Ейлера-Венна.

Діаграма Венна - діаграма, що показує всі можливі логічні відношення для скінченного набору множин.

Діаграми Венна придумані приблизно в 1880 Джоном Венном. Використовуються для вивчення елементарної теорії множин, та ілюстрування простих співвідношень в теорії ймовірностей, логіці, статистиці, мовознавстві та інформатиці.

Окрім діаграм Венна, для зображення множин використовують також кола Ейлера. Кола Ейлера використовуються для зображення всіх можливих відношень між різними множинами, в тому числі і таких коли одна множина містить іншу або взагалі відсутні перетини множин. Діаграма Венна зображує, всі можливі перетини множин. Всього таких перетинів буде , де n - кількість множин.

Будь-яку множину розглядатимемо у звязку з універсумом, який на діаграмах Ейлера-Венна асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини (рис. 1.1).

Рисунок 1.1 - Діаграма Венна, що показує всі перетини грецького, російського і латинського алфавітів

1.4.2 Деякі операції над множинами

Розглянемо дві множини А і В та введемо операції над ними. Для графічної ілюстрації будемо використовувати діаграми (кола) Ейлера-Венна.

Визначення. Об'єднанням множин і називається множина, що складається із всіх тих елементів, які належать хоча б однієї з множин або . Об'єднання множин і позначається . Це визначення рівносильне наступному:

.

Рисунок 1.2 - Об'єднання множин і ()

Приклад. Нехай , . Знайти .

Розвязання: .

Визначення. Перетином множин і називається множина, що складається із всіх тих елементів, які належать і множині і множині . Перетин множин і позначається . Це визначення рівносильне наступному: .

Рисунок 1.3 - Перетин множин і ()

Приклад. Нехай , . Знайти .

Розвязання: .

Визначення. Доповненням (або абсолютним доповненням) множини називається множина, що складається із всіх елементів універсальної множини, які не належать . Доповнення множини позначається . Це визначення рівносильне наступному:

.

Рисунок 1.4 - Доповнення множини ()

Визначення. Різницею множин і (або відносним доповненням) називається множина, що складається із всіх елементів множини , які не втримуються в . Різницю множин і позначають . Це визначення рівносильне наступному:

А \ В = {x | x Î А і x Ï В}.

Рисунок 1.5 - Різниця множин і ()

Приклад. Нехай , . Знайти А \ В.

Розвязання:

А \ В={5,6}.

Визначення. Симетричною різницею множин і називається множина, що складається з об'єднання всіх елементів, що належать множині і не містяться в , і елементів, що належать множині і не містяться в . Симетрична різниця множин і позначається А Å В. Це визначення рівносильне наступному:

А Å В = {x | (x Î А і x Ï В) або (x Î В і x Ï А)}, тобто .

Рисунок 1.6 - Симетрична різниця множин і (А Å В )

Визначення. Операції, які виконують над однією множиною, називають унарними. Операції, які виконують над двома множинами, називають бінарними. Прикладом унарної операції є знаходження доповнення. Прикладами бінарних операцій є об'єднання, перетинання, різниця, симетрична різниця.

Приклад. Нехай , . Знайти .

Розвязання:

.

Приклад. Нехай , ; . Знайти , , , , .

Розвязання: Зобразимо задані множини на числовій осі

Тоді шукані множини будуть мати наступний вигляд:

1.5 Властивості операцій над множинами

Операції над множинами, як і операції над числами, мають деякі властивості (табл.1). Останні виражаються сукупністю тотожностей незалежно від конкретних множин, що входять у ці тотожності та є підмножинами деякого універсуму U.

Таблиця 1. Властивості операцій над множинами

Комутативність1а) А È В = В È А1б) А Ç В = В Ç ААсоціативність2а) А È (В È С) = (А È В) È С2б) А Ç (В Ç С) = (А Ç В) Ç СДистрибутивність3а) А È (В Ç С) = (А È В) Ç (А È С)3б) А Ç (В È С) = (А Ç В) È (А Ç С)Властивості порожньої множини Æ та універсуму U4а) А È Æ = A4б) А Ç U = A5а) 5б) 6а) А È U = U6б) А Ç Æ = Æ7а) 7б) Самопоглинання (закон ідемпотентності)8а) А È A = A8б) А Ç A = AПоглинання9а) А È (А Ç В) = А9б) А Ç (А È В) = АЗакони де Моргана10а) 10б) Властивості доповнення, різниці, дизюнктивної суми11)12)13)14) А Å В = В Å А15) А Å (В Å С) = (А Å В) Å С16) А Å Æ = Æ Å A = A

Пріоритет операцій: 1. ; 2. ; 3. ; 4. ; 5. .

Взагалі поняття "операція " дуже важливе і його широко застосовують у різних галузях математики для конструювання одних об'єктів з інших, для визначення нових математичних об'єктів тощо. Зокрема, використовуючи представлення про операції об'єднання і перетину множин, вводять поняття розбиття.

Визначення. Сукупність підмножин A1, A2, …, An множини A називається розбиттям П множини A, якщо:

. ;

. Ai Ç Aj = Æ, i, j=1,.., n, i ¹ j.

Приклад. Нехай А={r1, r2,…,r6}. Розглянемо такі множини підмножин:

П1 = {{r1}, {r2}, {r3, r4}, {r5, r6}};

П2 = {{r1, r2}, {r3, r4, r5, r6}};

П3 = {{r1, r2, r3, r4, r5, r6}};

П4 = {{r1, r2, r3, r4}, {r4, r5, r6}};

П5 = {{r1, r2},{r3, r4, r6}}.

Тут множини підмножин П1, П2, П3 - розбиття, а множина підмножин П4 не є розбиттям, тому що не виконується умова 2). Множина підмножин П5 не є розбиттям, тому що не виконується умова 1).

Розбиття часто використовується при постановках задач керування. Наприклад, якщо R - множина лекцій, що повинні бути проведені k лекторами, причому кожна лекція проводиться одним лектором, то тоді закріплення лекцій - розбиття, що включає k підмножин лекцій. Умова 1) гарантує, що всі лекції будуть проведені, а умова 2) забезпечує закріплення кожної лекції за одним лектором.

1.6 Доведення тотожностей

Основний метод доведення тотожностей в алгебрі множин ґрунтується на згаданому раніше факті: А = В тоді і тільки тоді, коли А Í В і В Í А. Доведемо, наприклад, тотожність 3а) А È (В Ç С) = (А È В) Ç (А È С).

Доведемо спочатку, що А È (В Ç С) Ì (А È В) Ç (А È С). Для цього візьмемо будь-яке x Î А È (В Ç С), тоді за означенням операцій È та Ç маємо x Î А або (x Î В і x Î С). За законом дистрибутивності "або" відносно "і" (x Î А або x Î В) і (x Î А або x Î С), тобто x Î А È В і x Î А È С. Це рівносильно x Î ( А È В) Ç (А È С), що й треба було довести.

Доведемо тепер, що (А È В) Ç (А È С) Ì А È (В Ç С). Для цього візьмемо будь-яке x Î (А È В) Ç (А È С). Звідси (x Î А або x Î В) і (x Î А або x Î С). Це рівносильно x Î А або (x Î В і x Î С), тобто x Î А È (В Ç С), що й потрібно було довести.

Таким чином, А È (В Ç С) = (А È В) Ç (А È С).

Із властивості асоціативності операції обєднання множин випливає, що обєднання кількох множин можна виконати, послідовно обєднуючи їх, причому порядок входження множин не впливає на результат: А È (В È С) = (А È В) È С = А È В È С. Отже, обєднання сукупності множин можна подати співвідношенням: . Аналогічно на n множин узагальнюється операція перетину: .

Використовуючи узагальнення операцій обєднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад закон де Моргана, який в узагальненому вигляді записується так: і .

Приклад. Показати, що .

Розвязання. Доведемо цю властивість асоціативності, скориставшись діаграмами Венна:

Як бачимо , що й треба було довести.

.7 Парадокси теорії множин

Слово "парадокс" грецького походження і перекладається українською мовою - несподіваний, дивний. Вживають це слово у відношенні до висловлювання (положення, ідеї), яке суттєво різниться від загальноприйнятого традиційного уявлення з даного приводу. Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені різними математиками в теорії множин Г.Кантора, є наївною спробою зменшити їхнє значення і надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Більш точно суть явища передає назва, "антиномії теорії множин", оскільки термін антиномія є синонімом терміна суперечність. Але за традицією, будемо називати сформульовані нижче положення парадоксами.

Парадокс Б.Рассела. Для будь-якої множини M коректним є питання: чи множина M належить собі як окремий елемент, тобто чи є множина M елементом самої себе, чи ні? Наприклад, множина всіх множин є множиною і тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.

Отже коректно поставити сформульоване питання і щодо множини всіх множин, які не будуть власними елементами. Нехай M - множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а сама множина M є елементом самої себе чи ні? Якщо припустити, що MÎM, то з означення множини M випливає MÏM. Якщо ж припустимо, що MÏM, то з того ж таки означення дістанемо MÎM.

Близьким до парадокса Рассела є так званий "парадокс цирульника": цирульник - це мешканець міста, який голить тих і тільки тих мешканців міста, які не голять самі себе. Проводячи міркування, аналогічні тим, що були зроблені в парадоксі Рассела, дійдемо висновку, що цирульник голить себе в тому і тільки в тому випадку, коли цирульник не голить сам себе.

Багато хто з математиків на початку ХХ ст. не надавали цим парадоксам особливого значення, оскільки в той час теорія множин була відносно новою галуззю математики і не зачіпала інтересів більшості математиків. Однак їхні більш відповідальні та проникливі колеги зрозуміли, що виявлені парадокси стосуються не тільки теорії множин і побудованих на ній розділів класичної математики, але мають безпосереднс відношення до логіки взагалі, тобто до головного інструменту математики.

Зокрема, парадокс Рассела може бути переформульований в термінах логіки і таким чином доданий до відомих з давніх часів логічних парадоксів (парадоксу брехуна, парадоксу всемогутньої істоти тощо).

Якщо проаналізувати всі парадокси теорії множин, то можна зробити висновок, що всі вони обумовлені необмеженим застосуванням так званого принципу абстракції (або принципу згортання), згідно з яким для будь-якої властивості P(x) існує відповідна множина елементів x, які мають властивість P(x). Якщо відкинути це припущення, то всі відомі парадокси теорії множин стають неможливими.

В усіх існуючих аксіоматичних теоріях множин неможливість антиномій ґрунтується на обмеженнях принципу згортання.

2. Основи теорії відношень

.1 Декартовий добуток

Визначення. Декартовим (прямим) добутком множин A і B (записується A´B) називається множина всіх пар (a,b), в яких перша компонента належить множині A (aÎA), а друга - множині B (bÎB).

Тобто A´B = {(a,b) | aÎA і bÎB }.

Декартовий добуток природно узагальнюється на випадок довільної скінченної сукупності множин. Якщо A1, A2,..., An - множини, то їхнім декартовим добутком називається множина D = {(a1,a2,...,an) | a1ÎA1, a2ÎA2,..., anÎAn }, яка складається з усіх наборів (a1,a2,...,an), в кожному з яких i-й член, що називається i-ю координатою або i-ю компонентою набору, належить множині Ai, i=1,2,...,n. Декартовий добуток позначається через A1´ A2´...´ An.

Набір (a1,a2,...,an), щоб відрізнити його від множини, яка складається з елементів a1,a2,...,an, записують не у фігурних, а в круглих дужках і називають кортежем, вектором або впорядкованим набором. Довжиною кортежу називають кількість його координат. Два кортежі (a1,a2,...,an) і (b1,b2,...,bn) однакової довжини вважаються рівними тоді і тільки тоді, коли рівні їхні відповідні координати, тобто ai=bi, i=1,2,...,n. Отже, набори (a,b,c) і (a,c,b) вважаються різними, в той час як множини {a,b,c} і {a,c,b} - рівні між собою.

Декартовий добуток множини A на себе n разів, тобто множину A´A´...´A називають n-м декартовим (або прямим) степенем множини A і позначають An.

Прийнято вважати, що A0 = Æ (n=0) і A1 = A (n=1).

Наприклад, якщо A = {a,b} і B = {b,c,d}, то

A´B = {(a,b),(a,c),(a,d),(b,b),(b,c),(b,d)},= {(a,a),(a,b),(b,a),(b,b)}.

Якщо R - множина дійсних чисел або множина точок координатної прямої, то R2 - це множина пар (a,b), де a,bÎR, або множина точок координатної площини.

Зауважимо, що операція декартового добутку неасоціативна і некомутативна, тобто множини (A´B)´C і A´(B´C), а також множини A´B і B´A, взагалі кажучи, не рівні між собою.

Звязок декартового добутку з іншими операціями над множинами встановлюється такими тотожностями:

(A È B) ´ C = (A´C) È (B´C),

(AÇB) ´ C = (A´C)Ç(B´C),´ (B È C) =(A´B) È (A´C),´ (BÇC) =(A´B)Ç(A´C).

Координатне зображення точок площини вперше було запропоновано французьким математиком і філософом Рене Декартом, тому введена операція над множинами і називається декартовим добутком.

.2 Поняття відношень. Завдання відношення

Визначення. Упорядкована пара предметів - це сукупність, що складається із двох предметів, розташованих у деякому певному порядку. При цьому впорядкована пара має наступні властивості:

а) для будь-яких двох предметів і існує об'єкт, який можна позначити як , названий упорядкованою парою;

б) якщо і ? упорядковані пари, то тоді і тільки тоді, коли , .

При цьому будемо називати першою координатою, а - другою координатою впорядкованої пари .

Визначення. Бінарним (або двомісним) відношенням називається підмножина впорядкованих пар, тобто множина, кожен елемент якої є впорядкованою парою.

Якщо є деяке відношення, це записують як або .

Один з типів відношень ? це множина всіх таких пар , що є елемент деякої фіксованої множини , а ? елемент деякої фіксованої множини . Таке відношення називається прямим або декартовим добутком.

Визначення. Декартів добуток множин і є множина .

При цьому множина називається областю визначення відношення , а - його областю значень:

; (див. рис. 2.1).

Приклад. Знайти області визначення і значень відношення .

Розвязання: Область визначення заданого відношення , а область значень ? .

Рисунок 2.1 - Області визначення і значення відношення

Скориставшись визначенням декартового добутку, можемо дати ще одне визначення бінарного відношення:

Визначення. Бінарним відношенням називається підмножина пар прямого добутку , тобто .

Надалі ми будемо розглядати бінарні відношення, тому замість терміна "бінарне відношення" будемо вживати термін "відношення".

Розглянемо кілька прикладів відношень:

. Якщо ? множина дійсних чисел, тобто - бінарне відношення на . Графічно його зобразити можна в такий спосіб (рис. 2.2):

Рисунок 2.2 - Бінарне відношення

. Якщо ? множина натуральних чисел, то відношення виконується для пар , , , але не виконується для пар , , .

. Якщо ? множина студентів Університету, а ? множина груп Університету, то відношення множин і ? є множина ?.

. Якщо ? множина товарів у магазині, а ? множина дійсних додатних чисел, то відношення множин й ? є множина .

У силу визначення бінарних відношень, як спосіб їх задання можуть бути використані будь-які способи задання множин. Відносини, визначені на кінцевих множинах, звичайно задаються:

. Списком (перерахуванням) упорядкованих пар, для яких це відношення виконується.

. Матрицею - бінарному відношенню

,

де відповідає квадратна матриця порядку , кожен елемент якої дорівнює 1, якщо між й є відношення , і 0, у протилежному випадку, тобто:

Приклад. Нехай , . Знайти декартовий добуток множин й . Записати , , .

Розвязання:

;

;

;

;

.

Приклад. Нехай . Задати в явному вигляді (списком) і матрицею відношення , якщо відношення означає "бути строго більше".

Розвязання: Відношення містить всі впорядковані пари елементів з : .

Список відношення виглядає в такий спосіб:

Матриця відношення наведена на рис. 2.3:

Рисунок 2.3 - Матриця відношення

Приклад. Нехай . Задати в явному вигляді (списком) і матрицею відношення , якщо відношення означає:

а) "мати загальний дільник, відмінний від одиниці";

б) "їхня сума - число, кратне 3".

Розвязання: а) відношення може бути записане в такий спосіб

Список відношення :

.

Матриця відношення наведена на рис. 2.4 (а).

б) відношення може бути записане в такий спосіб

Список відношення :

.

Матриця відношення наведена на рис. 2.4 (б).

Рисунок 2.4 - Матриці відношень

Приклад. Для зазначених нижче відношень привести приклади пар, для яких виконуються відношення, і пара, для яких відношення не виконуються:

Відношення, задані на множині точок дійсної площини:

а) - "перебувати на однаковій відстані від початку координат";

б) - "перебувати на різній відстані від початку координат";

в) - "перебувати на одному і тому ж колі з центром у початку координат";

г) - "бути симетричним щодо осі ".

Розвязання:

За визначенням кола, відношення і виконуються для тих самих пар точок.

Відношення виконується тільки для тих пар точок, для яких не виконуються відношення і .

Відношення виконується для всіх пар точок і , які задовольняють умовам , .

2.3 Властивості бінарних відношень

Визначення. Відношення на називається рефлексивним, якщо має місце для кожного . Головна діагональ матриці такого відношення містить тільки одиниці.

Наприклад, відношення - рефлексивно. Відношення рефлексивно для всього вмісту пенала. Відношення на множині дійсних чисел рефлексивно.

Визначення. Відношення на називається антирефлексивним, якщо ні для якого не виконується , тобто із треба . Головна діагональ матриці такого відношення містить тільки нулі.

Наприклад, відношення , антирефлексивні. Відношення на множині дійсних чисел антирефлексивно.

Визначення. Відношення на називається симетричним, якщо для всіх з умови треба, що . Матриця симетричного відношення симетрична щодо головної діагоналі, тобто для всіх і .

Наприклад, відношення , - симетричні. Відношення на множині дійсних чисел симетрично.

Визначення. Відношення на називається антисиметричним, якщо для всіх , з умов і треба, що , тобто ні для яких елементів і , що розрізняються , не виконуються одночасно відношення і . У матриці антисиметричного відношення відсутні одиниці, симетричні щодо головної діагоналі.

Наприклад, відношення , - антисиметричні. Відношення на множині дійсних чисел антисиметричне. Дійсно, якщо й , то .

Визначення. Відношення на називається транзитивним, якщо для будь-яких з умов і прямує . У матриці такого відношення повинна виконуватися наступна умова: якщо в і-тому рядку і в j-тому стовпці стоїть одиниця, тобто , то всім одиницям в -тому рядку і -тому стовпці повинні відповідати одиниці в -тому рядку і у тих же -тих стовпцях, тобто (і, може бути, в інших стовпцях).

Наприклад, відношення , - транзитивні. Відносини , на множині дійсних чисел транзитивні.

Приклад. Нехай і відношення є множина . Які властивості має задане відношення?

Розвязання:

Побудуємо матрицю відношення:

Відношення рефлексивне, тому що для кожного , . Головна діагональ матриці відношення містить одиниці.

Відношення не є антирефлексивне, тому що з умови не треба , наприклад, , але .

Розглянувши всі можливі випадки методом безпосереднього перескладання (табл. 2.2а) можна показати, що відношення симетрично. Крім того, матриця відношення симетрична щодо головної діагоналі.

не є антисиметричне, тому що і , але .

Скориставшись методом безпосереднього перескладання можна також показати, що відношення транзитивне.

Приклад.

Які властивості мають відношення на множині натуральних чисел :

а) - "бути не менше";

б) - "бути рівним";

в) - "їхня сума - парне число".

Розвязання:

На множині натуральних чисел :

а)

рефлексивне, не антирефлексивне, тому що виконується для всіх . Наприклад, ;

не симетричне, тому що , але - невірно;

антисиметричне, тому що і виконуються тільки коли ;

транзитивне, тому що коли і , то . Наприклад, , і .

б)

рефлексивне, не антирефлексивне, тому що виконується для всіх . Наприклад, ;

симетричне, тому що коли , то і ;

антисиметричне, тому що коли і , то ;

транзитивне, тому що коли і , то і .

в)

рефлексивне, не антирефлексивне, тому що сума двох парних чисел і двох непарних чисел є число парне. Наприклад, - парне і - парне;

симетричне, не антисиметричне, тому що коли - парне, то і - теж парне (від переставлення доданків сума не міняється). Наприклад, - парне і - теж парне, - парне і - теж парне;

транзитивне, тому що якщо - парне, - парне, то і - теж парне. Наприклад, - парне і - парне, то і - теж парне.

2.4 Відношення еквівалентності

Визначення. Відношення R називається відношенням еквівалентності, якщо воно має такі властивості:

а) рефлективності: (x, х) Î R при будь-якому х Î Х;

б) симетричності: з (x1, х2) Î R випливає (x2, х1) Î R;

в) транзитивності: якщо (x1, х2) Î R і (x2, х3) Î R, то (x1, х3) Î R;

Замість того, щоб писати (x1, х2) Î R, часто пишуть x1 ~ x2 або x1 º x2(mod R) (читається так: x1 конгруентно x2 за модулем R) чи, простіше, (x1 ~ x2 або x1 º x2, якщо немає необхідності ще раз вказувати, що мова йде про одне й те саме відношення R).

Для x Î X позначимо через K(x) підмножину, що складається з елементів, еквівалентних x, тобто K(x) = {y | y Î X; y ~ x}. Таку підмножину будемо називати класом еквівалентності. Зрозуміло, що клас еквівалентності є множиною всіх елементів, еквівалентних довільному елементу з цього класу. Справедлива наступна теорема:

Теорема 1. Два класи еквівалентності або не перетинаються або співпадають.

Доведення. Припустимо, що перетин множин K(x) і K(х') непорожній, і візьмемо z Î K(x) Ç K(х'). Клас еквівалентності K(x) утворений з елементів, еквівалентних одному зі своїх елементів x. Оскільки x і z еквівалентні, то за властивістю транзитивності отримуємо, що K(x) утворений також з елементів, еквівалентних z. Аналогічно K(х') утворений з елементів, еквівалентних z. Таким чином, K(х) і K(х') співпадають.

Відношення еквівалентності на множині Х породжує деяке розбиття множини Х, тобто деяку сімю непорожніх підмножин множини X (класів еквівалентності), які попарно не перетинаються, а їх обєднання рівне X. Будь-які два елементи з одного класу звязані відношенням еквівалентності, тобто еквівалентні; з різних класів - не еквівалентні.

Навпаки, будь-яке розбиття множини X:

Х =,

де Xj непорожні і попарно не перетинаються, визначає деяке відношення еквівалентності, а саме x º х', якщо існує такий індекс j Î J, що x,х' Î Xj. У цьому випадку підмножини Xj є класами еквівалентності для цього відношення.

2.4.1 Фактор-множина

Виходячи із сказаного кожен клас еквівалентності Xj є підмножиною множини X, що складається з елементів, еквівалентних деякому фіксованому елементу цієї множини. Тому можна розглянути і множину всіх класів еквівалентності, яку звичайно називають фактор-множиною за даним відношенням еквівалентності R і позначають наступним чином Х/R. Якщо через K(x) позначити клас еквівалентності елемента x, то K(x) є елементом фактор-множини та x Î K(x).

Можна дати просту інтерпретацію фактор-множини на прикладах відношень еквівалентності, наведених раніше (1, 2, 3, 4, 5):

) фактор-множина - це множина Zm цілих чисел, порівняних за модулем m;

) фактор- множина - це множина напрямлених прямих на площині;

) фактор- множина - це множина місяців року. Вона може мати менше 12 місяців, бо в аудиторії може не виявитися студентів, які народилися в одному з місяців, скажімо в лютому.

.4.2 Рівнопотужні множини

Розглянемо відображення з множини натуральних чисел N в множину парних натуральних чисел N2, яке кожному натуральному числу ставить у відповідність подвоєне число, тобто бієктивне відображення f (п) = 2п. Тоді можна сказати, що існує стільки парних натуральних чисел, скільки й натуральних, а також, що y випадку нескінченних множин може існувати бієктивне відображення деякої множини на її підмножину, яка відмінна від самої множини. Завдяки поняттю бієктивного відображення можна порівнювати між собою нескінченні множини.

Дві множини X та Y називаються рівнопотужними, якщо існує принаймні одне бієктивне відображення f :X ? Y.

Відношення " X рівнопотужна Y " є відношенням еквівалентності між множинами. Клас еквівалентності, тобто клас всіх множин рівнопотужних даній множині, називається потужністю або кардинальним числом.

Скінченні кардинальні числа - це класи еквівалентності скінченних множин. Ці числа за визначенням є натуральними числами 0, 1, 2, ....

Слід відзначити, що ми приймаємо як первинне поняття натуральні числа, але їх строге математичне визначення досить складне. Як наслідок не легко apriori означити скінченні множини. Часто за визначенням вважають множину скінченною, якщо вона не рівнопотужна ніякій зі своїх підмножин, відмінних від самої множини, а потім доводять, що кардинальне число має властивості натуральних чисел.

Перейдемо до двох найбільш важливих нескінченних потужностей: потужності зчислених множин і потужності континууму.

.4.3 Зчисленні множини

Множина називається зчисленною, якщо вона рівнопотужна множині натуральних чисел N. Множина зчисленна, якщо існує хоча б одна бієкція цієї множини в множину N. Іншими словами, множина зчисленна, якщо її елементи можна пронумерувати натуральними числами і номери не будуть повторюватися.

Раніше ми зясували, що множина парних натуральних чисел N2 є зчисленною.

Задамо відображення f : Z ? N так: f(z)=2z при z>0, f(z)=2|z|+1 при z?0. Воно бієктивне і, значить, множина цілих чисел Z також є зчисленною.

Покажемо, що множина N ´ N рівнопотужна множині N. Дійсно, з наведеної далі схеми

бачимо, що відображення , тобто f : N ´ N ? N є бієкцією.

Інший варіант бієктивного відображення f : N ´ N ? N наведено далі.

Покажемо, що множина Z ´ Z рівнопотужна множині N. Далі наведено схему, яка задає відповідне бієктивне відображення f :Z ´ Z ? N

Таким чином, множина Z ´ Z також є зчисленною.

2.4.4 Потужність континууму

Теорема 2 (Кантора) . Множина дійсних чисел з інтервалу (0, 1) не є зчисленною.

Дійсно, доведемо, що множина X = (0, 1) дійсних чисел, які задовольняють нерівність 0 ? x ? 1, не є зчисленною.

Доведення проведемо від протилежного. Припустимо, що X зчисленна й існує деяка бієкція N на Х, тобто елементи X можуть бути записані y вигляді деякої послідовності x1, x2, x3, …, елементи якої попарно різні. Крім того, розглянемо дійсне число ?, яке визначимо так: перед комою поставимо 0, потім як j-й десятковий знак виберемо довільне ціле число між 1 і 8, яке відрізняється від j-го десяткового знака числа хj. Таким способом ми утворюємо нескінченний дріб, що визначає деяке число ?. Для довільного натурального j маємо таке. Оскільки j-й десятковий знак числа ? відрізняється від j-го десяткового знака числа хj і всі десяткові знаки числа ? відрізняються від 0 і 9, то ? ? хj (не допускаємо знаків 0 і 9, бо 0,102000... і 0,101999... одне і те ж саме число). Значить число ? не збігається ні з одним з чисел послідовності x1, x2, x3, … Ми отримали суперечність. Це й доводить теорему.

Будемо потужність множини X = (0, 1) називати потужністю континууму. Потужність континууму - це також потужність множини всіх дійсних чисел, оскільки є бієкцією (0, 1) на R.

Дійсно, нехай x1?x2 Припустимо, що суперечність Отже, це відображення інєктивне.

Це відображення також є сюрєктивним, бо з рівності .

Наведемо без доведення теорему.

Теорема 3 (Бернштейна). Нехай X та Y - дві довільні множини. Тоді 1) або існує інєкція X в Y, або існує інєкція Y в X (обидві обставини не виключають одна одну); 2) якщо існує одночасно інєкція X в Y та інєкція Y в X, то існує також бієкція X на Y.

Наслідок. Для заданих множин X та Y є тільки три можливості:

а) існує інєкція X в Y і не існує інєкція Y в X. В цьому випадку говорять, що Y має потужність строго більшу потужності X, або що X має потужність, строго меншу потужності Y;

б) існує інєкція Y в X і не існує інєкція X в Y. Тоді X має потужність строго більшу потужності Y або Y має потужність, строго меншу потужності X;

в) існує бієкція X в Y. У цьому випадку кажуть, що X і Y мають однакову потужність або рівнопотужні.

Теорема 4. Якою б не була множина X, множина її підмножин має потужність, строго більшу потужності X.

Виходячи з останньої теореми, для нескінченних множин існує нескінченне число класів рівнопотужних множин.

На завершення сформулюємо континуум-гіпотезу. Згідно цієї гіпотези, клас множини P(N) іде одразу за класом множини N (тобто між ними не можна вставити проміжний клас). Узагальнена континуум-гіпотеза полягає в припущенні, що при довільній множині X клас множини P(X) іде безпосередньо за класом множини X. Доведено (П. Коен, 1968 р.), що континуум-гіпотеза не має рішення - її не можливо ані довести, ані спростувати, можна тільки прийняти її або протилежне їй твердження як аксіому.

.5 Операції над бінарними відношеннями

Так як відношення на множині задаються підмножинами , то для них визначні ті ж операції, що й над множинами, а саме:

. Об'єднання:

.

. Перетинання:

.

3. Різниця:

.

. Доповнення:

, де .

Крім того, необхідно визначити інші, ще не знайомі нам, операції над бінарними відношеннями.

. Обернене відношення .

Визначення. Якщо - відношення, то відношення називається оберненим відношенням до даного відношення тоді й тільки тоді, коли .

Наприклад, якщо - "бути старіше", то - "бути молодше"; якщо - "бути дружиною", то - "бути чоловіком".

Нехай або . У такому випадку .

Приклад. Знайти відношення , обернене даному .

Розвязання:

.

. Композиція (або складене відношення):

Визначення. Нехай - відношення на , а - відношення на . Композицією відношень і називається відношення , певне як

.

Ця множина позначається

.

Зокрема, якщо відношення визначене на множині , то композиція визначається як

.

Приклад. Нехай , , , і нехай відношення на і на задані у вигляді

;

.

Знайти композицію .

Розвязання:

і ; ; і ; ;

і ; ; і ; ;

і ; ; і ; .

і ; ;

Отже, .

Приклад. Нехай і - бінарні відношення, задані на множині додатних цілих чисел у вигляді і . Знайти композиції і .

Розвязання:

, .

. Транзитивне замикання:

Визначення. Транзитивним замиканням називається множина, що складається з таких і тільки таких пар елементів з , тобто , для яких в існує ланцюжок з елементів : , між сусідніми елементами якої виконується відношення : , ,…,, тобто

.

Наприклад, для відношення - "бути дочкою" композиція - "бути онукою", - "бути правнучкою" і т.д. Тоді об'єднання всіх цих відносин є транзитивне замикання - "бути прямим нащадком".

Якщо відношення транзитивне, то .

Визначення. Транзитивне замикання на є найменше транзитивне відношення на , що містить як підмножину.

Процедура обчислення транзитивного замикання для відношення :

) привласнити ;

) обчислити , привласнити ;

) зрівняти і . Якщо , то перейти до кроку 4, якщо , то привласнити і перейти до кроку 2;

) .

. Рефлексивне замикання:

Визначення. Нехай тотожне відношення . Тоді рефлексивне замикання визначається як .

Якщо транзитивне і рефлексивно, то .

Приклад. Нехай - відношення на множині дійсних чисел "бути менше". Знайти рефлексивне замикання відношення .

Розвязання:

,

, тому що - транзитивне, тоді

- "бути не менше".

Визначення. Рефлексивне замикання на є найменше рефлексивне відношення на , що містить як підмножину.

Розглянемо приклади операцій над бінарними відношеннями.

Приклад. Нехай на множині натуральних непарних чисел визначено відношення - "бути більше". Задати характеристичною властивістю і списком відношення , обернене відношення , доповнення , композицію , транзитивне замикання і рефлексивне замикання .

Розвязання:

- "бути більше";

.

- "бути менше";

.

- "бути не більше";

.

;

, тому що - транзитивне.

- "бути більше або дорівнює", де - тотожне відношення, ;

.

Приклад. Нехай на множині натуральних чисел задані відношення і . Визначити відношення: ; ; ; .

Розвязання:

;;;;;

;

.

Аналогічно знайдемо

= ;

;

.

2.5.1 Правила побудови матриць відношень

Правила побудови матриць відношень: , , , , по відомій матриці відношення :

Матриця доповнення - в матриці вихідного відношення замінити одиниці нулями, а нулі - одиницями.

Матриця оберненого відношення - проставити в ній одиниці, які симетричні щодо головної діагоналі відповідним одиницям вихідної матриці відношення .

Матриця складеного відношення - для кожної одиниці вихідної матриці відношення , що стоїть в -тому рядку і -тому стовпці , в -тому рядку матриці , проставити одиниці в ті -ті стовпці, у яких є одиниці в -тому рядку вихідної матриці.

Матриця транзитивного замикання нетранзитивного відношення . Для її побудови треба виконати цикл (один або декілька) наступних дій:

а) для кожної одиниці у матриці відношення , що стоїть в -тому рядку і -тому стовпці , в -тому рядку матриці проставити одиниці в тих -тих стовпцях, у яких є одиниці в -тому рядку, а також в -тому рядку вихідної матриці;

б) отриману матрицю відношення приймають за вихідну і повторюють процедуру а), виконуючи таким чином наступний цикл обчислень доти, поки матриця не перестане змінюватися, тобто поки в деякому циклі обчислень вихідна і обчислена матриці не збіжаться.

Якщо відношення транзитивне, то матриця його транзитивного замикання збігається з матрицею вихідного відношення, тобто .

Матриця рефлексивного замикання - побудувати матрицю транзитивного замикання, а потім в отриманій матриці замінити нулі на головній діагоналі, якщо такі є, на одиниці.

Якщо відношення рефлексивно, то матриця рефлексивного замикання збіжиться з матрицею транзитивного замикання, тобто .

Приклад. Які властивості відношення , заданого матрицею на рис. 2.5? Виконати операції над відношенням . Побудувати матриці отриманих відношень.

Розвязання:

Рисунок 2.5 - Відношення

Список відношення

.

Визначимо властивості відношення :

а) нерефлексивне, тому що головна діагональ матриці відношення не містить тільки одиниці;

б) не антирефлексивне, тому що головна діагональ матриці відношення не містить тільки нулі;

б) несиметричне, тому що матриця відношення не симетрична щодо головної діагоналі;

в) не антисиметричне, тому що в матриці відношення відсутні одиниці, симетричні щодо головної діагоналі;

г) нетранзитивне, тому що існують пари, для яких порушується умова транзитивності, наприклад, , , але .

Виконаємо операції над :

; ; ;

(рис. 2.6,а);

(рис. 2.6,б);

(рис. 2.6,в).

Для одержання транзитивного замикання виконаємо процедуру виявлення нетранзитивності для вихідного відношення. Виявлений тільки один випадок порушення транзитивності , , але . Додавши цю пару до , або скориставшись визначенням, одержимо:

.

Перевірка на транзитивність відношення не виявляє в ньому порушення транзитивності, тому

(рис. 2.6,г).

Рефлексивне замикання, відповідно до визначення

(рис. 2.6,д).

Рисунок 2.6 - Матриця властивостей відношення

2.6 Відображення

2.6.1 Визначення і приклади

Нехай задано дві множини Х і Y. Відображення f з множини Х в множину Y кожному елементу х з множини Х ставить у відповідність деякий (один) елемент f (х) з множини Y. Елемент f (х) називають образом елемента х при відображенні f. Символічно відображення записується так: f : Х ® Y чи XY. У випадку Y = Х кажуть ще про відображення f множини Х в (на) себе.

Якщо Х = {x1, x2, …, xn} - скінченна множина, тo відображення f : Х ® Y, можна задати записом з двох рядків f = , де f (хi) Î Y, i = 1, 2, …, n.

Наприклад, f: Х ? Y, Х = {l, 2, 3, 4, 5}, Y = {а, b, c}, f = .

Відображення часто ілюструють за допомогою діаграм (рис.2.7), де відповідність між елементами показують стрілками. Відображення задане в попередньому прикладі зображене на рис. 2.7 (а). Відповідності рис.2.7(б) та рис.2.7(в) відображеннями не будуть, оскільки на рис.2.7(б) елемент 1 Î X не має образу в множині Y, а на рис.2.7(в) елементу 3 Î X ставиться у відповідність два елементи з множини Y: b та c.

Рисунок 2.7 - Відображення

Приклади відображень:

) f (x) = є відображенням множини відмінних від нуля елементів множини дійсних чисел R\{0} в R.

) Якщо, Х - множина дійсних функцій ?(х), визначених та інтегрованих на інтервалі [a, b], то інтеграл є відображенням з множини Х в множину дійсних чисел R.

) Якщо X - множина кривих скінченної довжини на площині, то можна визначити відображення з Х в множину R+ додатних дійсних чисел, яке кожній кривій ставить у відповідність її довжину.

2.6.2 Деякі часткові випадки

1. Відображення f множини Х в множину Х, визначене рівністю f (х) = х, називається тотожним.

. Якщо Х є підмножиною Y, то відображення Х в Y , визначене рівністю f (х) = х, називається канонічною інєкцією Х в Y.

. Відображення з прямого добутку множин Х ´ Y в X, що ставить у відповідність кожній парі (x, y) Î Х ´ Y елемент х Î Х, називається проекцією на множину X. Аналогічно визначається проекція на множину Y .

.6.3 Інєктивні, сюрєктивні та бієктивні відображення

Відображення f множини Х в множину Y називають інєктивним, чи інєкцією, якщо двом різним елементам з множини Х відповідають два різних елементи з множини Y (рис.2.8(а) та 2.8(в). Іншими словамиf : X ? Y інєктивне, якщо для будь-яких x ? x1, x, x1 Î Х, f (x) ? f (x1).

Зауважимо, зокрема, що канонічна інєкція деякої підмножини в саму множину є інєктивним відображенням.

Відображення f називають сюрєктивним, чи сюрєкцією, якщо для кожного елемента y з множини Y існує принаймні один елемент x з множини X такий, що f(x)=y. (рис.2.8(б) та 2.8(в)).

Відображення називають бієктивним, чи бієкцією, якщо воно одночасно інєктивнe та сюрєктивнe. Відображення f є бієктивним, якщо кожен елемент із Y є образом при відображенні f деякого, і при тому єдиного, елемента з X (рис.2.8(в)). Кажуть, що бієктивне відображення встановлює взаємно однозначну відповідність між множинами X та Y. Бієкція множини на себе називається також перестановкою чи перетворенням.

Рисунок 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}та два відображення

: Х ? 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 Поняття бінарної алгебраїчної операції

Кожна математична теорія вивчає множини, на яких введені певні відношення. Алгебра вивчає множини, на яких визначені відношення, що мають назву алгебраїчних операцій. З прикладами алгебраїчних операцій ми зустрічалися ще в шкільному курсі математики, а також вивчаючи інші розділи вищої математики. Прикладами алгебраїчних операцій є додавання і множення чисел, многочленів, алгебраїчних дробів, додавання векторів площини, додавання матриць, обєднання і переріз множин, додавання і множення функцій (наприклад, синусів і косинусів), композиція відображень тощо. Ці операції виконуються над парами елементів однієї і тієї ж множини: над парами чисел, многочленів, векторів, функцій. Тому їх називають бінарними алгебраїчними операціями або просто бінарними операціями. Дамо нижче загальне означення бінарної алгебраїчної операції, якому, зокрема, задовольняють перелічені вище операції.

Визначення. Нехай - довільна множина елементів . Бінарною алгебраїчною операцією (або законом композиції) на множині називається довільне (але фіксоване) відображення декартового квадрата в . Таким чином, будь-якій впорядкованій парі елементів однозначно ставиться у відповідність певний третій елемент тієї ж множини .

Іноді замість пишуть , а ще частіше конкретну бінарну операцію позначають спеціальним символом: +, , , і т.д. Але коли вивчають загальні властивості бінарних операцій, тобто властивості, притаманні багатьом конкретним бінарним операціям, то кажуть про довільні операції, для позначення яких будемо користуватися символами і .

Із означення випливає: для того, щоб відображення було бінарною алгебраїчною операцією на множині , необхідно, щоб задовольняло вимоги:

) було бінарним;

) було завжди виконуваним, тобто завжди можна було б знайти результат виконання операції - елемент ;

) було однозначним, тобто елемент був єдиним;

) задовольняв би умову замкненості, тобто щоб обовязково .

Приклад.

. Нехай - відповідно множини цілих, раціональних, дійсних та комплексних чисел. Бінарними алгебраїчними операціями на цих множинах є, наприклад, дії додавання, віднімання та множення.

. Нехай - множина всіх квадратних матриць порядку з дійсними елементами. Бінарними алгебраїчними операціями на множині є, наприклад, дії додавання, віднімання та множення матриць.

. Дія знаходження модуля дійсного числа не є бінарною операцією на множині , оскільки не виконується вимога бінарності.

Звичайно бінарна операція на скінченній множині з елементів задається так званою таблицею Келі, яка являє собою квадратну -таблицю з двома входами, кожній клітинці якої відповідає впорядкована пара елементів даної множини, елемент стоїть у вибраному рядку, елемент - у вибраному стовпці.

Приклад. У множині задано бінарну операцію так, що є остачею від ділення добутку на число 4. Задати бінарну операцію таблицею Келі.

Розв'язання. Таблиця Келі для операції у множині має вигляд:

3.2 Властивості бінарних алгебраїчних операцій

Визначення. Операція на множині називається комутативною, якщо .

Приклади.

1. Додавання і множення чисел комутативні.
2. Віднімання і ділення чисел некомутативні.
3. Множення матриць некомутативне.
4. Операції перерізу і обєднання множин комутативні.
5. Операція декартового добутку двох множин некомутативна.

Значення комутативності бінарної алгебраїчної операції полягає в тому, що вона дає можливість переставляти елементи, над якими виконується бінарна операція, і завдяки цьому спрощувати формули і твердження.

Таблиця Келі комутативної бінарної алгебраїчної операції симетрична відносно діагоналі.

Приклад. Операція у множині з прикладу 1 є комутативною, оскільки її таблиця Келі симетрична відносно діагоналі.

Визначення. Операція на множині називається асоціативною, якщо :.

Властивість асоціативності дозволяє опускати дужки у виразі .

Приклади.

1. Додавання і множення чисел асоціативні. Це дозволяє не ставити дужки у виразах

   і .

2. Віднімання чисел неасоціативне:

(Наприклад, )

Операції перерізу і обєднання множин асоціативні.

Значення асоціативності бінарної алгебраїчної операції полягає в тому, що вона дає можливість визначити композицію трьох і взагалі будь-якого числа елементів множини, взятих у певному порядку.

Визначення. Операція на множині називається дистрибутивною зліва відносно операції , якщо

і дистрибутивною справа відносно операції , якщо

.

Якщо операція комутативна на множині , то поняття дистрибутивності зліва і справа збігаються. В цьому випадку просто кажуть, що операція дистрибутивна відносно операції .

Приклади.

1. Множення чисел дистрибутивне відносно додавання і зліва і справа:

і

1. Додавання недистрибутивне і зліва і справа відносно множення:

та .

1. Операції перерізу і обєднання множин є взаємно дистрибутивними одна відносно одної.

Далі будемо припускати, що всі бінарні операції, які будуть розглядатися, асоціативні. В цьому випадку неважко визначити степінь елемента множини у такий спосіб: визначаємо , при покладаємо: . Тоді для будь-яких додатних цілих чисел виконуються співвідношення:

і .

Разом з бінарними алгебраїчними операціями не позбавлені інтересу більш загальні -арні операції, так само як і їх комбінації.

Визначення. -арною алгебраїчною операцією на множині називається відображення . Число називається арністю операції .

-арна алгебраїчна операція за елементами множини визначає -й елемент цієї ж множини. При будемо мати відповідно унарну, бінарну, тернарну і т.д. алгебраїчні операції.

Приклади.

1.Перехід до протилежного числа є унарною операцією.

2.Піднесення числа до квадрату є унарною операцією.

.Знаходження абсолютної величини числа є унарною операцією.

.Операція доповнення множини є унарною операцією.

3.3 Обернені бінарні операції

Нехай на множині визначена бінарна алгебраїчна операція .

Визначення. Якщо для будь-яких двох елементів і множини існує в множині одна і тільки одна пара елементів і таких, що і , то кажуть, що для визначеної на множині бінарної алгебраїчної операції виконується обернена операція, яку позначають .

Ясно, що якщо операція комутативна, то елементи і , про які йдеться в означенні, збігаються.

Приклади.

. Операцію, обернену до комутативної операції додавання (множення) чисел називають відніманням (діленням). Елемент , який задовольняє умовам і ( і ), називають різницею (часткою) і записують ( або ).

Існують множини, в яких операції додавання і множення визначені, а обернені їм операції віднімання і ділення не виконуються. Такою множиною є, наприклад, множина натуральних чисел . Існують також множини, наприклад, множина цілих чисел , в яких визначена операція додавання і виконується обернена їй операція - віднімання, а також множини, як, наприклад, множина відмінних від нуля раціональних чисел, в яких визначена операція множення і виконується обернена їй операція - ділення.

Обернена операція , очевидно, не є новою незалежною операцією, вона - похідна від операції .

3.4 Елементи, виділені відносно бінарної операції

Визначення. Якщо існує елемент такий, що , то він називається ідемпотентним по відношенню до операції , або просто ідемпотентом.

Визначення. Якщо існує елемент такий, що , то він називається нейтральним відносно операції , або одиничним.

Приклади.

. В множині 0 - нейтральний елемент відносно додавання +:

, а 1 - відносно множення :

. В множині всіх квадратних матриць -го порядку нульова матриця є нейтральним елементом відносно додавання матриць, а одинична матриця - відносно множення матриць.

. В множині всіх підмножин деякого універсуму - нейтральний елемент відносно обєднання: , а - нейтральний елемент відносно перерізу: .

Теорема (про єдиність нейтрального елемента). Якщо відносно операції існує нейтральний елемент, то він єдиний.

Доведення. Припустимо, що існують два нейтральних відносно операції елементи та і , тобто

;

.

Тоді , оскільки - нейтральний елемент, і , оскільки - нейтральний елемент. Отже . Одержана суперечність доводить теорему.

Визначення. Елемент називається симетричним елементу відносно операції , якщо , де - нейтральний відносно операції елемент.

Приклади.

. Нейтральний елемент , очевидно, симетричний сам собі.

. В множині відносно додавання симетричним елементу є елемент , який називається протилежним до . Відносно множення симетричним елементу є елемент , який називається оберненим до .

. В множині всіх квадратних матриць -го порядку відносно операції множення матриць симетричними є взаємно обернені матриці.

Теорема (про єдиність симетричного елемента). Якщо бінарна операція , визначена на множині , асоціативна, то для будь-якого елемента в ньому може існувати не більше одного симетричного елемента.

Доведення. Припустимо, що і - два різних симетричних елементу елемента, так що

, .

Тоді

.

Одержана суперечність доводить теорему.

Приклад. Визначити елементи, виділені відносно операції у множині з прикладу 1.

Розв'язання. Щоб визначити нейтральний елемент, знайдемо стовпець таблиці Келі, що цілком збігається з початковим. В таблиці для операції такий стовпець є, і йому відповідає елемент 1. Отже, елемент 1 є нейтральним відносно операції .

Щоб визначити існування симетричного елемента для даного, рухаємося по рядку, який відповідає даному елементу, до нейтрального елемента. Зверху, у початковому рядку, напроти нейтрального елемента знаходиться шуканий симетричний.

Для елемента 2 не існує симетричного, оскільки 20=22=0 і 21=23=2.

3.5 Поняття алгебраїчної структури

На непорожній множині може бути задано, взагалі кажучи, багато різних алгебраїчних операцій. Бажаючи виділити одну з них, використовують дужки: , і говорять, що операція визначає на алгебраїчну структуру. Якщо операція асоціативна чи комутативна, то такі ж назви привласнюються і відповідній алгебраїчній структурі. Природа елементів основної множини нас не цікавить, справжніми обєктами вивчення є алгебраїчні операції. Ясно, що виділити можна не одну операцію, а декілька.

Визначення. Непорожня множина разом із заданою на ній сукупністю алгебраїчних операцій називається алгебраїчною структурою: .

Приклад. У множині цілих чисел, крім природних операцій +, (додавання і множення), легко вказати "похідні" операції що виходять при допомозі + (або -) і : , і т.д. Ми приходимо до різних алгебраїчних структур , .

В процесі розвитку математики була виділена і детально досліджена невелика кількість основних типів алгебраїчних структур, алгебраїчні операції в яких за своїми властивостями більш-менш близькі до операцій додавання і множення. У звязку з цим при вивченні алгебраїчних структур застосовуються дві системи термінів або дві форми запису: адитивну і мультиплікативну. Нижче наводиться словник цих термінологій:

Адитивна термінологіяМультиплікативна термінологіяОперація+ - додавання - множенняРезультат операціїсумадобутокНейтральний елементнуль 0одиниця 1або еСиметричний елементпротилежний -аобернений або Обернена операціявідніманняділенняРезультат оберненої операціїрізницячасткаСтепінь елементакратне степінь

Крім операцій, на множині можуть бути визначені різні відношення.

Визначення. Непорожня множина разом із заданою на ній сукупністю алгебраїчних операцій і сукупністю відношень називається алгебраїчною системою: . Якщо алгебраїчна система не містить операцій, вона називається моделлю, якщо не містить відношень - алгеброю.

Приклади.

. є алгебраїчною системою.

. не є алгебраїчною системою, оскільки результат операції - не завжди є натуральним числом.

. є алгебраїчною системою. Ця алгебраїчна система носить назву "арифметика".

. Множина дійсних функцій однієї дійсної змінної, тобто функцій разом з унарною операцією диференціювання утворює алгебру

.

3.6 Основні типи алгебраїчних структур

Якщо визначити на деякій множині одну або дві бінарні операції і наділити їх певними властивостями, а також визначити наявність нейтральних і симетричних елементів відносно цих бінарних алгебраїчних операцій, можна дістати різні алгебраїчні структури.

) Алгебраїчні структури з однією бінарною операцією: півгрупи і групи

Визначення. Півгрупою називається непорожня множина з однією бінарною алгебраїчною операцією , яка має тільки властивість асоціативності

.

Приклади.

. - півгрупа.

2. - півгрупа.

Визначення. Групою називається непорожня множина , на якій визначена бінарна алгебраїчна операція , так, що виконуються наступні умови (аксіоми групи):

1)операція асоціативна:

;

2)в множині існує нейтральний елемент :

;

3)для кожного елемента існує симетричний елемент :

.

Позначається або просто .

Означення групи можна сформулювати ще й так:

Визначення. Групою називається півгрупа з одиницею, в якій для кожного елемента існує симетричний.

Група, в якій операція комутативна, тобто називається комутативною або абелевою. (на честь норвезького математика Нільса Хенріка Абеля (1802-1829)), який вивчав комутативні групи).

Визначення. Група, в якій всі елементи основної множини є степенями одного елемента, тобто є результатами k-кратного застосування операції (k=0,1,2,...), називається циклічною. Цей єдиний елемент називається твірним елементом циклічної групи. Циклічна група з твірним елементом позначається так: і є абелевою групою вигляду або в залежності від того, яка група розглядається - мультиплікативна або адитивна.

Число елементів групи називають її порядком.

Приклади.

. - абелева група цілих чисел, нейтральний елемент 0, оберненим до елемента є .

. - абелева група раціональних чисел, нейтральний елемент 1, оберненим до елемента є .

. Множина невироджених матриць порядку відносно операції множення матриць є некомутативною групою.

. Множина коренів -го степеня з 1 є циклічною групою.

) Алгебраїчні структури з двома бінарними операціями:

кільця і поля

Визначення. Кільцем називається непорожня множина , на якій визначені дві бінарні алгебраїчні операція + (додавання) і (множення) так, що виконуються наступні умови (аксіоми кільця):

К1. - абелева група:

1)операція + асоціативна:

;

2)в множині існує нульовий елемент :

;

3)для кожного елемента існує протилежний елемент :

.

4)операція + комутативна:

.

К2. - півгрупа:

5)операція асоціативна:

;

К3. Операція (множення) дистрибутивна зліва і справа відносно операції+(додавання):

6) ;

;

Кільце позначається або просто .

Алгебраїчна структура називається адитивною групою кільця, а - його мультиплікативною півгрупою.

Визначення. Кільце називається комутативним, якщо операція (множення) є комутативною, тобто .

(На відміну від груп, комутативне кільце не прийнято називати абелевим).

Означення кільця можна сформулювати ще й так:

Визначення. Кільцем називається множина з двома операціями + і ., яка відносно + є групою, а відносно є півгрупою і дистрибутивна відносно +.

Приклад. - кільце цілих чисел.

Визначення. Полем називається непорожня множина , на якій визначені дві бінарні алгебраїчні операція + (додавання) і (множення) так, що виконуються наступні умови (аксіоми поля):

1)операція + асоціативна на :

;

2)в множині існує нульовий елемент :

;

3)для кожного елемента існує протилежний елемент :

.

4)операція + комутативна на :

.

5)операція асоціативна на

: ;

6)операція дистрибутивна зліва і справа відносно операції+:

;

7)операція комутативна на :

;

8)в множині існує одиничний елемент :

9)для кожного ненульового елемента існує в обернений до нього елемент :

.

Означення поля можна сформулювати ще й так:

Визначення.

Полем називається комутативне кільце, елементи якого, відмінні від нульового елемента утворюють групу відносно операції .

Приклад.

. - поле раціональних чисел.

. - поле дійсних чисел.

. - поле комплексних чисел.

3.7 Ізоморфізми та гомоморфізми алгебраїчних структур

Визначення. Нехай - алгебраїчна операція, задана на множині , - алгебраїчна операція, задана на множині , - відображення множини в множину . Кажуть, що відображення зберігає алгебраїчну операцію , якщо для будь-яких елементів справедливо

.

Зміст цієї умови полягає в тому, що не має значення, чи здійснено спочатку операцію в , а потім виконане відображення , або спочатку виконане відображення , а потім здійснено операцію в .

Визначення. Дві алгебраїчні структури і називаються гомоморфними, якщо існує відображення , яке зберігає алгебраїчні операції. Відповідне відображення називається гомоморфізмом.

Визначення. Дві алгебраїчні структури і називаються ізоморфними, якщо існує взаємно однозначне відображення , яке зберігає алгебраїчні операції. Відповідне відображення називається ізоморфізмом.

Факт ізоморфізму алгебраїчних структур позначається символічно .

Визначення. Дві групи і називаються гомоморфними, якщо існує відображення , при якому зберігається групова операція, тобто таке, що .

Визначення. Дві групи і називаються ізоморфними, якщо існує взаємно однозначне відображення , при якому зберігається групова операція, тобто таке, що:

) ;

) - бієкція.

Визначення. Два кільця і називаються гомоморфними, якщо існує відображення , при якому зберігаються операції, тобто таке, що:

) ;

) ;

)

,

.

Визначення. Два кільця і називаються ізоморфними, якщо існує гомоморфне взаємно однозначне відображення.

Визначення. Два поля і називаються ізоморфними, якщо вони ізоморфні як кільця.

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)

.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 для завдання графа необхідно занумерувати вершини і ребра, а також задати відношення інцидентності. Відношення інцидентності будемо описувати трьома способами: матрицею інцидентності, матрицею суміжності, списком ребер графа. Опишемо докладно кожний з перерахованих способів.

Матриця інцидентності - це матриця розміром , де вертикально вказуються вершини , а горизонтально - ребра . На перетині -того і -того рядків число дорівнює:

а) у випадку неорієнтованого графа

б) у випадку орієнтованого графа

Матриця суміжності - це квадратна матриця розміром , де вертикально і горизонтально вказуються вершини графа і . На перетинанні -того і -того рядків число дорівнює:

числу ребер, що з'єднують ці вершини у випадку неорієнтованого графа;

числу ребер з початком в -тій вершині і кінцем в -тій вершині у випадку орієнтованого графа.

Список ребер графа - це таблиця, що складається із трьох рядків. У першому перераховані всі ребра; у другому і третьому - інцидентні їм вершини:

у випадку неорієнтованого графа порядок вершин у рядку довільний;

у випадку орієнтованого графа першою записується вершина, де починається ребро (другий рядок); вершина, де закінчується ребро, записується у третій рядок.

Для нумерації вершин і ребер графа використовують різний символьний запис: римські, арабські цифри, латинські букви.

Якщо графи рівні, то їх матриці суміжності і інцидентності, а також список ребер, однакові.

Приклад.

Задати матрицями інцидентності і суміжності, а також списком ребер, неорієнтований граф, зображений на наступному рисунку.

Розвязання:

Тут .

Список ребер

Ребро12345678910Вершинипочатокabaccdcdeeкінецьbccdddeefg

Як бачимо, у кожному стовпці матриці інцидентності є тільки два елементи, відмінних від нуля (або один, якщо ребро - петля).

Матриця суміжності симетрична щодо головної діагоналі.

Список ребер є найбільш компактним способом завдання графів.

Кожний із наданих способів однозначно описує граф, зображений на рисунку.

Приклад. Задати матрицями інцидентності, суміжності, списком ребер орієнтований граф, зображений на наступному рисунку.

Розвязання:

Список ребер

Ребро12345678910Вершинипочатокaabbccdfffкінецьabacdeedeg

Відмінність матриці інцидентності орієнтованого графа від неорієнтованого складається у вказівці початку і кінця ребер. Матриця суміжності губить свою симетричність. У списку ребер важливий порядок вказівки вершин, що з'єднують зазначеним ребром (від початку до кінця).

Як відзначалося вище, всі розглянуті способи завдання графів однозначно визначають граф. Виникає питання: чи можливо відновити граф по заданих матрицях інцидентності, суміжності або списку ребер? Очевидна позитивна відповідь.

По матриці інцидентності число ребер і вершин визначається з розмірності матриці: число ребер графа дорівнює числу стовпців , а число вершин - числу рядків матриці.

По матриці суміжності число вершин визначається з розмірності матриці. Як було відзначено, матриця суміжності н-графа симетрична щодо головної діагоналі, і кількість ребер визначається верхнім правим трикутником матриці, розташованим над головною діагоналлю, включаючи останню. Тобто, число ребер н-графа дорівнює сумі елементів, розташованих на головній діагоналі і у верхньому правому трикутнику.

У матриці суміжності орграфа симетрія відсутня, а число ребер дорівнює сумі всіх елементів матриці суміжності.

Список ребер є скороченим варіантом матриці інцидентності. Кількість ребер очевидна, а кількість вершин дорівнює максимальному номеру всіх перерахованих вершин зі списку.

Тобто, матриця інцидентності і список ребер по суті, еквівалентні, то знаючи матрицю інцидентності можна записати список ребер, і навпаки.

Побудова матриці інцидентності за списком ребер. Кожен рядок списку ребер відповідає рядку в матриці инцидентности з тим же номером.

Для неорієнтованого графа в кожному рядку списку ребер зазначені номери елементів матриці инцидентности, рівні 1 (всі інші елементи - нулі).

Для орієнтованого графа першою вказується вершина, що відповідає початку ребра (у матриці инцидентности - елемент ), а другий - відповідному кінцю ребра (у матриці инцидентности - елемент 1).

При збігу елементів у рядку списку ребер, у відповідному рядку матриці инцидентности записується число, відмінне від , 0, 1, наприклад, 2. Така ситуація відповідає наявності у графі петель.

Приклад. Побудувати матрицю інцидентності неорієнтованого графа за списком ребер:

Ребро12345678ВершинипочатокadecadbfкінецьdffebcffРозвязання.

Матриця інцидентності, відповідно до списку ребер, має вигляд:

Приклад.

Запиcати список ребер відповідно до матриці інцидентності орієнтованого графа:

Розвязання:

Список ребер, записаний відповідно до матриці інцидентності орієнтованого графа має вигляд:

Ребро12345678Вершинипочатокbbccddeaкінецьaccddeff

У визначенні уведене поняття ізоморфних графів. Чи можливо встановити, чи є графи ізоморфними за їхніми матрицями інцидентності, суміжності, або списку ребер?

Для перевірки ізоморфності графів і за матрицею суміжності необхідно визначити, чи існує така перестановка рядків і стовпців у матриці суміжності , щоб у результаті вийшла матриця . Із цією метою треба зробити всі можливі перестановки рядків і стовпців (а їхня максимальна кількість дорівнює ?)! Якщо після однієї із цих перестановок матриці суміжності тотожньо збіжаться, то графи ізоморфні.

Для перевірки ізоморфності графів і за матрицею інцидентності (і списку ребер) необхідно визначити, чи існує така перестановка рядків і стовпців у матриці інцидентності , щоб у результаті вийшла матриця . Із цією метою треба зробити всі можливі пари перестановок рядків і стовпців (а їхня максимальна кількість дорівнює )! Якщо після однієї із цих перестановок матриці інцидентності тотожно збіжаться, то графи ізоморфні.

І в першому, і в другому випадку це досить трудомісткі операції, і рішення задачі "вручну" не завжди виправдано. Найчастіше изоморфність графів простіше встановити з їх графічних подань.

5.3 Звязність графа. Маршрути, шляхи, ланцюги, цикли

5.3.1 G - неорієнтований граф

Визначення. Маршрутом (шляхом) у графі називається така послідовність ребер , у якій кожні два сусідніх ребра і мають загальну вершину. У маршруті те саме ребро може зустрічатися кілька разів. Іншими словами маршрут - це сукупність ребер, які об'єднані разом вершинами так, що можна рухатися по них уздовж графа.

Визначення. Початок маршруту - це вершина , інцидентна ребру і не інцидентна ребру . Кінець маршруту - це вершина інцидентна ребру і не інцидентна . Якщо ребра , ( , ) - кратні, то необхідно додатково вказувати, яку із двох інцидентних вершин вважати початком (кінцем) маршруту.

Визначення. Маршрут довжини - послідовність, що містить ребер. Іншими словами, довжиною маршруту називається кількість ребер у ньому; при цьому кожне ребро враховується стільки разів, скільки разів воно зустрічається в маршруті.

Позначення маршруту з у - послідовністю надлишкове, тому ми будемо позначати маршрут як .

Визначення. Маршрут, всі ребра якого різні, називається ланцюгом. Ланцюг, що не перетинає себе, тобто не має вершин, що повторюються, називається простим.

Приклад. Визначити можливі маршрути (і їхню довжину) з вершини в у графі, зображеному на наступному рисунку.

Розвязання: з вершини у ведуть, наприклад, шляхи:

) - довжини 2; 5) - довжини 6;

) - довжини 4; 6) - довжини 6;

) - довжини 4; 7) - довжини 8;

) - довжини 6; 8) - довжини 10.

Шляхи: 6), 8) не є простими.

Визначення. Маршрут, у якому збігаються початок і кінець - і - називається циклічним. Циклічний маршрут називається циклом, якщо він є ланцюг, і простим циклом - якщо це простий ланцюг.

Наприклад, маршрут для графа, зображеного на рис. 6.17, є простим циклом; а маршрут є циклом, але не буде простим, тому що містить вершини, які повторюються.

Визначення. Вершини і графа називаються зв'язаними, якщо існує маршрут з початком у і кінцем у . Маршрут між зв'язаними вершинами може бути поданий простим ланцюгом.

Визначення. Граф називається зв'язним, якщо будь-які пари його вершин зв'язані між собою.

Приклад. Граф, зображений на рис. 5.9,а - не зв'язний, а граф на рис. 5.9,б - зв'язний.

Рисунок 5.9 - Приклад незвязного і звязного графів

Теорема. Якщо існує маршрут з вершини в графа , то існує простий ланцюг, що з'єднує вершини і .

Наслідок. Граф є зв'язним тоді і тільки тоді, коли між будь-якими двома його вершинами існує простий ланцюг.

Визначення. Максимальний непустий зв'язний підграф графа називається компонентом графа .

Отже, кожен граф являє собою об'єднання своїх компонент, які попарно не перетинаються.

Незв'язний граф має, як мінімум, два компоненти. Наприклад, граф, зображений на рис. 5.9,а, має два компоненти: і .

Визначення. Вершина називається точкою зчленування, якщо видалення її із графа приводить до збільшення числа компонент звязності.

Визначення. Ребро називається міст, якщо видалення його із графа приводить до збільшення числа компонент звязності.

Визначення. Множина ребер зв'язного графа називається множиною розрізу, якщо видалення ребер із множини порушує звязність графа, а видалення власної підмножини множини залишає граф зв'язним. Якщо множина складається з одного ребра, то це ребро називається ребром розрізу.

Приклад. Визначити ребра розрізу графа, зображеного на наступному рисунку.

Розвязання: ребра , і - є ребрами розрізу. Їх видалення порушує звязність графа.

Приклад. Визначити множини розрізу для графа, зображеного на наступному рисунку.

Розвязання: Множинами розрізу для даного графа можуть бути, наприклад:

, , , , і т.д.

5.3.2 G - орієнтований граф

Визначення. Послідовність ребер, у якому кінець кожного попереднього ребра збігається з початком наступного , називається шляхом або орієнтованим маршрутом. У шляху те саме ребро може зустрічатися кілька разів.

Визначення. Початком шляху є вершина ребра , а кінцем шляху є вершина ребра .

Визначення. Довжиною орієнтованого маршруту називається кількість орієнтованих ребер, що входять у цей шлях.

Приклад. Для графа, зображеного на рис. 5.10, приведемо приклади орієнтованих маршрутів з вершини до вершини : ; ; - довжини 3; - довжини 5.

Рисунок 5.10 - Приклади орієнтованих маршрутів

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

Визначення. Контуром називається шлях, початок і кінець якого збігаються. Контур називається циклом, якщо він є ланцюгом, і простим циклом - якщо це простий ланцюг.

Приклад. Для графа, зображеного на рис. 5.11,а, приклади: орієнтованого ланцюга - ; контуру - ; циклу - . Для графа, зображеного на рис. 5.11,б, приклади: простого орієнтованого ланцюга - ; простого циклу - . При цьому зауважимо, що при записі циклу як для орієнтованого, так і для неорієнтованого графа, як початком, так і кінцем може бути обрана будь-яка вершина. Наприклад: ; і т.п.

Рисунок 5.11 - Приклади ланцюгів і циклів

Визначення. Для кожного орієнтованого графа може бути побудований неорієнтований граф , такий, що всі вершини цих графів збігаються, а кожне ребро (крім петель), стане неорієнтованим ребром графа . У такому випадку граф називається співвіднесеним графом орієнтованого графа .

Приклад. Для графа , зображеного на рис. 5.12,а, співвіднесений граф буде мати вигляд (рис. 5.12,б):

Рисунок 5.12 - Приклад співвіднесеного графа

Визначення. Вершина називається досяжною з вершини , якщо існує шлях з початком у і кінцем у .

Визначення. Орієнтований граф називається зв'язним, якщо його співвіднесений граф є зв'язним. Орієнтований граф називається сильно зв'язним, якщо для будь-якої пари вершин існує орієнтований шлях з , у .

Так, наприклад, граф, зображений на рис. 5.12,а, є зв'язним, але не є сильно зв'язним.

5.4 Метрика на графах

Визначення. Відстанню між вершинами і графа називається мінімальна довжина простого ланцюга з початком у вершині і кінцем у вершині . Якщо вершини і не з'єднані ланцюгом, тобто належать різним компонентам, то покладається, що .

У зв'язному графі відстань між вершинами задовольняє наступним умовам:

) , і тоді і тільки тоді, коли ;

) , ;

) , .

Функція , що задовольняє трьом перерахованим умовам, називається метрикою графа.

Визначення. Центром графа називається вершина, від якої максимальна з відстаней до інших вершин була б мінімальною.

Визначення. Периферійною точкою графа називається вершина, від якої максимальна з відстаней до інших вершин була б максимальна.

Визначення. Максимальна відстань від центра графа до його вершин називається радіусом графа .

Визначення. Найпростіший ланцюг найкоротшої довжини називається геодезичним.

Визначення. Відхиленням вершини називається найбільша довжина геодезичної, яка з неї виходить.

У зв'язку із цим можна дати ще одне визначення радіуса графа:

Визначення. Відхилення центра називається радіусом графа , а відхилення периферійної точки - діаметром графа .

Алгоритм знаходження відстаней від даної вершини до інших вершин графа :

1)позначаємо через ;

2)позначаємо індексом всі вершини, суміжні з вершиною , виписуємо множину всіх цих вершин з їхніми позначками;

)кожну вершину, що не належить множині і суміжну з кожною з вершин, що належать множині , позначаємо індексом ; виписуємо множину всіх цих вершин з їхніми позначками …;

) повторюємо описану процедуру доти, поки множина непомічених вершин не виявиться порожньою.

Приклад. Визначити відстань від вершини 7 (для зручності запису позначимо вершини графа арабськими цифрами) до всіх вершин графа , зображеного на наступному рисунку.

Розвязання. Згідно алгоритму відстань від вершини 7 будемо шукати в такий спосіб:

) ; 2) ; 3) .

Більше непомічених вершин немає. Тобто відстані від вершини 7 до кожної з вершин графа такі:

; .

Для визначення центра і радіуса графа необхідно побудувати для нього матрицю відстаней , кожен елемент якої описує відстань між вершинами і графа , тобто . Очевидно, що матриця відстаней симетрична щодо головної діагоналі (елементи якої дорівнюють нулю, тому що ).

Приклад. Визначити центр, периферійні вершини, радіус і діаметр графа , зображеного на на наступному рисунку.

Розвязання.

Матриця відстаней графа має вигляд.

Знайдемо максимальну відстань від кожної з вершин графа як :

; ; ; ; ; ; ; ; .

Отже, згідно з визначенням 6.36, центром графа є вершина 4; периферійні вершини - 1, 6, 7, 8, 9. Радіус графа , а діаметр графа .

5.5 Ейлерів цикл. Ейлерів граф

Теорія графів бере свій початок з рішення видатним математиком Ейлером у 1736 р. задачі про кенігсбергські мости. Вона виникла в пруськом містечку Кенігсберг на річці Прегал. Жителі Кенігсберга полюбляли гуляти по доріжках, які включають сім мостів через річку. Людей цікавило питання, чи можуть вони, почавши шлях з однієї ділянки суши, обійти всі мости по черзі за одну ходу, і повернутися в початок шляху, не перепливаючи річку. План розташування семи мостів у Кенігсберзі наведений на рис. 5.13.

Рисунок 5.13 - План розташування семи мостів у Кенігсберзі

Ейлер замінив план міста графом (рис. 5.14), у якому ділянки суші зобразив як вершини, а мости, їх з'єднуючі - як ребра.

Рисунок 5.14 - Заміна плана міста графом

Для того, щоб відповістити на поставлене запитання, дамо ряд визначень.

Визначення. Ейлеровим циклом називається цикл, що містить всі ребра графа.

Ейлерів цикл можна вважати як слід олівця, що вичерчує граф, не відриваючись від паперу.

Відшукання ейлерових циклів пов'язане з рядом прикладних задач. Наприклад, при перевірці дорожньої мережі необхідно по кожній дорозі досліджуваної мережі проїхати тільки один раз і повернутися у вихідний пункт. Очевидно, що такі цикли існують не на будь-якому графі.

Визначення. Ейлеровим графом називається граф, що містить ейлеров цикл.

Теорема Ейлера. Кінцевий неорієнтований граф ейлеров тоді і тільки тоді, коли він зв'язний, і степінь всіх його вершин парна (при підрахунку степеня вершини, будь-яку інцидентну їй петлю вважати двічі).

Доведення:

Необхідність. Якщо граф містить ейлеров цикл , то будь-які дві його вершини належать цьому циклу; граф зв'язний. Якщо при обході циклу деяка вершина зустрічається разів, то ми разів входимо і виходимо з неї (щораз по різних ребрах). Отже, степінь вершини дорівнює .

Достатність. Нехай граф зв'язний і степінь будь-якої його вершини парна (рис. 5.15). Нехай - деяка вершина графа, - суміжна їй вершина. Цій вершині інцидентно хоча б одне ребро , відмінне від , вершині - ребро, відмінне від , і т.д.

Рисунок 5.15 - Ейлерів граф

Побудуємо із цих ребер ланцюг, відзначаючи їх і не повторюючи вже пройдені.

Граф кінцевий, то цей ланцюг повинен закінчитися в деякій вершині . Число ребер, інцидентных вершині парне. Якби була відмінною від , ланцюг необхідно було би продовжити. Отже, .

Ми побудували цикл . Якщо в графі залишилися невідмічені ребра, то оскільки зв'язний, серед них найдеться хоча б одне, інцидентне якій-небудь вершині на циклі . Починаючи з вершини , ми можемо побудувати, як і раніше, цикл із ребер, що не ввійшли в . З і можна скласти новий цикл, що проходить із у по , потім уздовж усього циклу , і по частині циклу , що залишилася від до . Оскільки граф кінцевий, то після кінцевого числа кроків, ми одержимо ейлеров цикл.

Отже, ми готові відповістити на запитання жителів Кенігсберга. Для цього підрахуємо степіні вершин графа, побудованого Ейлером (рис. 6.33): ; ; ; . Цей граф має непарні степені вершин. Отже, цей граф не має ейлерова цикла. Тобто, неможливо пройти кожен міст по черзі за одну ходу і повернутися у вихідну точку шляху.

Приклад. Чи мають графи, зображені на рис.5.16 (а, б), ейлерів цикл?

Рисунок 5.16 - Приклад графів

Розвязання:

Щоб відповістити на поставлене запитання, порахуємо степені вершин графа: а) ; ; ; ; .

Степені всіх вершин графа, зображеного на рис. 6.35,а, парні, отже, граф, має ейлеров цикл;

б) ; ; ; ; ; .

Степені вершин і графа, зображеного на рис. 6.35,б, непарні, отже, граф не має ейлеров цикл.

Що стосується кенігсбергських мостів, можна задати інше питання: " чи можливо пройти кожен міст по одному разі і не обов'язково повертатися у вихідну точку маршруту?" Відповідь на це питання жадає від нас знання наступного визначення і теореми.

Визначення. Шлях, що включає кожне ребро графа тільки один раз, називається ейлеровим шляхом. У тому випадку, якщо ейлеров шлях не є ейлеровим циклом, він називається власним ейлеровим шляхом.

Теорема (про ейлерів шлях). Граф має власний ейлерів шлях тоді і тільки тоді, коли він зв'язний і рівно дві його вершини мають непарний степінь.

Так як граф для задачі про кенігсбергські мости має чотири вершини з непарними степенями, то можна зробити висновок про те, що даний граф не має власного ейлерова шляху, а отже, неможливо пройти кожен міст по одному разі, навіть якщо не потрібно повертатися у вихідну точку маршруту.

5.6 Шляхи і цикли Гамільтона

В 1857 році математик Вільям Роуен Гамільтон придумав іграшку-головоломку. Ця іграшка являла собою додекаедр - правильний багатогранник, 12 граней якого ? це правильні п'ятикутники. У кожному з 20 кутів просвердлувалась дірка, у яку вставляли кілочок, що зображував місто. За допомогою мотузки було потрібно знайти шлях через міста, відвідав кожне місто один раз, і повернутися у вихідне місто. Додекаедр на площині зображується так, як показано на рис. 5.17.

Рисунок 5.17 - Зображення додекаедра на площині

Задача головоломки зводиться до знаходження циклу в графі, що проходить через кожну вершину, крім початкової, тільки один раз.

Визначення. Шляхом Гамільтона (або гамільтоновим ланцюгом) називається простий ланцюг, що проходить через всі вершини графа, з початком і кінцем у різних вершинах .

Визначення. Цикл Гамільтона - це простий цикл, що проходить через всі вершини графа .

Гамільтонів цикл у деякому змісті протилежний ейлерову циклу, що проходить через всі ребра один раз, хоча до певного моменту обидва цикли можуть здаватися схожими. Цикл Гамільтона виявляється набагато складніше, і для його знаходження поки немає ефективних алгоритмів, що вимагають істотно меншого часу, чим пряме перебирання варіантів. Проте приведемо ряд теорем без доведення, що дозволяють нам судити про можливість відшукати гамільтонів цикл у досліджуваному графі. А для початку покажемо один з варіантів рішення головоломки, запропонованої Гамільтоном (рис. 5.18).

Рисунок 5.18 - Варіант розвязання головоломки Гамільтона

Теорема. Для будь-якої вершини із циклу Гамільтона існує рівно два ребра із цього циклу, інцидентні даній вершині.

Визначення. Граф, що має цикл Гамільтона, називається гамільтонів.

Виходячи з наведеного визначення, як наслідок теореми 6.5, робимо висновок про те, що будь-який граф, що має вершину степені 1, не є гамільтонів. Помітимо також, що для того, щоб граф мав цикл Гамільтона, необхідно, щоб він був зв'язним.

Приклад. Граф Петерсона, зображений на рис. 5.19,а, має шлях Гамільтона (рис. 5.19,б), але не має цикл Гамільтона.

Рисунок 5.19 - Граф Петерсона

Теорема. Якщо граф має ребро розрізу, то він не може мати цикл Гамільтона. Якщо компоненти графа, отримані шляхом видалення ребра розрізу, мають цикл Гамільтона, то граф має шлях Гамільтона.

Теорема. Якщо - зв'язний граф з вершинами і для кожної пари несуміжних вершин , сума степенів вершин задовольняє умові , тоді граф має цикл Гамільтона.

Наслідок. Якщо - зв'язний граф з вершинами і для кожної вершини виконується умова , то граф має цикл Гамільтона.

Приклад. Знайдіть цикл Гамільтона, якщо він існує, для графа , зображеного на рис. 5.20,а.

Рисунок 5.20 - Знаходження циклу Гамільтона

Розвязання: Граф - зв'язний, кількість вершин графа - . Степінь кожної з вершин дорівнює 3, тобто кожна з вершин графа задовольняє умові . Отже, даний граф є гамільтонів, тобто існує цикл Гамільтона. Знайти його можемо тільки методом перебирання. Результати прямого перебирання - цикл (рис. 6.41,б).

Практичне застосування циклів Гамільтона знаходимо в рішенні класичної задачі комівояжера, яка цікава для людей, у чиє коло обов'язків входить знаходження оптимальних шляхів, наприклад, об'їзду філій фірми, транспортування вантажів, доставки товарів і інше.

Задача комівояжера. Комівояжер повинен відвідати кілька міст і повернутися у вихідний пункт. Відстані між містами відомі. Потрібно знайти дорогу найкоротшої довжини. При такій постановці задачі схема доріг являє собою граф, у якій будь-якому ребру запропонована певна довжина . Задача комівояжера зводиться до знаходження в отриманому графі із заданими довжинами ребер циклу Гамільтона мінімальної довжини.

Існує ряд алгоритмів, досить громіздких, що дозволяють знаходити найкоротший шлях від вершини до вершини , таких як алгоритми Дейкстри, Флойда-Уоршолла і т.п. Але ефективних алгоритмів, для пошуку циклу Гамільтона мінімальної довжини немає. Через їхню відсутність, щораз цю практичну задачу доводиться вирішувати методом прямого перебирання.

5.7 Планарні графи

Визначення. Граф називається правильно укладеним на площині, якщо його графічне подання таке, що ребра графа перетинаються тільки в його вершинах.

Визначення. Граф називається плоским (планарним), якщо він ізоморфний деякому графу, правильно укладеному на площині. Тобто плоский граф - це граф, який можна правильно укласти на площині.

Приклад. Графи і , подані на наступному рисунку, ізоморфні. Граф - правильно укладений на площині. Отже, дані графи - плоскі.

Розглянемо граф як малюнок на аркуші паперу. Якщо граф планарний, тобто намальований так, що його ребра не перетинаються, і його необхідно розрізати уздовж ребер, то граф виявиться розділеним на частини, включаючи зовнішню частину. Такі частини називаються гранями. Границя кожної грані є циклом.

Визначення. Гранню планарного графа називається така максимальна ділянка площини, що будь-які дві її точки можуть бути з'єднані кривою, що не перетинає ребро графа.

Задача про можливості правильного укладання графа на площині є актуальною у зв'язку з використанням у радіотехніці друкованих схем. Інтегральні мікросхеми складаються із шарів мініатюрних мікросхем, удрукованих у пластину. Ці схеми наносяться на ізолятор у друкований спосіб і перетинання яких-небудь двох провідників, у непередбачуваних точках (не у вершинах графа), привело б до їх замикання. Тобто для друкування електричних схем просто необхідно, щоб графи (що їх зображують) були плоскими.

Задачі, пов'язані із плоскими графами, актуальні не тільки в радіотехніці. Приведемо класичну задачу про три міста і три джерела постачання. Нехай є три міста , і і три джерела життєзабезпечення: водонапірна башта , електростанція і станція магістрального газопроводу . Чи можна з'єднати ці міста із джерелами постачання водою, газом і електрикою так, щоб траншеї, прориті для цих ліній (на одній глибині) не перетиналися?

Ця задача зводиться до побудови плоского графа, ізоморфного графу, зображеному на рис. 5.21.

Рисунок 5.21 - Заданий граф

Відповідь на питання поставлене у сформульованій задачі негативна. Завжди можна намалювати 8 попарно неперетинаючихся ліній, а дев'ята обов'язково перетне одну із цих восьми.

Доведення неможливості такої побудови спирається на теорему, доведену Жорданом. Проілюструємо її в такий спосіб. Нехай - безперервна замкнута лінія без самоперетинань (рис. 5.22). Ця лінія ділить площину на дві частини: зовнішню і внутрішню. Будь-які дві точки і із внутрішньої і зовнішньої частин відповідно можна з'єднати тільки лінією, що перетинає .

Рисунок 5.22 - Безперервна замкнута лінія

Позначимо граф, зображений на рис. 5.21 як . Замінимо граф йому ізоморфним (рис. 5.23).

Рисунок 5.23 - Ізоморфний граф

З'єднати вершини і без перетинання вже проведених ребер неможливо, тому що точка лежить усередині області, обмеженої кривою , а точка - поза зазначеної області. Отже, граф не є планарним.

Аналогічно доводиться непланарність повного графа (рис. 5.24).

Рисунок 5.24 - Повний граф

Використовуючи графи і , можна сформулювати наступний критерій планарності графів.

Теорема. (Теорема Куратовського). Граф є планарним тоді і тільки тоді, коли він не містить підграф, ізоморфний графу або .

Існують і інші критерії планарності графів.

Теорема. Якщо - зв'язний планарний граф, що містить вершин, ребер і граней, то повинна виконуватися умова .

За допомогою теореми 6.8 задача про життєзабезпечення трьох будинків (рис. 6.44) вирішується в такий спосіб. У графа шість вершин і дев'ять ребер: , , а кількість граней - . Підставимо в умову . Умова теореми 6.8 не виконується. Отже, граф - не планарний.

Лема. У довільному планарному графі з кількістю вершин не менше трьох має місце нерівність .

За допомогою леми 6.1 доведемо, що граф не планарний. Граф має п'ять вершин і десять ребер: , . Скористаємося умовою . Як бачимо, умова для графа не виконана, отже, граф не планарний.

5.8 Розфарбування графів

Нехай G =(V,E ) довільний граф, а Nk={1,2,...,k }.

Будь-яке відображення f :V ® Nk, яке ставить у відповідність кожній вершині v V деяке натуральне число f (v) Nk, називається розфарбуванням графа G. Число f (v) називається кольором або номером фарби вершини v.

Розфарбування f графа G називається правильним, якщо для будь-яких його суміжних вершин v і w виконується f (v) f (w).

Мінімальне число k, для якого існує правильне розфарбування графа G, називається хроматичним числом графа G і позначається Xp(G ).

Мінімальним правильним розфарбуванням графа G називається правильне розфарбування для k= Xp (G ).

Для певних типів графів визначити хроматичні числа нескладно. Наприклад, 1-хроматичними є порожні графи G =(V,Æ) і тільки вони. Хроматичне число повного графа Kn дорівнює n, а хроматичне число довільного двочасткового графа - 2. 2-хроматичні графи часто називають біхроматичними.

Очевидними є такі твердження.

Лема. Якщо кожна звязна компонента графа G потребує для свого правильного розфарбування не більше k фарб, то c(G )£k.

Лема. Граф є біхроматичний тоді і тільки тоді, коли він двочастковий.

Зокрема, всі дерева і прості цикли парної довжини C2k є біхроматичні. У той же час, c(C2k+1)=3.

Використовуючи теорему Кеніга, останню лему можна переформулювати у такому вигляді.

Лема. Граф є біхроматичний тоді і тільки тоді, коли він не має циклів непарної довжини.

Проблема визначення, чи є заданий граф k-хроматичним для певного k, та проблема знаходження мінімального правильного розфарбування для заданого графа належать до класу задач, для яких на сьогодні не існують (і є всі підстави вважати, що не існують взагалі) ефективні точні алгоритми їх розвязку. Тому важливими є результати, які дозволяють оцінити значення хроматичного числа c(G ), виходячи з певних характеристик та властивостей графа G.

Теорема. Позначимо через D(G ) найбільший зі степенів вершин графа G, тоді c(G ) £ D(G )+1.

Доведення проведемо індукцією за кількістю n вершин графа G. Для тривіального графа (n=1) і графів з двома вершинами нерівність виконується.

Нехай твердження теореми виконується для всіх графів з кількістю вершин t (t ³ 2). Розглянемо довільний граф G з t +1 вершиною. Вилучимо з G деяку вершину v, дістанемо граф G ¢, всі степені вершин якого не перевищують D(G ). Отже, за припущенням індукції, для правильного розфарбування G ¢ потрібно не більше ніж D(G )+1 фарба. Правильне розфарбування для G дістанемо з правильного розфарбування графа G ¢, якщо пофарбуємо вершину v у колір, відмінний від кольорів усіх суміжних із v вершин. Оскільки таких вершин не більше, ніж D(G ), то для правильного розфарбування графа G достатньо D(G )+1 фарба.

Наслідок. Для правильного розфарбування довільного кубічного графа достатньо чотири фарби.

Так склалося історично, що окреме місце в теорії графів займають дослідження з розфарбування планарних графів. Повязано це зі славетною проблемою або гіпотезою чотирьох фарб.

Грані плоскої карти назвемо суміжними, якщо їхні межі мають принаймні одне спільне ребро.

Гіпотеза чотирьох фарб виникла у звязку з розфарбуванням друкованих географічних карт (звідси й термін "плоска карта") і формулювалась так:

"Грані довільної плоскої карти можна розфарбувати не більше ніж чотирма фарбами так, що будь-які суміжні грані матимуть різні кольори".

Згодом зявилось інше, рівносильне, формулювання гіпотези чотирьох фарб.

Для правильного розфарбування вершин довільного планарного графа потрібно не більше чотирьох фарб.

Ця гіпотеза виникла в середині ХIХ століття. Більше ста років професійні та непрофесійні дослідники намагалися довести або спростувати цю гіпотезу. В результаті багаторічних досліджень виявилось, що для вирішення проблеми чотирьох фарб необхідно перевірити її справедливість для скінченного числа графів певного виду. Кількість варіантів, які потрібно було перебрати, була настільки великою, що тільки за допомогою потужної ЕОМ, яка неперервно працювала протягом більше двох місяців, у 1976 році справедливість гіпотези чотирьох фарб була підтверджена. Однак такий "фізичний" експериментальний спосіб доведення не зовсім влаштовує багатьох професійних математиків, і вони продовжують пошуки аналітичного доведення гіпотези.

Зауважимо, що існують планарні графи, хроматичне число яких дорівнює 4. Найпростішим таким графом є K4. Отже, гіпотезу чотирьох фарб не можна "вдосконалити", перетворивши у "гіпотезу трьох фарб".

.9 Дерева і ліс

Визначення. Неорієнтованим деревом (або просто деревом) називається неорієнтований зв'язний граф без циклів, отже без петель і кратних ребер, що має не менш двох вершин.

Дерево є мінімальним зв'язним графом у тому розумінні, що видалення хоча б одного ребра приводить до того, що граф виявляється незв'язним.

Приклад. Чи є графи, зображені на рис. 5.25, (а), (б) деревами?

Рисунок 5.25 - Графи

Розвязання:

Граф на рис. 5.25(а) є деревом, тому що він зв'язний і не містить циклів. Граф на рис. 5.25(б) не є деревом, тому що містить цикл .

Дамо без доведення ряд теорем, корисних для вивчення дерев.

Теорема. Будь-яке дерево з вершинами містить ребро.

Теорема. Нехай - граф, що містить більше однієї вершини. Видаляючи його ребра можна одержати дерево тоді і тільки тоді, коли він зв'язний.

Визначення. Лісом називається незв'язний неорієнтований граф без циклів. Зв'язані компоненти лісу є деревами.

Приклад. На рис. 5.26 наведений приклад лісу, що містить три дерева.

Рисунок 5.26 - Приклад лісу, що містить три дерева

Добре зрозумілим прикладом дерева є: будь-яке генеалогічне дерево; організаційна структура будь-якого підприємства, організації.

Визначення. Орієнтованим деревом називається вільний від петель орієнтований граф, співвіднесений граф якого є деревом; тому якщо існує шлях від вершини до вершини , то він єдиний.

Помітимо, що якщо в орієнтованому дереві є ребро , то немає ребра , інакше шлях був би циклом.

Приклад. На рис. 5.27 наведено приклад орієнтованого дерева:

Рисунок 5.27 - Приклад орієнтованого дерева

Визначення. Вершини дерева степіня 1 називаються листя, інші вершини - внутрішніми вершинами.

Наприклад, у дерева, зображеного на рис. 6.49(а), листя це вершини . Інші вершини є внутрішніми.

Дерева визначаються такою властивістю: для будь-яких двох вершин дерева шлях з вершини до вершини єдиний. І, навпаки, якщо для будь-яких двох вершин графа існує єдиний шлях з вершини до вершини , тоді граф - дерево.

Припустимо, що дерево являє собою якийсь фізичний об'єкт, рухливий у вершинах. Його можна підвісити за кожну з вершин. Так, наприклад, якщо дерево, зображене на рис. 5.28(а) підвісити за вершину , або , то воно буде виглядати, як показано на рис. 5.28(а) або на рис. 5.28 (б).

Рисунок 5.28 - Приклад дерева

Обрана нами вершина називається коренем дерева і розташовується в самій верхній його частині. Для дерева на рис. 5.28(а) коренем є вершина , а для дерева на рис. 5.28(б) - вершина .

Визначення. Дерево, корінь якого визначений, називається кореневим деревом.

Аналогічно визначається і орієнтоване кореневе дерево. При цьому варто пам'ятати, що всі його ребра орієнтуються від кореня.

При заміні кореневого неорієнтованого дерева на кореневе орієнтоване дерево , говорять, що є породженим кореневим деревом .

Приклад. На рис. 5.29(а) зображене неорієнтоване кореневе дерево, а на рис. 5.29(б) - породжене їм орієнтоване кореневе дерево.

Рисунок 5.29 - Неорієнтоване і породжене ним орієнтоване дерево

Якщо корінь дерева обраний, то можна ввести ще ряд визначень.

Визначення. Рівнем вершини називається довжина єдиного шляху від кореня дерева до вершини .

Визначення. Висотою дерева називається довжина самого довгого шляху від кореня дерева до листя.

Приклад. Для кореневого дерева, зображеного на наступному рисунку, визначити рівень вершини , висоту дерева.

Розвязання: Рівень вершини дорівнює двом; а висота дерева з коренем у вершині дорівнює максимальному шляху від кореня до вершини - -дорівнює п'яти.

Для генеалогічних дерев дамо ряд визначень. Їх можна розповсюдити на будь-які орієнтовані кореневі дерева.

Визначення. Якщо існує орієнтоване ребро з в , то вершина називається батьком вершини , а вершина - сином (дочкою) вершини .

Визначення. Якщо є одночасно батьком і , то і називаються братами (сестрами).

Визначення. Якщо існує орієнтований шлях з вершини у вершину , то вершина називається предком вершини , а вершина - нащадком вершини .

Приклад. Визначити батьків і синів, братів, предків і нащадків кореневого орієнтованого дерева, зображеного на на наступному рисунку.

Розвязання: є батьком і ; - батьком і ; - батьком , і ; - батьком і ; - батьком ; - батьком і . І навпаки: і - сини ; і - сини ; , і - сини ; і - сини ; - син ; і - сини .

Груп нащадків і предків можна виділити дуже багато, приведемо лише деякі приклади: - нащадки , отже, - предок для ; є нащадком , отже, - предок .

5.10 Алгоритми пошуку найкоротших шляхів

Розглянемо орієнтований граф G=(V,E), дугам якого приписані ваги. Це означає, що кожній дузі (u,v) поставлено у відповідність деяке дійсне число a(u,v), яке називається вагою даної дуги. Вважаємо a(u,v)=?, якщо дуга (u,v) не існує.

Під довжиною шляху будемо розуміти суму ваг дуг, з яких складається шлях. Довжину найкоротшого шляху будемо позначати d(s,t) і називати відстанню від s до t. Якщо не існує жодного шляху з s в t, то вважаємо d(s,t)=?.

Введемо ще одне обмеження. Нехай ваги дуг будуть тільки додатними значеннями. Тому що при існуванні дуг з відємними вагами довжина найкоротшого шляху між парою вершин стає невизначеною, виходячи з можливості кількаразового включення таких дуг у шлях.

Якщо відома відстань між парою вершин, можна легко визначити найкоротший шлях. Тому що для двох довільних вершин s і t (s?t) існує така вершина v, що d(s,t)=d(s,v)+d(v,t). Цією властивістю володіє і передостання вершина в найкоротшому шляху від s до t. Отже, визначаючи в такий спосіб передостанню вершину, можна пройти від кінця найкоротшого шляху до його початку.

Більшість відомих алгоритмів знаходження відстані між двома вершинами s і t можна описати наступною послідовністю дій:

) При заданій матриці ваг дуг A[u,v], обчислюємо деякі верхні обмеження D[v] на відстані від s до всіх вершин v.

) Щораз, коли з'ясовується, що D[u]+A[u,v]<D[v], поліпшуємо оцінку D[v]=D[u]+A[u,v].

) Процес закінчується, коли подальше поліпшення жодного з обмежень неможливо. Значення кожної D[u] дорівнює відстані d(s,u). Вершину s у цьому випадку називають джерелом.

5.10.1 Алгоритм пошуку у глибину

Робота всякого алгоритму обходу складається в послідовному відвідуванні вершин і дослідженні ребер. Які саме дії виконуються при відвідуванні вершини і дослідженні ребра - залежить від конкретної задачі, для розвязування якої виконується обхід. У кожному разі факт відвідування вершини запам'ятовується, так що з моменту відвідування і до кінця роботи алгоритму вона вважається відвідуваною. Вершину, що ще не відвідана, називають новою. У результаті відвідування вершина стає відкритою і залишається такою, поки не будуть досліджені всі інцидентні їй ребра. Після цього вона перетворюється в закриту.

Існує багато алгоритмів на графах, в основі яких лежить систематичний перебір вершин, такий, що кожна вершина проглядається в точності один раз. Тому важливою задачею є знаходження гарних методів пошуку в графі. Метод пошуку гарний, якщо він дозволяє алгоритму розвязання задачі, що цікавить нас, легко використовувати цей метод, і кожне ребро графа аналізується не більше одного разу (або кількість таких досліджень обмежена зверху).

Пошук у глибину - це найбільш важлива завдяки численності додатків стратегія обходу графа. Ідея цього методу - шлях вперед у недосліджену область, поки це можливо, якщо ж навколо все досліджено, відступити на крок назад і шукати нові можливості для просування вперед. Метод пошуку в глибину відомий під різними назвами: "бектрекінг", "пошук з поверненням".

Обхід починається з відвідування заданої стартової вершини a, що стає активною і єдиною відкритою вершиною. Потім вибирається інцидентне вершині a ребро (a, y) і відвідується вершина y. Вона стає відкритою і активною. Надалі, як і при пошуку завширшки, кожний черговий крок починається з вибору активної вершини з множини відкритих вершин. Якщо всі ребра, які інцидентні активній вершині x, уже досліджені, вона перетворюється в закриту. У протилежному випадку вибирається одне з недосліджених ребер (x, y), це ребро досліджується. Якщо вершина y нова, то вона відвідується і перетворюється у відкриту.

При пошуку в глибину в якості активної вибирається та з відкритих вершин, що була відвідана останньою. Для реалізації такого правила вибору найбільш зручною структурою зберігання множини відкритих вершин є стек: вершини, які відкриваються, складаються в стек у тім порядку, у якому вони відкриваються, а в якості активної вибирається остання вершина.

5.10.2 Алгоритм пошуку завширшки

Пошук завширшки - це класичний метод розвязування задачі знаходження найкоротшого шляху між двома конкретними вершинами графа. Найкоротший шлях - це такий шлях, що з'єднує вершини графа та володіє тією властивістю, що ніякий інший шлях, що з'єднує ці вершини, не містить менше число ребер. Пошук у глибину мало придатний для розвязування цієї задачі, оскільки пропонований їм порядок проходження графа не має відношення до пошуку найкоротших шляхів, а пошук завширшки призначений саме для досягнення цієї мети.

Розглянемо метод пошуку завширшки. В розглянутому методі пошуку в глибину чим пізніше буде відвідана вершина, тим раніше вона буде використана - точніше, так буде при допущенні, що друга вершина відвідується перед використанням першої. Це прямий наслідок того факту, що переглянуті, але ще не використані вершини накопичуються в стеці. Пошук завширшки, грубо говорячи, ґрунтується на заміні стека чергою.

Ідея пошуку завширшки полягає в тому, щоб відвідувати вершини в порядку їхньої далекості від деякої заздалегідь обраної або зазначеної стартової вершини a. Інакше кажучи, спочатку відвідується сама вершина a, потім всі вершини, суміжні з a, тобто які знаходяться від неї на відстані 1, потім вершини, що перебувають від a на відстані 2, і далі по далекості.

Розглянемо алгоритм пошуку завширшки із заданою стартовою вершиною a. Спочатку всі вершини позначаються як нові. Першою відвідується вершина a, вона стає єдиною відкритою вершиною. Надалі кожний черговий крок починається з вибору деякої відкритої вершини x. Ця вершина стає активною. Далі досліджуються ребра, інцидентні активній вершині. Якщо таке ребро з'єднує вершину x з новою вершиною y, то вершина y відвідується і перетворюється у відкриту. Коли всі ребра, інцидентні активній вершині, досліджені, вона перестає бути активною і стає закритою. Після цього вибирається нова активна вершина, і описані дії повторюються. Процес закінчується, коли множина відкритих вершин стає порожньою.

Основна особливість пошуку завширшки, що відрізняє його від інших способів обходу графів, полягає в тому, що в якості активної вершини вибирається та з відкритих, яка була відвідана раніше інших. Саме цим забезпечується головна властивість пошуку завширшки: чим ближче вершина до старту, тим раніше вона буде відвідана. Для реалізації такого правила вибору активної вершини зручно використати для зберігання множини відкритих вершин чергу - коли нова вершина стає відкритою, вона додається в кінець черги, а активна вибирається в її початку.

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

Перевагою пошуку в глибину є той факт, що в момент відвідування вершини b стік містить послідовність вершин, що визначає шлях з a в b. Це стає очевидним, якщо відзначити, що кожна вершина, що попадає в стек, є суміжною з попередньою.

Однак недоліком пошуку в глибину є те, що отриманий у такий спосіб шлях у загальному випадку не буде найкоротшим шляхом з a в b. Від цього недоліку вільний метод знаходження шляху, заснований на пошуку завширшки.

5.10.3 Алгоритм Дейкстри

Найбільш ефективний алгоритм пошуку найкоротших шляхів на графах дав Дейкстра. Эдсгер Вібе Дейкстра (нідерл. Edsger Wybe Dijkstra; народився 11травня 1930 року в Роттердамі (Нідерланди) - помер 6 серпня 2002 року) - видатний нідерландський вчений, ідеї якого зробили величезний вплив на розвиток комп'ютерної індустрії. Популярність Дейкстрі принесли його роботи в галузі застосування математичної логіки при розробці комп'ютерних програм. Він брав активну участь в розробці мов програмування. Один з авторів концепції структурного програмування і алгоритму знаходження найкоротшого шляху на орієнтованому графі з вагами ребер, відомий як Алгоритм Дейкстри. У 1972 році Дейкстра став лауреатом премії Тьюрінга.

Нехай G = (V, E) - зважений орієнтований граф, w(vi, vj) - вага дуги (vi,vj). Почавши з вершини a, знаходимо відстань від a до кожної із суміжних із нею вершин. Вибираємо вершину, відстань від якої до вершини a найменша; нехай це буде вершина v*. Далі знаходимо відстані від вершини a до кожної вершини суміжної з v* вздовж шляху, який проходить через вершину v*. Якщо для якоїсь із таких вершин ця відстань менша від поточної, то замінюємо нею поточну відстань. Знову вибираємо вершину, найближчу до a та не вибрану раніше; повторюємо процес.

Описаний процес зручно виконувати за допомогою присвоювання вершинам міток. Є мітки двох типів: тимчасові та постійні. Вершини з постійними мітками групуються у множину M, яку називають множиною позначених вершин. Решта вершин має тимчасові мітки, і множину таких вершин позначимо як T, T=V\M. Позначатимемо мітку (тимчасову чи постійну) вершини v як l(v). Значення постійної мітки l(v) дорівнює довжині найкоротшого шляху від вершини a до вершини v, тимчасової - довжині найкоротшого шляху, який проходить лише через вершини з постійними мітками.

Фіксованою початковою вершиною вважаємо вершину a; довжину найкоротшого шляху шукаємо до вершини z (або до всіх вершин графа). Розглянемо приклади.

Варіант 1. Дана мережа автомобільних доріг, що зєднують міста України. Знайти найкоротші шляхи від Київа до кожного міста України (якщо рухатися можна тільки по дорогах).

Варіант 2. Надана кількість маршрутів пасажирського транспорту, для кожного маршруту відома його вартість. Знайти маршрут мінімальної вартості (можливо, з пересадками), наприклад, від Таїровського житлового масиву до Іллічівська.

У загальному випадку алгоритм Дейкстри заснований на присвоєнні вершинам тимчасових позначок, причому позначка вершини дає верхню межу довжини шляху від деякої вершини s до наданої вершини. Ці позначки поступово зменшуються за допомогою деякої ітераційної процедури, і на кожному кроці ітерації тільки одна з тимчасових позначок стає постійною. Останнє указує на те, що позначка вже не є верхньою межею, а дає точну довжину найкоротшого шляху від t до наданої вершини.

Розглянемо докладніше цей алгоритм. Надано граф G = (X, A, C) із зваженими дугами, приклад якого показано на рис.5.30 Позначимо L(хi) позначку вершини хi. Ваги відстаней наведено в таблиці.

Рисунок 5.30 - Граф із зваженими дугами

Таблиця - Ваги відстаней

x1x2x3x4x1c1c3x2c2x3c5x4c4

Розглянемо алгоритм знаходження найкоротшого шляху від вершини s до вершини t графа і більш загальний випадок: від вершини s до всіх вершин графа.

Привоєння початкових позначок.

КРОК 1. Присвоїти L(s)=0 і вважати цю позначку постійною. Для всіх вершин хis покласти L(хi)=? і вважати ці позначки тимчасовими. За поточну дану вершину з постійною позначкою візьмемо вершину p, тобто покласти p=s.

Оновлення позначок

КРОК 2. Для вершин, що входять в пряме відображення вершини р, тобто для всіх хi, належних Г(p), позначки яких тимчасові, змінити позначки відповідно до наступного виразу:

(xi)¬ min[L(xi),L(p)+C(p,xi)] (5.1)

Перетворення позначки в постійну.

КРОК 3. Серед всіх вершин з тимчасовими позначками знайти таку, для якої L()=min[L(xi)].

КРОК 4. Рахувати позначку вершини постійною і покласти p=.

КРОК 5(а). (При знаходженні шляху від s до t) - якщо поточна вершина p є шуканою, тобто p = t, то L(p) є довжиною найкоротшого шляху від s до t. Якщо pt, перейти до КРОКУ 2.

КРОК 5(б). (При знаходженні шляхів від s до всіх вершин)

-якщо всі вершини відмічені постійними позначками, то ці позначки дають довжини найкоротших шляхів;

-якщо деякі позначками є тимчасовими, то слід перейти до КРОКУ 2.

Як тільки довжини найкоротших шляхів від вершини s будуть знайдені, шляхи можна одержати за допомогою рекурсивної процедури (*). Оскільки вершина безпосередньо передує вершині хi в найкоротшому шляху від s до хi, то для будь-якої вершини хi відповідну вершину можна знайти як одну з вершин, що залишилися, для якої

()+c(,xi)=L(xi) (5.2)

Якщо найкоротший шлях від s до будь-якої вершини хi є єдиним, то дуги (, xi) цього найкоротшого шляху утворюють орієнтоване дерево з коренем s.

Якщо існує декілька найкоротших шляхів від s до якої-небудь іншої вершини, то при деякій фіксованій вершині співвідношення (*) виконуватиметься для більш ніж однієї вершини хi . В цьому випадку вибір може бути або довільним (якщо потрібен якийсь один найкоротший шлях між s і хi), або таким, що розглядаються всі дуги (, x2), що входять в який-небудь з найкоротших шляхів, і при цьому сукупність всіх таких дуг утворює не орієнтоване дерево, а загальний граф, званий базою щодо s.

Приклад. Розглянемо граф змішаного типу, зображений на рис. 5.31 (а), де кожне неорієнтоване ребро розглядається як пара протилежно направлених дуг рівної ваги.

Матриця вагів надана на рис. 5.31 (б). Потрібно знайти всі найкоротші шляхи від вершини х1 до всієї решти вершин.

КРОК 1. Привласнимо L(х1)=0, L(хi)=? для всіх хi, окрім х1 . Покладемо р=х1.

Перша ітерація.

КРОК 2. Знайдемо пряме відображення для поточної даної вершини:

Г(р)=Г(х1)={х2,х7,х8,х9}. Всі вершини, що входять в пряме відображення мають тимчасові позначки, тому перерахуємо їх значення:

(x2)=min[L(x2),L(x1)+c(x1,x2)]=min[?,0+10]=10;(x7)=min[?,0+3]=3;(x8)=min[?,0+6]=6;(x9)=min[?,0+12]=12.

Рисунок 5.31 - Приклад пошуку найкоротшого шляху:

а) граф; б) матриця вагів дуг

КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:

(х2)=10, L(х3)=?,(х7)=3, L(х4)=?,(х8)=6, L(х5)=?,(х9)=12, L(х6)=?.

Очевидно, що мінімальну позначку, яка дорівнює 3, має вершина х7.

КРОК 4. За наступну поточну позначку приймаємо вершину х7, тобто p=х7, а її позначка стає постійною, L(х7)=3+.

КРОК 5. Оскільки не всі вершини графу мають постійні позначки, переходимо до кроку 2.

Друга ітерація.

Граф з поточними значеннями позначок вершин надано на рис.5.32.

Рисунок 5.32 - Позначки в кінці першої ітерації

КРОК 2. Знаходимо Г(х7)={х2,х4,х6,х9}. Позначки всіх вершин тимчасові, отже перераховуємо їх значення:

(х2)=min[10,3+2]=5,(х4)=min[?,3+4]=7,(х6)=min[?,3+14]=17,(х9)=min[12,3+24]=12.

КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:

(х2)=5, L(х3)= ? ,(х4)=7, L(х5)= ? ,(х6)=17, L(х8)=6, L(х9)=12.

Очевидно, що мінімальну позначку, рівну 5, має вершина х2 .

КРОК 4. За наступну поточну позначку приймаємо вершину х2, тобто p=х2, а її позначка стає постійною, L(х2)=5+ .

КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.

Третя ітерація.

Граф з поточними значеннями позначок вершин надано на рис. 5.33.

Рисунок 5.33 - Позначки в кінці другої ітерації

КРОК 2. Знаходимо Г(х2)={х1,х3,х7,х9}. Помітки вершин х3 і х9 тимчасові, отже перераховуємо їх значення:

(х3)=min[?,5+18]=23,(х9)=min[12,5+13]=12.

КРОК 3. На даному кроці ітерації маємо наступні тимчасові помітки вершин:

L(х3)=23, L(х4)=7, L(х5)=? ,(х6)=17, L(х8)=6, L(х9)=12.

Очевидно, що мінімальну мітку, рівну 6, має вершина х8.

КРОК 4. За наступну поточну помітку приймаємо вершину х8, тобто p=х8, а її мітка стає постійною, L(х8) = 6+ .

КРОК 5. Не всі вершини графа мають постійні помітки, тому переходимо до кроку 2.

Четверта ітерація.

КРОК 2. Знаходимо Г(х8)={х1,х5,х6,х9}. Помітки вершин х5, х6 і х9 тимчасові, отже, перераховуємо їх значення:

(х5)=min[?,6+23]=29,(х6)=min[17,6+15]=17,(х9)=min[12,6+5]=11.

КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:

(х3)=23, L(х4)=7,(х5)=29, L(х6)=17, L(х9)=11.

Очевидно, що мінімальну позначку, рівну 7 має верші на х4 .

КРОК 4. За наступну поточну мітку приймаємо вершину х4, тобто p=х4, а її мітка стає постійною, L(х4) = 7+.

КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.

П'ята ітерація.

КРОК 2. Знаходимо Г(х4)={х3,х5,х6,х7}. Позначки вершин х3, х5 і х6 тимчасові, отже, перераховуємо їх значення:

L(х3)=min[23,7 + 25]=23,(х5)=min[29,7 + 5]=12,(х6)=min[17,7 +1 6]=17.

КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:

(х3) = 23, L(х5) = 29,(х6) = 17, L(х9) = 11.

Очевидно, що мінімальну позначку, рівну 11 має вершина х9 .

КРОК 4. За наступну поточну позначку приймаємо вершину х9, тобто p=х9, а її мітка стає постійною, L(х9) = 11+.

КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.

Шоста ітерація.

КРОК 2. Знаходимо Г(х9)={х1,х2,х6,х7,х8}. Саме вершина х6 тимчасова, отже перераховуємо її значення: L(х6)=min[17,11+9]=17.

КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин: L(х3) = 23, L(х5) = 12, L(х6) = 17.

Очевидно, що мінімальну позначку, рівну 12 має вершина х5 .

КРОК 4. За наступну поточну мітку приймаємо вершину х5, тобто p = х5, а її мітка стає постійною, L(х5) = 12+.

КРОК 5. Оскільки не всі вершини графа мають постійні мітки, переходимо до кроку 2.

Сьома ітерація.

КРОК 2. Знаходимо Г(х5) = {х4, х6}. Позначка вершини х6 тимчасова, отже, перераховуємо її значення:

(х6)=min [17,12 + 10]=17.

КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки:(х3) = 23, L(х6) = 17.

Очевидно, що мінімальну позначку, рівну 17 має вершина х6 .

КРОК 4. За наступну поточну позначку приймаємо вершину х6, тобто p=х6, а її позначка стає постійною, L(х6) = 17+.

КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.

Восьма ітерація.

КРОК 2. Знаходимо Г(х6)={х3,х5,х7,х8,х9}. позначка вершини х3 тимчасова, отже, перераховуємо її значення: L(х3)=min[23,17 + 20]=23.

КРОК 3. На даному кроці ітерації маємо одну тимчасову позначку вершини: L(х3)=23, яка стає постійною.

КРОК 4. Всі вершини мають постійні мітки, тому алгоритм закінчений. Для знаходження найкоротшого шляху між вершинами, наприклад, х2 і початковою х1 послідовно використовуємо співвідношення:

(x'2)+c(x'2,x2)=L(x2) = 5, (5.3)

де вершина x'2 - це вершина, безпосередньо передуюча x2 в найкоротшому шляху від х1 до x2 . Єдиною такою вершиною є вершина х7 . Далі відношення (5.3) застосовуємо другий раз:

(x'7)+с(x'7,x7)=L(x7)=3 (5.4)

Єдиною такою вершиною є вершина х1 . Тому найкоротший шлях від х1 до x2 є перелік вершин: х1, х7, х2.

Вершина х1, є базою та надає всі найкоротші шляхи від х1 , які надано на рис.5.34.

Девята ітерація. Кінець алгоритму.

Рисунок 5.34 - Вершина х1 є базовою вершиною

.10.4 Алгоритм Флойда

Алгоритм Флойда - динамічний алгоритм для находження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений у 1962 році Робертом Флойдом. Роберт Флойд (англ. Robert Floyd, 8 червня 1936 року, Нью-Йорк, США - 25 вересня 2001 року, Стенфорд, США) - американський вчений в області теорії обчислювальних систем. Мав нагороди: у 1978 році - премія Тюрінга за його безперечний вплив на методологію створення ефективного і надійного програмного забезпечення і за його допомогу в становленні таких областей комп'ютерних наук як семантика мов програмування, автоматична верифікація програм, автоматичний синтез програм, і аналіз алгоритмів", у 1991 році - премія піонера обчислювальної техніки (англ. Computer Pioneer Award) від IEEE [4].

Припустимо, що ми маємо помічений орграф, який містить час польоту по маршрутах, що зв'язують певні міста.

Припустимо, що необхідно побудувати таблицю, де приводився би мінімальний час перельоту з одного (довільного) міста в будь-який іншій. В цьому випадку ми стикаємося із загальною задачею знаходження найкоротших шляхів, тобто знаходження найкоротших шляхів між всіма парами вершин орієнтованого графа.

Формулювання завдання. Надано орієнтований граф G = (X, A), кожній дузі (ребру) (u, w) цього графу відповідає невідємна вага C u w. Загальна задача знаходження найкоротших шляхів полягає в знаходженні для кожної впорядкованої пари вершин (u, w) будь-якого шляху від вершини u у вершину w, довжина якого є мінімальною серед всіх можливих шляхів від u до w.

Можна розвязувати цю задачу, послідовно застосовуючи алгоритм Дейкстри для кожної вершини, що оголошується як джерело. Але для розвязання поставленої задачі можна скористатися алгоритмом, запропонованим Флойдом.

Припустимо, що всі вершини орграфа послідовно пронумеровані від 1 до n. Алгоритм Флойда використовує матрицю A(n,n), в якій знаходяться довжини найкоротших шляхів:= Cij, якщо i ?j;= 0, якщо i = j;j = ¥, якщо відсутній шлях з вершини i у вершину j.

Над матрицею A виконується n ітерацій. Після k-ої ітерації Aij містить значення найменшої довжини шляху з вершини i у вершину j, причому шлях не проходить через вершини з номерами великими k.

Обчислення на k -ій ітерації виконується за формулою:

= min (A k-1ij, A k-1ik, A k-1kj) (5.5)

Верхній індекс k означає значення матриці A після k-ої ітерації.

Для обчислення Akij проводиться порівняння величини Ak-1ij (тобто вартість шляху від вершини i до вершини j без участі вершини k або іншої вершини з вищим номером) з величиною Ak-1ik + Ak-1kj (вартість шляху від вершини i до вершини k плюс вартість шляху від вершини k до вершини j). Якщо шлях через вершину k дешевше, ніж Ak-1ij, то величина Akij змінюється.

Розглянемо помічений орграф, наданий на рис. 2.6.

Рисунок 5.35 - Помічений орграф

Матриця A (3х3) на нульовій ітерації (k = 0):

Матриця A ( 3 х 3 ) після першої ітерації (k = 1):

Матриця A (3 х 3) після другої ітерації (k = 2):

Матриця A (3 х 3) після третьої ітерації (k = 3):

Кінець алгоритму.

Задача пошуку найкоротших шляхів виникає при проектуванні і удосконаленні маршрутних мереж транспорту загального користування у містах, розподілі пасажирських кореспонденцій за шляхами прямування, визначенні завантаження ділянок маршрутних мереж і пасажиропотоків.

Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів останнім часом інтенсивно розвивається. Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від знаходження оптимального маршруту між двома обєктами на місцевості (наприклад, найкоротший шлях від будинку до університету), в системах автопілоту, для знаходження оптимального маршруту при перевезеннях, комутації інформаційного пакету в Internet і т.д.

Література

Основна

1.Новиков Ф.А. Дискретная математика для программистов. - С.-Пб.: Питер, 2001. - 304 с.

2.Бондаренко М.Ф. Компютерна дискретна математика. - Харків: "Компанія СМІТ", 2004. - 480 с.

.Нікольський Ю.В. Дискретна математика. - К.: Видавнича група BHV, 2007. - 368 с.

.Новиков Ф.А. Дискретная математика для программистов. - С.-Пб.: Питер, 2006. - 364 с.

.Донской В.И. Дискретная математика. - Симферополь: "СОНАТ", 2000. - 360 с.

.Сигорский В.П. Математический аппарат инженера. Изд. 2-е, стереотип. "Texнiкa", 1977, 768 с.

.Иванов Б.Н. Дискретная математика: Алгоритмы и программы: Учебное пособие. М.: Лаборатория базовых знаний, 2001. - 288 с.

Додаткова література

1.Акимов О.Е. Дискретная математика: логика, группы, графы. - М.: Лаборатория базових знаний, 2001. - 376 с.