Представлення графа за допомогою матриці інцидентності

Графи

1. Означення та властивості графів.

2. Деякі спеціальні класи простих графів.

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

Простим графом називають пару G=(V,), де V – деяка скінченна непорожня множина елементів, а E – множина невпорядкованих пар різних елементів із V.

Елементи множини V називають вершинами графа, а елементи множини E – ребрами графа.

 

V = {V₁, V₂, V₃, V₄}

E = {{V₁, V₂},{ V₂, V₃},{V₁, V₃},{ V₃, V₄}}

Для зручності ребра позначають e₁ = {V₁, V₂}.

Після того, як додали елемент V₅, отримали інший граф, де V складається з п’яти елементів, а E є тією ж самою множиною, що й для попереднього графа.

Мультиграфом називають пару (V, E), в якій V – скінченна множина, а E – сім’я невпорядкованих пар різних елементів із V.

Під словом сім’я слід розуміти сукупність невпорядкованих пар різних елементів із V, в якій елементи можуть повторюватись.

 

 

V = {V₁, V₂, V₃, V₄, V₅}

E = {{V₁, V₂}, {V₁, V₂}, {V₁, V₂}, {V₂, V₃},{V₂, V₃}, {V₃, V₄}, {V₃, V₄}, {V₃, V₄}, {V₄, V₅}}

Ребра, які з’єднують одні і ті ж вершини, називаються кратними.

Псевдографом називають пару (V, E), в якій V – скінченна непорожня множина вершин, а E – сім’я невпорядкованих пар елементів із V.

 

 

V = {V₁, V₂, V₃, V₄}

E: {V₁, V₂}, {V₁, V₂}, {V₂, V₃},{V₂, V₂}, {V₃, V₃}, {V₃, V₁}, {V₃, V₄}, {V₁, V₃}

Ребра, які з’єднують одну і ту ж саму вершину називаються кратними.

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

Орієнтованим графом називають пару (V, E), де V – скінчена непорожня множина елементів, а E – множина впорядкованих пар елементів з множини V.

 

V = {V₁, V₂, V₃, V₄}

E: {(V₂, V₁), (V₁, V₃), (V₃, V₁),(V₂, V₃), (V₃, V₂), (V₃, V₃), (V₄, V₃)}

На відміну від простих графів елементи множини Е називаються дугами або орієнтованими ребрами.

Орієнтованим мультиграфом називають пару (V, E), де V – скінчена непорожня множина вершин, а E – сім’я впорядкованих пар елементів із V.

 

 

 

Вершини простого графа u, v називаються суміжними, якщо {u, v} є ребром.

Якщо e={u, v} є ребром, то вершини u, v називаються його кінцями.

Ребра u та v називаються суміжними, якщо вони мають спільний кінець.

Ребро e і вершину v називають інцидентними, якщо v є кінцем ребра e.

 

Для V₁ суміжні V₂, V₃, V₄. Для V₄ суміжні V₁, V₂. V₁ інцидентна з ребрами e₁, e₄, e₅, а V₃ - з ребрами e₄, e₂.

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

deg (V₁)=4, deg (V₂)=4, deg (V₃)=4, deg (V₄)=3, deg (V₅)=3.

Нехай G – неорієнтований граф, який має m ребер, тоді:

 

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

Неорієнтований граф має парну кількість вершин непарного степеня.

M=9 =18

Нехай G=(V₁, E₁), H=(V₂, E₂) прості графи.

Граф G називається підграфом H, якщо V₁ V₂, E₁ E₂.

 

 

Об’єднанням двох простих графів G(V₁, E₁), H(V₂, E₂) називається граф W=(V, E), в якого

V=V₁ V₂, E = E₁ E₂

Повний граф з n вершинами (K_n) – простий граф, у якого будь-яка пара вершин з’єднані між собою єдиним ребром.

 

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

Граф G=(V, E) називається дводольним, якщо:

1. V=V₁ V₂, V1 V₂=

2. кожне ребро з’єднує вершини з V₁ та V₂.

 

 

V = { V₁, V₂, V₃, V₄ }

V₁ = { V₁, V₂ }, V₂ = { V₃, V₄ }

Повним дводольним графом називається дводольний граф, в якому кожна вершина з V₁ з’єднана ребром з кожною вершиною V₂.

Повний дводольний граф позначать K_{m, n}, де m – кількість вершин множини V₁, а n – кількість вершин множини V₂.

 

 

Повний дводольний граф K_{2, 3}.

Повний дводольний граф при m=1 називають зіркою.

 

 

Зірка K_{1, 4}.

Зауваження

Повний дводольний граф K_{3, 3} відіграє важливу роль при встановленні структури певного типу графів.

Циклом C_n (n 3) називається граф з множиною вершин V = {V₁, V₂, …, V_n} та множиною ребер E={{V₁, V₂}, {V₂, V₃}, …, {V_n-1, V_n}, {V_n, V₁}}.

 

Цикли C₄.

Колесом W_n (n 3) називається граф, який отримується з циклу C_nдодаванням (приєднанням) ще однієї вершини V_n+1, яку з’єднують ребрами з усіма іншими вершинами графа.

W₄

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

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

Приклад

 

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

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

 

 

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

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

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

Приклад

Зауваження

Недоліком представлення графів матрицями інцидентності є те, що для встановлення існування ребра, що з’єднує вершину V_i із V_j потрібно в загальному випадку проглядати (аналізувати) всі стовпчики цієї матриці.

Деякою перевагою матриці інцидентності є те, що її розмір (n*m).

Зауваження

Перевагою представлення графів матрицями суміжності є, що вони булеві. Тоді просто розв’язуються задачі встановлення існування ребра з вершини V_i до вершини V_j (потрібно проаналізувати значення елемента a_ij).

Недоліком представлення є те, що в незалежності від кількості ребер, матриця має розмір (n*n), кількість елементів – n².

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

 

 

V1	V2
V1	V3
V1	V4
V2	V3
V4	V3

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

Задача про найкоротший шлях

1. Шляхи та цикли. Зв’язність графів.

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

3. Зважені графи. Задача про найкоротший шлях і алгоритм її розв’язку.

Шляхом довжини r із вершини u в вершину v в неорієнтованому графі називається послідовність ребер вигляду

e₁ ={x₀, x₁}, e₂={x₁, x₂},…, e_r ={x_r-1, x_r}, x₀= u, x_r= v

Вершини u, v – крайні, всі решта – внутрішні вершини шляху.

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

Простим шляхом (циклом) називається шлях (цикл), який не містить ребер, які повторюються.

 

V₁V₅V₆ – простий шлях.

V₁V₂V₅V₄V₁V₂ – не простий шлях.

V₁V₅V₄V₁ – простий цикл.

V₁V₂V₃V₄V₅V₂V₁ – не простий цикл.

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

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

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

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

Граф, що на малюнку, зв’язний.

 

 

V₁ і V₂ не можна з’єднати шляхом.

Шлях, який з’єднує вершини u та v в графі і має найменшу довжину серед усіх інших шляхів, які з’єднують ці вершини, називається геодезичним.

Кожну пару вершин зв’язного неорієнтованого графа можна з’єднати простим шляхом.

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

Шляхом довжини r в орієнтованому графі, що з’єднує вершини u та v, називається послідовність дуг вигляду

e₁ =(x₀, x₁), e₂=(x₁, x₂),…, e_r =(x_r-1, x_r), x₀= u, x_r= v.

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

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

 

V₁V₄V₅ – орієнтований шлях. В цьому графі немає орієнтованого циклу.

Сильнозв’язним орієнтованим графом називається граф, у якому для будь-яких його вершин u та v завжди існує орієнтований шлях з вершини v в u та орієнтований шлях з u у вершину v.

Граф на малюнку не є зв’язним, бо з вершини V₁ у вершину V₄ існує орієнтований шлях, а з вершини V₄ в V₁ такого шляху немає.

Нехай G – граф (неорієнтований чи орієнтований), A – його матриця суміжності, яка відповідає заданій нумерації вершин, тоді кількість різних шляхів довжини r, які з’єднують вершини V_i та V_j, дорівнює елементу a_ij матриці A^r.

Задача про найкоротший шлях

Знайти найкоротший шлях від заданої початкової вершини a до кінцевої вершини z у зв’язному (сильнозв’язному) графі.

З цієї задачі випливають наступні задачі:

1. Знайти найкоротші шляхи від заданої вершини a до всіх інших вершин.

2. Знайти найкоротші шляхи між всіма можливими парами вершин графа.

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

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

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

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

Серед знайдених віддалей знову вибираємо вершину з найменшою віддалю і т. д.

 

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

 

Дерева

1. Поняття «дерево» та його властивості.

2. Рекурсія. Обхід дерев.

3. Форми запису виразів.

Деревом називається зв’язний граф, який не містить простих циклів.

 

 

 

Зауваження

З означення випливає, що дерево є простим графом.

Теорема (еквівалентні означення дерева)

Нехай T – граф, який має n вершин.

Наступні твердження еквівалентні:

1. T – дерево.

2. T - зв’язний граф і має n-1 ребро.

3. T не містить простих циклів і має n-1 ребро.

4. Довільні дві вершини графа T зв’язані одним простим шляхом.

5. T – зв’язний граф, але вилучення довільного його ребра приводить його до незв’язного графа.

Розглянемо поняття кореневого дерева.

Розглянемо T – дерево, v – одна з його вершин.

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

Вершину v називають коренем дерева.

Кореневим деревом називається дерево разом з виділеним коренем (орієнтований граф).

Зауваження

Якщо задано дерево, то при кожному виборі кореня отримують різні кореневі дерева (орієнтовані графи).

 

а) б) в)

а) дерево; б) d – корінь; в) g – корінь;

Нехай T – кореневе дерево.

Батьком вершини u, яка відмінна від кореня дерева, називається така вершина v, що (v u) – ребро орієнтованого графа.

Якщо v батько u, то u – син v.

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

Вершина кореневого дерева, яка не має синів, називається листком.

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

Корінь дерева є внутрішньою вершиною.

Якщо a – вершина дерева, то під піддеревом з коренем a, розуміють граф, що містить a та всі вершини, що є нащадками a, а також ребра, що їх з’єднують.

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

Повним m-арним деревом називається дерево, в якого кожна внутрішня вершина має рівно m синів.

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

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

Приклад

Введемо означення бінарного дерева, використовуючи рекурсію.

Ізольована вершина є бінарним деревом. Нехай A, B – бінарні дерева. Тоді конструкція є бінарним деревом.

 

 

Причому повним, якщо A і B повні бінарні древа.

Зауваження

При означенні рекурсивного об’єкта в основному використовують наступний принцип.

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

Приклад

0!=1

n!=n(n-1)!

В багатьох задачах для знаходження розв’язку потрібно здійснити обхід всіх вершин кореневого дерева.

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

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

 

 

Нехай маємо бінарне кореневе дерево, задане рекурсією.

1. Прямий обхід або обхід зверху вниз задається послідовністю R, A, B.

2. Внутрішній обхід або обхід зліва направо задається A, R, B.

3. Обхід у зворотньому порядку або знизу вверх задається A, B, R.

Приклад

 

 

1. Зверху вниз

dackmnbefsp

2. Знизу вверх

cmnkaespfbd

При використанні алгебраїчних та логічних виразів в програмах виникає проблема їх представлення.

В більшості випадків ці представлення використовують бінарні або m-арні дерева, які представляються у вигляді певних записів.

Приклад

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

При обході дерев, які відповідають деяким виразам, отримують записи, які мають певну назву.

1. Зверху вниз – польський запис (префіксний).

2. Знизу вверх – зворотній польський запис (постфіксний).

Приклад

Польський запис

*+a/bc-d*ef

Зауваження

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

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

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

На останньому кроці отримують значення виразу.

Приклад

Обчислити значення виразу в польському записі.

+-*235/↑234

Крок	Вираз	Виділені символи	Виконані операції
	+-*235/↑234	↑23	2^3=8
	+-*235/84	/84	8/4=2
	+-*2352	*23	3*2=6
	+-652	-65	6-5=1
	+12	+12	1+2=3

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

 

Пошук в деревах

1. Бінарне дерево пошуку.

2. Пошук з поверненням (бектрекінг).

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

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

Для спрощення встановлення вершини дерева з певним іменем (значенням) використовують бінарні дерева пошуку.

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

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

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

Ключ – елемент з деякої лінійно впорядкованої множини.

Бінарне дерево пошуку будують рекурсивно.

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

Ця властивість повторюється рекурсивно для кожної вершини дерева.

Приклад

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

 

Задача про мандрівника

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

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

Приклад 1

Побудувати гамільтонові цикли для графа (мал. 33).

 

 

 

 

 

 

Приклад 2

Розфарбувати граф в 3 кольори.

 

 

 

Задача про ферзів

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

Приклад 3

n=4

 

 

 

Мал. 37.

Алгоритм пошуку з поверненням можна також використати для розв’язання задачі знаходження суми елементів підмножин деякої множини.

Приклад 4

Нехай маємо деяку скінченну множину натуральних чисел A. І задане деяке натуральне число M. Знайти підмножини множини A, сума елементів яких дорівнює M.

 

Відношення

1. Відношення та їх властивості.

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

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

Нехай A, B множини.

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

Зауваження

Відношення з A в B інколи називають бінарним відношенням. А відношення між m множинами називається m-арним відношенням.

Приклад 1

А={1, 2, 3}, B={a, 0}

R={(1,a), (2,0), (3,0)}

Якщо A=B, тоді говорять, що мають відношення на множині А.

Приклад 2

А={1, 2, 3, 4}

R позначає, що A перебуває у відношення з B, якщо A ділить B.

R={(1, 2), (1, 1), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

Кожному відношенню можна поставити і відповідність граф, де ребра графа (дуги) це елементи відношення.

 

 

 

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

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

Приклад 3

A={1, 2, 3, 4}

R₁= {(1,1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}

R₂= {(1, 1), (1, 2), (2, 1)}

R₃= {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}

R₄= {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}

R₅= {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

R₆= {(3, 4)}

R₃, R₅ – рефлексивні відношення.

Відношенням R на множині називається симетричним якщо з того, що aRb випливає bRa.

R₃, R₂ – симетричні відношення.

Відношенням R на множині називається іррефлексивним якщо

R₄, R₆ – іррефлексивні відношення.

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

R₄, R₆ – асиметричне відношення.

Відношення A називається транзитивним, якщо з того, що випливає aRc.

R₄, R₅, R₂ – транзитивні відношення.

Кожне з відношень є рефлексивним чи іррефлексивним, симетричним чи асиметричним.

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

Приклад 4

Відношення на R задане наступним чином:

1. aRa a=a

2. aRb

a=b a=b a=­-b

b=a b=-a

3. aRb bRc aRc

(a=b a=-b) (b=c b=-c)

Використовуючи властивості диз’юнкціїї та кон’юнкції, отримаємо aRc. Отже, задане відношення є відношенням еквівалентності.

Приклад 5

Відношення R на множині дійсних чисел задане:

1.

2. aRb

3. aRb bRc

a – c = (a – b) + (b – c) Z

Дане відношення є відношенням еквівалентності.

Приклад 6

Відношення R на множині цілих чисел, яке задається:

- різниця цих чисел – число, кратне m.

1.

2.

3.

Дане відношення є відношенням еквівалентності.

Нехай R – відношення еквівалентності на множиніA.

Кожний елемент перебуває у відношенні хоча б з одним елементом (рефлективність відношення означає aRa).

Класом еквівалентності елемента a (породженого елементом а) називають множину всіх елементів множини A, які еквівалентні з елементом a.

- клас еквівалентності.

Приклад

Описати класи еквівалентності у відношеннях

aRb

[1] = {1; -1}

[-3,5] = {-3,5; 3,5}

[a] = {a; -a}

[0] = {0}

Зауваження

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

Приклад

Побудувати класи еквівалентності для відношення на Z

Всі решта класів співпадають.

Зауваження

На множині класів еквівалентності можна ввести операції додавання, множення. При цьому будемо мати:

[1]+ [2]= [3] [2]+[4]=[1]

[3]+[2]=[0] [2]*[2]=[4]

[2]*[3]=[1]

 

Нехай R відношення еквівалентності на множині А, тоді еквівалентні наступні співвідношення:

I. aRb

II. [a]=[b]

III.

Нехай R відношення еквівалентності на множині А.

Множину А можна представити у вигляді

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

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

Нехай A, B – множини.

Оскільки відношення R підмножина добутку A´B , то на нього можна розповсюдити операції, які повязані з множинами.

Нехай R₁, R₂ – відношення з множини А на множину В.

Об’єднанням називається відношення, яке задає підмножина декартового добутку:

Приклад

А={1, 2, 3} В={1, 2, 3, 4}

R₁={(1, 1), (2, 2), (3, 3)}

R₂={(1, 2), (1, 1), (1, 3), (1, 4)}

={(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)}

={(1, 1)}

={ (2, 2), (3, 3)}

Зауваження

Відношення з множини А в B можна вважати в певному розумінні деякою функцією.

Нехай R – відношення з A в B, а S – відношення з B в C.

Суперпозицією відношень R та S називають таке відношення , елементами якого є пари (a, c) такі, що існує елемент , де aRb та bRc.

Нехай M₁ і M₂ – булеві матриці однакових розмірів.

Диз’юнкцією мулевих матриць називається булева матриця, елементи якої визначаються

Кон’юнкцією мулевих матриць називається булева матриця, елементи якої визначаються

Об’єднанням відношень (перетин) відповідає диз’юнктивна (кон’юнктивна) булева матриця.

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

Графи

1. Означення та властивості графів.

2. Деякі спеціальні класи простих графів.

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

Простим графом називають пару G=(V,), де V – деяка скінченна непорожня множина елементів, а E – множина невпорядкованих пар різних елементів із V.

Елементи множини V називають вершинами графа, а елементи множини E – ребрами графа.

 

V = {V₁, V₂, V₃, V₄}

E = {{V₁, V₂},{ V₂, V₃},{V₁, V₃},{ V₃, V₄}}

Для зручності ребра позначають e₁ = {V₁, V₂}.

Після того, як додали елемент V₅, отримали інший граф, де V складається з п’яти елементів, а E є тією ж самою множиною, що й для попереднього графа.

Мультиграфом називають пару (V, E), в якій V – скінченна множина, а E – сім’я невпорядкованих пар різних елементів із V.

Під словом сім’я слід розуміти сукупність невпорядкованих пар різних елементів із V, в якій елементи можуть повторюватись.

 

 

V = {V₁, V₂, V₃, V₄, V₅}

E = {{V₁, V₂}, {V₁, V₂}, {V₁, V₂}, {V₂, V₃},{V₂, V₃}, {V₃, V₄}, {V₃, V₄}, {V₃, V₄}, {V₄, V₅}}

Ребра, які з’єднують одні і ті ж вершини, називаються кратними.

Псевдографом називають пару (V, E), в якій V – скінченна непорожня множина вершин, а E – сім’я невпорядкованих пар елементів із V.

 

 

V = {V₁, V₂, V₃, V₄}

E: {V₁, V₂}, {V₁, V₂}, {V₂, V₃},{V₂, V₂}, {V₃, V₃}, {V₃, V₁}, {V₃, V₄}, {V₁, V₃}

Ребра, які з’єднують одну і ту ж саму вершину називаються кратними.

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

Орієнтованим графом називають пару (V, E), де V – скінчена непорожня множина елементів, а E – множина впорядкованих пар елементів з множини V.

 

V = {V₁, V₂, V₃, V₄}

E: {(V₂, V₁), (V₁, V₃), (V₃, V₁),(V₂, V₃), (V₃, V₂),