Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - Графы - файл 1.doc


Лекции - Графы
скачать (518.5 kb.)

Доступные файлы (1):

1.doc519kb.19.11.2011 14:43скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Графи

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

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

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

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

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




V = {V1, V2, V3, V4}

E = {{V1, V2},{ V2, V3},{V1, V3},{ V3, V4}}

Для зручності ребра позначають e1 = {V1, V2}.

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

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

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




V = {V1, V2, V3, V4, V5}

E = {{V1, V2}, {V1, V2}, {V1, V2}, {V2, V3},{V2, V3}, {V3, V4}, {V3, V4}, {V3, V4}, {V4, V5}}

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

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



V = {V1, V2, V3, V4}

E : {V1, V2}, {V1, V2}, {V2, V3},{V2, V2}, {V3, V3}, {V3, V1}, {V3, V4}, {V1, V3}

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

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

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



V = {V1, V2, V3, V4}

E : {(V2, V1), (V1, V3), (V3, V1),(V2, V3), (V3, V2), (V3, V3), (V4, V3)}

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

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




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

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

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

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




Для V1 суміжні V2, V3, V4. Для V4 суміжні V1, V2. V1 інцидентна з ребрами e1, e4, e5, а V3 - з ребрами e4, e2.

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







deg(V1)=4, deg(V2)=4, deg(V3)=4, deg(V4)=3, deg(V5)=3.

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




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

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

M=9 =18

Нехай G=(V1, E1), H=( V2, E2) прості графи.

Граф G називається підграфом H, якщо V1 V2, E1 E2.
Об’єднанням двох простих графів G(V1, E1), H( V2, E2) називається граф W=(V, E), в якого

V=V1V2, E = E1 E2

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




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

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

  1. V=V1V2, V1V2=

  2. кожне ребро з’єднує вершини з V1 та V2.



V = {V1, V2, V3, V4}

V1 = {V1, V2}, V2 = {V3, V4}

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

Повний дводольний граф позначать Km, n, де m – кількість вершин множини V1, а n – кількість вершин множини V2.
Повний дводольний граф K2, 3.



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




Зірка K1, 4.

Зауваження

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

Циклом Cn (n3) називається граф з множиною вершин V = {V1, V2, … , Vn} та множиною ребер E={{V1, V2}, {V2, V3}, … , {Vn-1, Vn}, {Vn, V1}}.





V4



Цикли C4.

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

W4

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

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

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

Нехай G = (V, E) простий граф з множиною вершин V = {V1, V2, … , Vn} і множиною ребер E={e1, e2, … , em}.

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



Приклад




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

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



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

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

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



Приклад





Зауваження

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

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

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

Нехай G = (V, E) простий граф, в якому n вершин.

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



Приклад


Матриця суміжності – симетрична для простого графа. По головній діагоналі розміщені нулі.

Для псевдографа матрицю суміжності будують аналогічно, причому aij=k, якщо ребро {Vi, Vj} має кратність k, aii=1 (m), якщо в вершині Vi є петля (кратності m).

Для орієнтованого графа також використовують матрицю суміжності, яка визначається наступним чином:



Якщо в орієнтованому графі є кратні дуги, тоді елемент aij дорівнює кількості кратних дуг, що починаються у вершині Vi і закінчуються в Vj.


Зауваження

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

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

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





V1

V2

V1

V3

V1

V4

V2

V3

V4

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


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

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

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

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

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

e1={x0, x1}, e2={x1, x2},…, er={xr-1, xr}, x0=u, xr=v

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

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

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



V1V5V6 – простий шлях.

V1V2V5V4V1V2 – не простий шлях.

V1V5V4V1 – простий цикл.

V1V2V3V4V5V2V1 – не простий цикл.

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

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

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

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

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




V1 і V2 не можна з’єднати шляхом.

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

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

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

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

e1=(x0, x1), e2=(x1, x2),…, er=(xr-1, xr), x0=u, xr=v.

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

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



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

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

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

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

^ Задача про Кенінгсберські мости



Чи можна з будь-якої частини міста повернутися назад, пройшовши кожен із мостів один раз?

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



Мовою графів задача про Кенінгсберські мости формулюється:

Чи існує в мультографі простий цикл, який містить всі його ребра?

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

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

Зваженим називається простий граф, в якому кожному ребру e відповідає деяке число w(e), яке називається його вагою.

В більшості випадків число w(e) вважають додатнім.

Зваженим орієнтованим графом називається граф, в якому кожній дузі e ставиться у відповідність число w(e).

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

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

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

Знайти найкоротший шлях від заданої початкової вершини 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

Крок

Вираз

Виділені символи

Виконані операції

1

+-*235/↑234

↑23

23=8

2

+-*235/84

/84

8/4=2

3

+-*2352

*23

3*2=6

4

+-652

-65

6-5=1

5

+12

+12

1+2=3

6

3







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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад

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

  1. Починаємо з кореня дерева.

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

  3. Якщо об’єкт більший від ключа кореня, то переходимо до правого сина.

  4. Якщо об’єкт дорівнює (співпадає) ключу кореня, то він знайдений.

  5. Повторюючи кроки 1-4 отримуємо або наявність об’єкта в дереві пошуку або його відсутність.

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

Суть алгоритму пошуку з поверненням

Нехай розв’язком задачі є множина елементів (x1, x2, … , xn) – впорядкована.

Пошук починають з порожньої послідовності (порожньої множини - ).

Нехай знайдені на i-ому кроці значення (x1, x2, … , xi) – деякі часткові розв’язки.

На i+1 кроці вибирають (знаходять) таке xi+1, яке не виключає можливість того, що набір (x1, x, … , xi, xi+1) можна продовжити до повного розв’язку.

Якщо таке значення xi+1 знайдено, то цей процес продовжують для набору (x1, x, … , xi, xi+1). Якщо ж такого значення xi+1 не існує, тобто не знайдено, тоді повертаємося до послідовності (x1, x2, … , xi-1) і знаходимо ще невикористане значення xi′ таке, що набір (x1, x2, … , xi-1, xi′) можливо можна продовжити до певного розв’язку.

І за скінчену кількість кроків знаходять розв’язок задачі. Або вдалося знайти набір (x1, x2, … , xn), або встановити, що задача не має розв’язку.

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

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

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

Приклад 1

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










^ Задача про розфарбування графа в n кольорів

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

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

Встановлено, що кожний такий граф можна розфарбувати в 4 кольори.

Ідея використання пошуку з поверненням для розфарбування графа

a, b, c – вершини графа.

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

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

Приклад 2

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




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

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

Алгоритм розв’язку з використанням бектрекінгу

  1. Починають з порожньої шахівниці. Нехай в k перших стовпчиках ферзі розставлено. На k+1 кроці ставлять ферзя на першій верхній клітинці k+1 стовпчика.

  2. Якщо k+1 ферзів не б’ють один одного, то переходять до наступного кроку. Якщо це не так, то ферзя в k+1 стовпчику ставлять в другій верхній клітинці і т. д.

  3. В тому випадку, коли ферзя не можна розмістити в жодній клітинці k+1 стовпчика, повертаються до k – ого кроку. Переміщають ферзя в k-ому стовпчику на одну клітинку вниз і переходять до k+1 кроку. Якщо таке переміщення ферзя не дає змогу розмістити його в k+1 стовпчику, тоді ферзя на k-ому стовпчику переміщають на ще одну клітинку вниз.

Приклад 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}

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

R2= {(1, 1), (1, 2), (2, 1)}

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

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

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

R6= {(3, 4)}

R3, R5 – рефлексивні відношення.

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

R3, R2 – симетричні відношення.

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

R4, R6 – іррефлексивні відношення.

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

R4, R6 – асиметричне відношення.

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

R4, R5, R2 – транзитивні відношення.

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

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

Приклад 4

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



  1. aRa a=a

  2. aRb

a=b a=b a=­-b

b=a b=-a

  1. aRb bRc aRc

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

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

Приклад 5

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





  1. aRb



  1. aRb bRc



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

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

Приклад 6

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



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











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

Нехай 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 відношення еквівалентності на множині А, тоді еквівалентні наступні співвідношення:

  1. aRb

  2. [a]=[b]



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

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



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

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

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

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

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

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



Приклад

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

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

R2={(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.



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

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



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



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

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


Скачать файл (518.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru