Лекція №17. Операції над графами
Питання для самоперевірки та вправи
1. Які ви знаєте способи машинного представлення графа ? В яких випадках доцільно використовувати кожний спосіб ?
2. Намалюйте довільний граф, позначте його вершини і ребра. Дайте матричну інтерпретацію цього графа.
3. Дайте машинну інтерпретацію графа, створеного в пункті 2. Обгрунтуйте вибраний спосіб.
4. Створіть схему з полем зв'язків для графа, створеного в пункті 2.
Об’єднання, переріз, сума та різниця графів
Декартовий добуток графів
Композиція графів
Нехай і - два орієнтованих графа, множини вершин і множини ребер цих графів не перетинаються.
Об’єднанням графів називається граф , вершинами якого є множина , а відображення .
Наприклад:
: | : |
Тоді об’єднанням графів буде граф:
Перерізом графів і називається граф , для якого виконуються умови , .
Наприклад:
Розглянемо переріз графів, зображених у попередніх прикладах:
Одержимо граф
Різницею графів і називається граф , для якого виконуються умови , , тобто, якщо, наприклад, множина вершин деякого графа і , то .
Різниця графів, розглянутих у попередніх прикладах буде: , . Одержимо:
Композиція графів визначається по таким правилам:
1. Вершинами результуючого графа є множина .
2. Відображення кожної вершини визначається .
Наприклад:
Створимо граф , як композицію графів :
Побудова декартового добутку визначається таким правилом:
1. Вершини графа одержуємо шляхом послідовного сполучення кожної з вершин першого графа з кожною з вершин другого графа . Отже, в графі кожна вершина має двохзначне позначення. Загальна кількість вершин графа дорівнює добутку вершин графів , так, наприклад, якщо маємо множини вершин , , тоді .
2. Відображення кожної вершини в декартовому добутку графів одержуємо шляхом можливих сполучень кожного з відображень графа з кожним з відображень графа для відповідних вершин. Загальна кількість відображень для кожної вершини графа дорівнює добутку числа відображень графів та для відповідних вершин, тобто
Наприклад:
Визначити відображення для вершини, якщо відомо ,
.
Розглянемо приклад:
Сумою графів і називається граф , який визначається по таким правилам:
1. Вершини графа визначаються аналогічно декартовому добутку .
2. Відображення для будь-якої вершини графа одержують шляхом об’єднання двох сполучень, одне з яких одержане відображенням вершини графа і вершиною графа , а друге - вершиною графа і відображенням вершини графа : .
Наприклад:
Треба визначити образ , якщо виконуються умови , . Визначимо можливі сполучення з і з .
Для прикладу визначимо суму графів які розглядались для визначення їх декартового добутку:
.
Подальшу побудову графа пропонуємо читачеві.
Операції над неорієнтованими графами
Розглянемо операції над графами і , які мають множини вершин і і множини ребер і , які не перетинаються. Тоді визначені такі операції:
Операція | Число вершин | Число ребер |
Об’єднання | ||
З’єднання + | ||
Добуток | ||
Композиція |
Наприклад: Об’єднання:
З’єднання: Добуток:
Вершини і суміжні в тоді і тільки тоді, коли і або .
Композиція:
Вершина суміжна з тоді і тільки тоді, коли або і .