СПОСОБИ ЗАДАННЯ ГРАФІВ. ОПЕРАЦІЇ НАД ГРАФАМИ

3.1 Мета заняття

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

3.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1–8, 10–12] з таких питань: основне визначення графа, елементи графа; неорієнтовані графи та термінологія; орієнтовані графи та термінологія; абстрактні графи та геометричні реалізації; зв’язок графів з відношеннями; «лема про рукостискання»; способи задання графів; матриці суміжності та інциденцій графа; ізоморфізм і гомеоморфізм графів; планарність графів, теорема Понтрягіна-Куратовського; операції вилучення вершин і ребер; операції введення вершини в ребро та операції введення ребра в граф; теоретико-множинні операції над графами.

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

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

Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, поданих у підрозділі 3.3, на основі запропонованих типових прикладів (див. підрозділ 3.4).

3.3 Контрольні запитання і завдання

3.3.1 Контрольні запитання

1. Дайте визначення графу.

2. Який граф називається неорієнтованим? Наведіть приклади.

3. Який граф називається орієнтованим? Наведіть приклади.

4. Який граф називається порожнім?

5. Дайте визначення повного графа. Наведіть приклади.

6. Які вершини є суміжними в графі?

7. Які вершини й ребра інцидентні в графі. Наведіть приклади.

8. Дайте визначення абстрактного орієнтованого графа.

9. Перелічіть способи задання графів.

10. Як можна побудувати матрицю суміжності графа? Наведіть приклад.

11. Що таке матриця інциденцій графа? Наведіть приклад матриці інциденцій для неорієнтованого та орієнтованого графів.

12. Поясніть геометричний спосіб задання графа.

13. Чому дорівнює для орієнтованого графа сума півстепенів «виходу і заходу»?

14. Поясніть поняття маршруту в графі.

15. Дайте визначення шляху в графі.

16. Дайте визначення циклу в графі.

17. Прокоментуйте використання «леми про рукостискання».

18. Який граф називається зв’язним?

19. Як визначити степінь вершини графа?

20. Який граф називається деревом?

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

22. Дайте характеристику та приклад виконання операції вилучення ребер графа, операції вилучення вершини графа.

23. Який граф називається доповненням графа ?

24. У якій формі може бути виконана операція об’єднання графів?

25. Що є операцією перетину графів і які властивості вона має?

26. Як визначити композицію графів и ? Наведіть приклад.

27. Дайте характеристику операції з’єднання графів.

3.3.2 Контрольні завдання

Завдання 1. Побудувати всі графи на п’яти, чотирьох і трьох вершинах.

Завдання 2. Побудувати повний граф з чотирма вершинами. Знайти всі його підграфи. Знайти його частини, що містять 5, 4, 3, 2, 1 ребро. Які знайдені частини є підграфами, а які ні?

Завдання 3. Побудувати доповнення до графів, зображені на рис 3.1, визначити степені вершин графів та їх доповнень.

Рисунок 3.1

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

а) б)

Рисунок 3.2

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

.

Побудувати доповнення цих графів та їхніх матриць суміжності та інциденцій.

Завдання 6. Для графів, зображенb[ на рис. 3.2, скласти матриці суміжності та інциденцій. Використовуючи ці матриці, підрахувати степені вершин графів, півстепені «виходу і заходу» для вершин орієнтованого графа.

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

.

Завдання 8. Довести ізоморфізм графів, які зображені на рис. 3.1.

Завдання 9. Довести неізоморфність графів і , де

, ,

, .

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

Рисунок 3.3

Завдання 11. Довести, що граф непланарний, якщо ,

.

Завдання 12. На рис. 3.4 наведені графи і . Знайти і .

Рисунок 3.4 – Графи і , для яких визначається і

Завдання 13. На рис. 3.5 наведені графи і . Знайти і .

Рисунок 3.5 – Графи і , для яких визначається і

Завдання 14. На рис. 3.6 зображені графи і . Знайти композицію графів і .

Рисунок 3.6 – Графи, для яких визначається композиція і

3.4 Приклади аудиторних і домашніх завдань

Завдання 1. Визначити степінь кожної вершини графа , який зображений на рис 3.7. Побудувати його доповнення.

Рисунок 3.7 – Граф

Розв’язок. Степені вершин визначаються кількістю ребер, які їй інцидентні. Тому: ; ; ; ; ; .

Доповнення графа будується так: з повного графа на 6-ти вершинах вилучаються ті ребра, які належать графу . На рис. 3.8, а) ребра графа позначені пунктиром.

а) б)

Рисунок 3.8 – Граф (а) і доповнення графа (б)

Перевірити правильність побудови можна так: сума степенів однойменних вершин графа і його доповнення дорівнює 5 (степінь вершин графа ).

Завдання 2. Для кожної вершини орієнтованого графа , зображеного на рис. 3.9, визначити півстепені «виходу і заходу» (додатний степінь і від’ємний степінь), степінь вершини.

Рисунок 3.9 – Орієнтований граф

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

Для графа додатні степені усіх вершин такі: , , , . Від’ємні степені усіх вершин графа такі: , , , . Степені вершин графа : , ,

, .

Завдання 3. Побудувати матриці суміжності та інциденцій для неорієн-
тованого графа й орієнтованого графа (рис. 3.10 а) та б) відповідно).

а) б)

Рисунок 3.10 – Графи і

Розв’язок. Будуємо матрицю суміжності графа , рядки й стовпці якої позначаємо вершинами графа (табл. 3.1).

Таблиця 3.1 – Матриця суміжності неорієнтованого графа

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

Матриця інциденцій будується таким чином: рядки її відповідають вершинам, стовпці – ребрам графа (табл. 3.2). Елемент дорівнює 1, якщо вершина інцидентна ребру, і 0 – у протилежному випадку.

Таблиця 3.2 – Матриця інциденцій неорієнтованого графа

У кожному стовпці повинні перебувати тільки 2 одиниці. Сума чисел у рядку дорівнює степеню вершини.

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

Таблиця 3.3 – Матриця суміжності орієнтованого графа

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

Матриця інциденцій будується так: рядки її відповідають вершинам, стовпці – ребрам графа (табл. 3.4). Елемент дорівнює 1, якщо вершина
є початком дуги, (–1) – якщо вершина – кінець дуги, і 0 – якщо вершини й
дуга не інцидентні.

Сума чисел у стовпці дорівнює нулю.

Таблиця 3.4 – Матриця інциденцій орієнтованого графа

Завдання 4. Використовуючи матрицю суміжності (табл. 3.5), побудувати діаграму графа і визначити, чи є він орієнтованим або неорієнтованим.

Таблиця 3.5 – Матриця суміжності графа

Розв’язок. Матриця суміжності несиметрична, тому граф орієнтований. Кількість вершин – 6. Будуємо граф: з вершини 1 ведуть дуги у вершини 2 і 3;
з вершини 2 – у вершини 3 і 6; з вершини 3 – у вершину 4; з вершини 4 – у вершини 1, 5 і 6; з вершини 5 – у вершину 2; з вершини 6 – у вершину 1.

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

Рисунок 3.11 – Граф

Завдання 5. Використовуючи матрицю інциденцій (табл. 3.6), побудувати діаграму графа і визначити, чи є він орієнтованим або неорієнтованим.

Таблиця 3.6 – Матриця інциденцій графа

Розв’язок. У матриці немає значень (-1), тому можна зробити висновок про те, що граф неорієнтований. Кількість вершин дорівнює 6, кількість ребер – 7. Будуємо порожній граф на шести вершинах і з’єднуємо їх ребрами: ребро з’єднує вершини 1 і 4, ребро – вершини 2 і 4 і т.д. Граф, що відповідає матриці інциденцій (табл. 3.6), зображений на рис. 3.12.

Рисунок 3.12 – Граф

Завдання 6. Довести ізоморфізм графів і , де , ,

,

.

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

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

Рисунок 3.13 – Графи і

Розв’язок. У графі присутні всі вершини й усі дуги графів і . Так само, як в об’єднанні множин, елементи, що повторюються, використовуємо один раз. У графі присутні ті вершини й ті дуги графів і , які є й у графі , й у графі . На рис. 3.14, а) зображені результати об’єднання, на рис. 3.14, б) – перетину графів і .

а) б)

Рисунок 3.14 – Об’єднання й перетин графів і

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

Матриця суміжності результуючого графа утвориться поелементним логічним множенням матриць суміжності графів і .

Композиція графів будується так: виписуються всі дуги графа й відповідні їм дуги графа , у результуючий граф включа-
ються дуги , крім повторюваних (у цьому випадку, дуга (1,3) (рис. 3.15).

(1,1)	(1,3)	(1,3)
(1,1)	(1,4)	(1,4)
(1,2)	(2,1)	(1,1)
	(2,3)	(1,3)
(2,3)	–
(2,4)	(4,3)	(2,3)
(4,3)	–

Рисунок 3.15 – Композиція графів

Граф зображений на рис. 3.16. Матриця суміжності графа будується множенням матриці суміжності графа на матрицю суміжності графа .

Рисунок 3.16 – Граф

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

(1,3)	–
(1,4)	(4,3)	(1,3)
(2,1)	(1,1)	(2,1)
	(1,2)	(2,2)
(4,3)	–

Рисунок 3.17 – Композиція графів

Результуючий граф зображений на рис. 3.18.

Рисунок 3.18 – Граф

Матриця суміжності графа будується множенням матриці суміжності графа на матрицю суміжності графа .

Операція композиції не є комутативною, графи й неізоморфні.

Завдання 8. На рис. 3.19 наведені графи і . Знайти і .

Рисунок 3.19 – Графи і

Розв’язок. Об’єднанням графів і називається граф . Тому множина вершин складається з чотирьох вершин. До множини дуг додаємо дві дуги и . Тоді граф має вид, що зображено на рис. 3.20, а).

Рисунок 3.20 – Графи і

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

Завдання 9. Для графів і , зображених на рис. 3.21, виконати операцію диз’юнктивного об’єднання.

Рисунок 3.21 – Графи і

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

Рисунок 3.22 – Результат операції диз’юнктивного об’єднання графів і

Завдання 10. Для графів і , які представлено на рис. 3.23, виконати операцію з’єднання (сильного добутку).

Рисунок 3.23 – Графи і , для яких виконується операція з’єднання

Розв’язок. З’єднанням (сильним добутком) графів і (за умови , ) називається такий граф , що , а .

Результат операції з’єднання графів і (позначається ) зображений на рис. 3.24.

Рисунок 3.24 – Результат операції з’єднання графів і ()

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

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

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: