Розв'язник вправ по дискретній математиці/Графи

Розв'язник вправ по дискретній математиці. Графи

Граф — це сукупність об'єктів та зв'язків між ними.

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

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

Математичне визначення графа

Орієнтований граф з трьома вершинами і трьома ребрами.

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

Граф або неорієнтований граф $G$ — це впорядкована пара $G:=(V,E)$ , для якої виконуються наступні умови:

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

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

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

Орієнтований граф

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

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

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

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

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


Тип графу	Ребра	Кратні ребра
Простий граф	Неорієнтовані	Ні
Мультиграф	Неорієнтовані	Так
Орієнтований граф	Орієнтовані	Ні
Орієнтований мультиграф	Орієнтовані	Так

Завдання 1

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

Побудуйте граф для кожного з наведених нижче відношень на А:

А={a,b,c,d,e}; R={(a,b),(b,a),(b,c),(c,b),(c,a),(a,c),(d,e),(e,d)};
А={a,b,c,d,e}; R={(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(c,a),(a,c)};
А={a,b,c,d,e}; R={(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(d,e),(e,d),(b,e),(e,b),b,d),(d,b)};
А={a,b,c,d}; R={(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(d,a),(a,d),(b,d),(d,b),(a,c),(c,a)};

Рішення:

Пов'язані поняття

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

Способи представлення графів

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