Білоруський державний університет інформатики і радіоелектроніки
Кафедра інформатики
РЕФЕРАТ
На тему:
«Операції на графах»
МІНСЬК, 2008
Операції на графах дозволяють утворювати нові графи з декількох більш простих. У цьому параграфі будуть розглянуті операції на графах без паралельних ребер (дуг).
Об'єднання графів.
Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - довільні графи. Об'єднанням G 1 È G 2 графів G 1 і G 2 називається граф з множиною вершин X 1 È X 2, і з безліччю ребер (дуг) E 1 È E 2.
Розглянемо операцію на прикладі графів G 1 (X 1, E 1) і G 2 (X 2, E 2), наведених на рис. 4.1. Множини вершин першого і другого графів відповідно рівні X 1 = {x 1, x 2, x 3} і X 2 = {x 2, x 3, x 4}, а безліч вершин результуючого графа визначиться як X = X 1 È X 2 = {x 1, x 2, x 3, x 4}. Аналогічно визначаємо безлічі дуг графа:
E 1 = {(x 1, x 2), (x 1, x 3), (x 2, x 1), (x 3, x 3)}. E 2 = {(x 2, x 4), ( x 3, x 2), (x 4, x 2)}.
E = {(x 1, x 2), (x 1, x 3), (x 2, x 1), (x 3, x 3), (x 2, x 4), (x 3, x 2) , (x 4, x 2)}.
Результуючий граф G (X, E) = G 1 (X 1, E 1) ÈG 2 (X 2, E 2) також наведено на рис. 1.
Операція об'єднання має такі властивості, які випливають з визначення операції і властивостей операцій на множинах:
G 1 È G 2 = G 2 È G 1 - властивість комутативності;
G 1 È (G 2 È G 3) = (G 1 È G 2) È G 3 - властивість асоціативності.
Операція об'єднання графів може бути виконана в матричній формі. Для графів з одним і тим же безліччю вершин справедлива наступна теорема.
Теорема 1. Нехай G 1 і G 2 - два графа (орієнтовані чи не орієнтовані одночасно) з одним і тим же безліччю вершин X, і нехай A 1 і A 2 - матриці суміжності вершин цих графів. Тоді матрицею суміжності вершин графа G 1 È G 2 є матриця A = A 1 È A 2, утворена поелементний логічним складанням матриць A 1 і A 2.
Розглянемо виконання операції об'єднання графів, безлічі вершин яких не збігаються. Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - графи без паралельних ребер і безлічі X 1 і X 2 вершин цих графів не збігаються. Нехай A 1 і A 2 - матриці суміжності їх вершин графів. Для таких графів операція об'єднання може бути виконана наступним чином.
Відповідно до визначення операції об'єднання графів знайдемо безліч вершин результуючого графа як X 1 È X 2. Побудуємо допоміжні графи G '1 і G' 2, безлічі вершин яких є безліч X 1 È X 2, а безліч ребер (дуг) визначається множинами E 1 для графа G '1 і E 2 для графа G' 2. Очевидно, що матриці A '1 і A' 2 суміжності вершин цих графів можуть бути отримані з матриць A 1 і A 2 шляхом додавання в них додаткових стовпців і рядків з нульовими елементами.
Застосувавши до графів G '1 і G' 2 теорему 4.1, знайдемо матрицю суміжності вершин графа G '1 È G' 2 як A '1 È A' 2. Очевидно, що отриманої матриці суміжності вершин відповідає граф, множина вершин якого дорівнює X 1 È X 2, а безліч ребер визначається, як E 1 È E 2, що відповідає операції об'єднання графів.
Приклад 1. Виконати в матричній формі операцію об'єднання графів G 1 і G 2, представлених на рис. 1.
Складемо матриці суміжності вершин графів.
Безліч вершин результуючого графа X 1 È X 2 = {x 1, x 2, x 3, x 4}. Складемо матриці суміжності вершин допоміжних графів G '1 і G' 2.
Матриця A = A '1 È A' 2 має вигляд
Отримана матриця суміжності вершин A '1 È A' 2 відповідає графу G 1 È G 2, зображеному на рис.1.
Перетин графів
Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - довільні графи. Перетином G 1 Ç G 2 графів G 1 і G 2 називається граф з множиною вершин X 1 Ç X 2 з безліччю ребер (дуг) E = E 1 Ç E 2
Операція перетину має такі властивості, які випливають з визначення операції і властивостей операцій на множинах:
G 1 Ç G 2 = G 2 Ç G 1 - властивість комутативності;
G 1 Ç (G2 Ç G3) = (G1 Ç G2) Ç G 3 - властивість асоціативності.
Для того щоб операція перетину була всеосяжною, необхідно ввести поняття порожнього графа. Граф G (X, E) називається порожнім, якщо множина X вершин графа є порожнім (X = Æ). Зауважимо, що в цьому випадку і безліч E ребер (дуг) графа також порожня множина (E = Æ). Порожній граф позначається символом Æ. Такий граф може бути отриманий в результаті виконання операції перетину графів, у яких X 1 Ç X 2 = Æ. У цьому випадку говорять про непересічних графах.
Розглянемо виконання операції перетину графів, зображених на рис. 2. Для знаходження безлічі вершин результуючого графа запишемо безлічі вершин вихідних графів і виконаємо над цими множинами операцію перетину:
X 1 = {x 1, x 2, x 3}; X 2 = {x 1, x 2, x 3, x 4};
X = X 1 Ç X 2 = {x 1, x 2, x 3}.
Аналогічно визначаємо безліч E дуг результуючого графа:
E 1 = {(x 1, x 2), (x 1, x 3), (x 2, x 1), (x 2, x 3), (x 3, x 2)};
E 2 = {(x 1, x 3), (x 2, x 1), (x 2, x 3), (x 2, x 4), (x 3, x 1)};
E = E 1 Ç E 2 = {(x 1, x 3), (x 2, x 1)}.
Графи G 1 (X 1, E 1), G 2 (X 2, E 2) та їх перетин наведено на рис 4.2.
Операція перетину графів може бути виконана в матричній формі.
Теорема 2. Нехай G 1 і G 2 - два графа (орієнтовані або неорієнтовані одночасно) з одним і тим же безліччю вершин X, і нехай A 1 і A 2 - матриці суміжності вершин цих графів. Тоді матрицею суміжності вершин графа G1 Ç G2 є матриця A = A 1 Ç A 2 утворена поелементний логічно множенням матриць A 1 і A 2.
Розглянемо виконання операції перетину для графів з незбіжним безліччю вершин.
Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - графи без паралельних ребер, безлічі X 1 і X 2 вершин графів не збігаються, а A 1 і A 2 - матриці суміжності вершин графів. Для таких графів операція перетину може бути виконана так.
Відповідно до визначення операції перетину графів знайдемо безліч вершин результуючого графа як X 1 Ç X 2. Побудуємо допоміжні графи G '1 і G' 2, безлічі вершин яких є безліч X 1 Ç X 2, а безліч ребер (дуг) визначається множинами E '1 і E' 2 всіх ребер (дуг), інцидентних цих вершин. Очевидно, що матриці A '1 і A' 2 суміжності вершин цих графів можуть бути отримані з матриць A 1 і A 2 шляхом видалення з них стовпців і рядків, які відповідають вершинам, котрі ввійшли в безліч X1 Ç X2.
Застосувавши до графів G '1 і G' 2 теорему 2, знайдемо матрицю суміжності вершин графа G '1 Ç G' 2 як A '1 Ç A' 2. Очевидно, що отриманої матриці суміжності вершин відповідає граф, множина вершин якого дорівнює X 1 Ç X 2, а безліч ребер визначається, як E 1 Ç E 2, що відповідає операції перетину графів.
Приклад 2. Виконати в матричній формі операцію перетину графів G 1 і G 2, представлених на рис. 2.
Складемо матриці суміжності вершин вихідних графів.
Знаходимо безліч вершин X результуючого графа.
X = X 1 Ç X 2 = {x 1, x 2, x 3}.
Складемо матриці суміжності вершин допоміжних графів G '1 і G' 2.
Знайдемо матрицю суміжності вершин A = A 1 Ç A 2
Отримана матриця суміжності вершин A '1 Ç A' 2 відповідає графу G 1 Ç G 2, зображеному на рис.2.
Композиція графів
Нехай G 1 (X, E 1) і G 2 (X, E 2) - два графа з одним і тим же безліччю вершин X. Композицією G 1 (G 2) графів G 1 і G 2 називається граф з множиною вершин E, в якому існує дуга (x i, x j) тоді і тільки тоді, коли існує дуга (x i, x k), що належить безлічі E 1, і дуга (x k, x j), що належить безлічі E 2.
Розглянемо виконання операції композиції G 1 (G 2) на графах, зображених на рис.3. Для розгляду операції складемо таблицю, в першому стовпці якої вказуються ребра (x i, x k), що належать графу G 1, у другому - ребра (x k, x j), що належать графу G 3, а в третьому - результуюче ребро (x i, x j) для графа G 1 (G 2).
Зауважимо, що дуга (x 1, x 3) результуючого графа в таблиці зустрічається двічі. Однак, оскільки розглядаються графи без паралельних ребер (дуг), то в безлічі E результуючого графа дуга (x 1, x 3) враховується тільки один раз, тобто E = {(x 1, x 1), (x 1, x 3), (x 2, x 1), (x 2, x 3)}
На рис. 3 зображені графи G 1 і G 2 та їх композиції G 1 (G 2). На цьому ж малюнку зображено граф G 2 (G 1). Рекомендується самостійно побудувати граф G 2 (G 1) і переконатися, що графи G 1 (G 2) і G 2 (G 1) не ізоморфні.
Нехай А 1 і A 2 - матриці суміжності вершин графів G 1 (X, E 1) і G (X, E 2) відповідно. Розглянемо матрицю A 12 елементи a ij якої обчислюється так:
n
a ij = Ú a 1 ik Ù a 2 kj (1)
k = 1
де a 1ik і a 2kj - елементи матриці суміжності вершин першого і другого графів відповідно. Елемент a ij дорівнює 1, якщо в результуючому графі G 1 (G 2) існує дуга, яка виходить із вершини x i і заходить x j, і нулю - в іншому випадку.
Приклад 3. Виконати операцію композиції для графів, представлених на рис. 3.
Складемо матриці суміжності вершин графів:
Обчисливши елементи матриці згідно (1), отримуємо:
Неважко переконатися, що отриманим матрицями суміжності вершин відповідають графи G 1 (G 2) і G 2 (G 1), що представлені на рис. 3.
Декартово твір графів. Нехай G 1 (X, E 1) і G 2 (Y, E 2) - два графа. Декартовим твором G 1 (X, E 1) 'G 2 (Y, E 2) графів G 1 (X, E 1) і G 2 (X, E 2) називається граф з множиною вершин X' Y, в якому дуга ( ребро), що йде з вершини (x i y j) в (x k y l), існує тоді і тільки тоді коли існує дуга (x i x k), що належить безлічі дуг E 1 і j = l або коли існує дуга (y j, y l), що належить безлічі E 2 і i = k.
Виконання операції декартового добутку розглянемо на прикладі графів, зображених на рис. 4. Безліч вершин Z результуючого графа визначається як декартово добуток множин X 'Y. Безліч Z містить такі елементи: z 1 = (x 1 y 1), z 2 = (x 1 y 2), z 3 = (x 1 y 3), z 4 = (x 2 y 1), z 5 = ( x 2 y 2), z 6 = (x 2 y 3).
Кафедра інформатики
РЕФЕРАТ
На тему:
«Операції на графах»
МІНСЬК, 2008
Операції на графах дозволяють утворювати нові графи з декількох більш простих. У цьому параграфі будуть розглянуті операції на графах без паралельних ребер (дуг).
Об'єднання графів.
Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - довільні графи. Об'єднанням G 1 È G 2 графів G 1 і G 2 називається граф з множиною вершин X 1 È X 2, і з безліччю ребер (дуг) E 1 È E 2.
Розглянемо операцію на прикладі графів G 1 (X 1, E 1) і G 2 (X 2, E 2), наведених на рис. 4.1. Множини вершин першого і другого графів відповідно рівні X 1 = {x 1, x 2, x 3} і X 2 = {x 2, x 3, x 4}, а безліч вершин результуючого графа визначиться як X = X 1 È X 2 = {x 1, x 2, x 3, x 4}. Аналогічно визначаємо безлічі дуг графа:
E 1 = {(x 1, x 2), (x 1, x 3), (x 2, x 1), (x 3, x 3)}. E 2 = {(x 2, x 4), ( x 3, x 2), (x 4, x 2)}.
E = {(x 1, x 2), (x 1, x 3), (x 2, x 1), (x 3, x 3), (x 2, x 4), (x 3, x 2) , (x 4, x 2)}.
Результуючий граф G (X, E) = G 1 (X 1, E 1) ÈG 2 (X 2, E 2) також наведено на рис. 1.
Операція об'єднання має такі властивості, які випливають з визначення операції і властивостей операцій на множинах:
G 1 È G 2 = G 2 È G 1 - властивість комутативності;
G 1 È (G 2 È G 3) = (G 1 È G 2) È G 3 - властивість асоціативності.
Операція об'єднання графів може бути виконана в матричній формі. Для графів з одним і тим же безліччю вершин справедлива наступна теорема.
Теорема 1. Нехай G 1 і G 2 - два графа (орієнтовані чи не орієнтовані одночасно) з одним і тим же безліччю вершин X, і нехай A 1 і A 2 - матриці суміжності вершин цих графів. Тоді матрицею суміжності вершин графа G 1 È G 2 є матриця A = A 1 È A 2, утворена поелементний логічним складанням матриць A 1 і A 2.
Розглянемо виконання операції об'єднання графів, безлічі вершин яких не збігаються. Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - графи без паралельних ребер і безлічі X 1 і X 2 вершин цих графів не збігаються. Нехай A 1 і A 2 - матриці суміжності їх вершин графів. Для таких графів операція об'єднання може бути виконана наступним чином.
Відповідно до визначення операції об'єднання графів знайдемо безліч вершин результуючого графа як X 1 È X 2. Побудуємо допоміжні графи G '1 і G' 2, безлічі вершин яких є безліч X 1 È X 2, а безліч ребер (дуг) визначається множинами E 1 для графа G '1 і E 2 для графа G' 2. Очевидно, що матриці A '1 і A' 2 суміжності вершин цих графів можуть бути отримані з матриць A 1 і A 2 шляхом додавання в них додаткових стовпців і рядків з нульовими елементами.
Застосувавши до графів G '1 і G' 2 теорему 4.1, знайдемо матрицю суміжності вершин графа G '1 È G' 2 як A '1 È A' 2. Очевидно, що отриманої матриці суміжності вершин відповідає граф, множина вершин якого дорівнює X 1 È X 2, а безліч ребер визначається, як E 1 È E 2, що відповідає операції об'єднання графів.
Приклад 1. Виконати в матричній формі операцію об'єднання графів G 1 і G 2, представлених на рис. 1.
Складемо матриці суміжності вершин графів.
| x 1 | x 2 | x 3 | x 2 | x 3 | x 4 | ||||||
| x 1 | 0 | 1 | 1 | x 2 | 0 | 0 | 1 | ||||
| A 1 | = | x 2 | 1 | 0 | 0 | A 2 | = | x 3 | 1 | 0 | 0 |
| x 3 | 0 | 0 | 1 | x 4 | 0 | 1 | 0 |
| x 1 | x 2 | x 3 | x 4 | x 1 | x 2 | x 3 | x 4 | ||||||
| x 1 | 0 | 1 | 1 | 0 | x 1 | 0 | 0 | 0 | 0 | ||||
| A '1 | = | x 2 | 1 | 0 | 0 | 0 | A '2 | = | x 2 | 0 | 0 | 0 | 1 |
| x 3 | 0 | 0 | 1 | 0 | x 3 | 0 | 1 | 0 | 0 | ||||
| x 4 | 0 | 0 | 0 | 0 | x 4 | 0 | 0 | 1 | 0 |
| X 1 | x 2 | x 3 | x 4 | |||
| x 1 | 0 | 1 | 1 | 0 | ||
| x 2 | 1 | 0 | 0 | 1 | ||
| A = A '1 È A' 2 | = | x 3 | 0 | 1 | 1 | 0 |
| x 4 | 0 | 0 | 1 | 0 |
Перетин графів
Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - довільні графи. Перетином G 1 Ç G 2 графів G 1 і G 2 називається граф з множиною вершин X 1 Ç X 2 з безліччю ребер (дуг) E = E 1 Ç E 2
Операція перетину має такі властивості, які випливають з визначення операції і властивостей операцій на множинах:
G 1 Ç G 2 = G 2 Ç G 1 - властивість комутативності;
G 1 Ç (G2 Ç G3) = (G1 Ç G2) Ç G 3 - властивість асоціативності.
Для того щоб операція перетину була всеосяжною, необхідно ввести поняття порожнього графа. Граф G (X, E) називається порожнім, якщо множина X вершин графа є порожнім (X = Æ). Зауважимо, що в цьому випадку і безліч E ребер (дуг) графа також порожня множина (E = Æ). Порожній граф позначається символом Æ. Такий граф може бути отриманий в результаті виконання операції перетину графів, у яких X 1 Ç X 2 = Æ. У цьому випадку говорять про непересічних графах.
Розглянемо виконання операції перетину графів, зображених на рис. 2. Для знаходження безлічі вершин результуючого графа запишемо безлічі вершин вихідних графів і виконаємо над цими множинами операцію перетину:
X 1 = {x 1, x 2, x 3}; X 2 = {x 1, x 2, x 3, x 4};
X = X 1 Ç X 2 = {x 1, x 2, x 3}.
Аналогічно визначаємо безліч E дуг результуючого графа:
E 1 = {(x 1, x 2), (x 1, x 3), (x 2, x 1), (x 2, x 3), (x 3, x 2)};
E 2 = {(x 1, x 3), (x 2, x 1), (x 2, x 3), (x 2, x 4), (x 3, x 1)};
E = E 1 Ç E 2 = {(x 1, x 3), (x 2, x 1)}.
Графи G 1 (X 1, E 1), G 2 (X 2, E 2) та їх перетин наведено на рис 4.2.
Операція перетину графів може бути виконана в матричній формі.
Теорема 2. Нехай G 1 і G 2 - два графа (орієнтовані або неорієнтовані одночасно) з одним і тим же безліччю вершин X, і нехай A 1 і A 2 - матриці суміжності вершин цих графів. Тоді матрицею суміжності вершин графа G1 Ç G2 є матриця A = A 1 Ç A 2 утворена поелементний логічно множенням матриць A 1 і A 2.
Розглянемо виконання операції перетину для графів з незбіжним безліччю вершин.
Нехай G 1 (X 1, E 1) і G 2 (X 2, E 2) - графи без паралельних ребер, безлічі X 1 і X 2 вершин графів не збігаються, а A 1 і A 2 - матриці суміжності вершин графів. Для таких графів операція перетину може бути виконана так.
Відповідно до визначення операції перетину графів знайдемо безліч вершин результуючого графа як X 1 Ç X 2. Побудуємо допоміжні графи G '1 і G' 2, безлічі вершин яких є безліч X 1 Ç X 2, а безліч ребер (дуг) визначається множинами E '1 і E' 2 всіх ребер (дуг), інцидентних цих вершин. Очевидно, що матриці A '1 і A' 2 суміжності вершин цих графів можуть бути отримані з матриць A 1 і A 2 шляхом видалення з них стовпців і рядків, які відповідають вершинам, котрі ввійшли в безліч X1 Ç X2.
Застосувавши до графів G '1 і G' 2 теорему 2, знайдемо матрицю суміжності вершин графа G '1 Ç G' 2 як A '1 Ç A' 2. Очевидно, що отриманої матриці суміжності вершин відповідає граф, множина вершин якого дорівнює X 1 Ç X 2, а безліч ребер визначається, як E 1 Ç E 2, що відповідає операції перетину графів.
Приклад 2. Виконати в матричній формі операцію перетину графів G 1 і G 2, представлених на рис. 2.
Складемо матриці суміжності вершин вихідних графів.
| x 1 | x 2 | x 3 | x 1 | x 2 | x 3 | x 4 | ||||||
| x 1 | 0 | 1 | 1 | x 1 | 0 | 0 | 0 | 1 | ||||
| A 1 | = | x 2 | 1 | 0 | 1 | A 2 | = | x 2 | 1 | 0 | 1 | 1 |
| x 3 | 0 | 1 | 0 | x 3 | 1 | 0 | 0 | 0 | ||||
| x 4 | 0 | 0 | 0 | 0 |
X = X 1 Ç X 2 = {x 1, x 2, x 3}.
Складемо матриці суміжності вершин допоміжних графів G '1 і G' 2.
| x 1 | x 2 | x 3 | x 1 | x 2 | x 3 | ||||||
| x 1 | 0 | 1 | 1 | x 1 | 0 | 0 | 0 | ||||
| A '1 | = | x 2 | 1 | 0 | 1 | A '2 | = | x 2 | 1 | 0 | 1 |
| x 3 | 0 | 1 | 0 | x 3 | 1 | 0 | 0 |
| x 1 | x 2 | x 3 | |||
| x 1 | 0 | 0 | 0 | ||
| A '1 Ç A' 2 | = | x 2 | 1 | 0 | 1 |
| x 3 | 0 | 0 | 0 |
Композиція графів
Нехай G 1 (X, E 1) і G 2 (X, E 2) - два графа з одним і тим же безліччю вершин X. Композицією G 1 (G 2) графів G 1 і G 2 називається граф з множиною вершин E, в якому існує дуга (x i, x j) тоді і тільки тоді, коли існує дуга (x i, x k), що належить безлічі E 1, і дуга (x k, x j), що належить безлічі E 2.
Розглянемо виконання операції композиції G 1 (G 2) на графах, зображених на рис.3. Для розгляду операції складемо таблицю, в першому стовпці якої вказуються ребра (x i, x k), що належать графу G 1, у другому - ребра (x k, x j), що належать графу G 3, а в третьому - результуюче ребро (x i, x j) для графа G 1 (G 2).
| G 1 | G 2 | G 1 (G 2) |
| (X 1, x 2) | (X 2, x 1) (X 2, x 3) | (X 1, x 1) (X 1, x 3) |
| (X 1, x 3) | (X 3, x 3) | (X 1, x 3) |
| (X 2, x 1) | (X 1, x 1) (X 1, x 3) | (X 2, x 1) (X 2, x 3) |
Зауважимо, що дуга (x 1, x 3) результуючого графа в таблиці зустрічається двічі. Однак, оскільки розглядаються графи без паралельних ребер (дуг), то в безлічі E результуючого графа дуга (x 1, x 3) враховується тільки один раз, тобто E = {(x 1, x 1), (x 1, x 3), (x 2, x 1), (x 2, x 3)}
На рис. 3 зображені графи G 1 і G 2 та їх композиції G 1 (G 2). На цьому ж малюнку зображено граф G 2 (G 1). Рекомендується самостійно побудувати граф G 2 (G 1) і переконатися, що графи G 1 (G 2) і G 2 (G 1) не ізоморфні.
Нехай А 1 і A 2 - матриці суміжності вершин графів G 1 (X, E 1) і G (X, E 2) відповідно. Розглянемо матрицю A 12 елементи a ij якої обчислюється так:
n
a ij = Ú a 1 ik Ù a 2 kj (1)
k = 1
де a 1ik і a 2kj - елементи матриці суміжності вершин першого і другого графів відповідно. Елемент a ij дорівнює 1, якщо в результуючому графі G 1 (G 2) існує дуга, яка виходить із вершини x i і заходить x j, і нулю - в іншому випадку.
Приклад 3. Виконати операцію композиції для графів, представлених на рис. 3.
Складемо матриці суміжності вершин графів:
| x 1 | x 2 | x 3 | x 1 | x 2 | x 3 | ||||||
| x 1 | 0 | 1 | 1 | x 1 | 1 | 0 | 1 | ||||
| A 1 | = | x 2 | 1 | 0 | 0 | A 2 | = | x 2 | 1 | 0 | 1 |
| x 3 | 0 | 0 | 0 | x 3 | 0 | 0 | 1 |
| x 1 | x 2 | x 3 | x 1 | x 2 | x 3 | ||||||
| x 1 | 1 | 0 | 2 | x 1 | 0 | 1 | 1 | ||||
A 12 | = | x 2 | 1 | 0 | 1 | A 21 | = | x 2 | 0 | 1 | 1 |
| x 3 | 0 | 0 | 0 | x 3 | 0 | 0 | 0 |
Декартово твір графів. Нехай G 1 (X, E 1) і G 2 (Y, E 2) - два графа. Декартовим твором G 1 (X, E 1) 'G 2 (Y, E 2) графів G 1 (X, E 1) і G 2 (X, E 2) називається граф з множиною вершин X' Y, в якому дуга ( ребро), що йде з вершини (x i y j) в (x k y l), існує тоді і тільки тоді коли існує дуга (x i x k), що належить безлічі дуг E 1 і j = l або коли існує дуга (y j, y l), що належить безлічі E 2 і i = k.
Виконання операції декартового добутку розглянемо на прикладі графів, зображених на рис. 4. Безліч вершин Z результуючого графа визначається як декартово добуток множин X 'Y. Безліч Z містить такі елементи: z 1 = (x 1 y 1), z 2 = (x 1 y 2), z 3 = (x 1 y 3), z 4 = (x 2 y 1), z 5 = ( x 2 y 2), z 6 = (x 2 y 3).
| № п.п. | Групи вершин з співпадаючими компонентами | Дуги для незбіжних компонент | Дуга (X i y j) ® (x k y l) | Дуга (Z a, z b) |
| 1 | z 1 = (x 1 y 1), z 2 = (x 1 y 2), z 3 = (x 1 y 3) | (Y 1, y 1) (Y 1, y 2) (Y 2, y 3) (Y 3, y 1) | (X 1 y 1) ® (x 1 y 1) (X 1 y 1) ® (x 1 y 2) (X 1 y 2) ® (x 1 y 3) (X 1 y 3) ® (x 1 y 1) | (Z 1, z 1) (Z 1, z 2) (Z 2, z 3) (Z 3, z 1) |
| 2 | z 4 = (x 2 y 1), z 5 = (x 2 y 2), z 6 = (x 2 y 3) | (Y 1, y 1) (Y 1, y 2) (Y 2, y 3) (Y 3, y 1) | (X 2 y 1) ® (x 2 y 1) (x 2 y 1) ® (x 2 y 2) (x 2 y 2) ® (x 2 y 3) (x 2 y 3) ® (x 2 y 1) | (Z 4, z 4) (Z 4, z 5) (Z 5, z 6) (Z 6, z 4) |
| 3 | z 1 = (x 1 y 1), z 4 = (x 2 y 1) | (X 1, x 2) (X 2, x 1) | (X 1 y 1) ® (x 2 y 1) (x 2 y 1) ® (x 1 y 1) | (Z 1, z 4) (Z 4, z 1) |
| 4 | z 2 = (x 1 y 2), z 5 = (x 2 y 2) | (X 1, x 2) (X 2, x 1) | (X 1 y 2) ® (x 2 y 2) (x 1 y 2) ® (x 1 y 2) | (Z 2, z 5) (Z 5, z 2) |
| 5 | Z 3 = (x 1 y 3), z 6 = (x 2 y 3) | (X 1, x 2) (X 2, x 1) | (X 1 y 3) ® (x 2 y 3) (x 2 y 3) ® (x 1 y 3) | (Z 3, z 6) (Z 6, z 3) |
Граф G 1 'G 2 зображений на рис. 4.
Операція декартового добутку володіє наступними властивостями.
1. G 1 'G 2 = G 2' G 1
2. G 1 '(G 2' G 3) = (G 1 'G 2)' G 3.
Операція декартового добутку графів може бути виконана в матричній формі.
Нехай G 1 (X, E 1) і G 2 (Y, E 2) - два графа, що мають n x і n y вершин відповідно. Результуючий граф G 1 'G 2 має n x × n y вершин, а його матриця суміжності вершин - квадратна матриця розміром (n x × n y) '(n x × n y). Позначимо через a a b = a (ij) (kl) елемент матриці суміжності вершин, що вказує на наявність дуги (ребра), що з'єднує вершину z a = (x i y j) c z b = (x k y l). Відповідно до визначення операції цей елемент може бути обчислений за допомогою матриць суміжності вершин вихідних графів наступним чином:
a a b = a (ij) (kl) = K ik × a 2, jl Ú K jl × a 1, ik, (2)
де a 1, ik, a 2, jl - елементи матриці суміжності вершин графів G 1 і G 2 відповідно;
K ik - Символ Кронекера, рівний 1, якщо i = k, і нулю, якщо i ¹ k.
Приклад 4. Виконати операцію декартового добутку на графах, наведених на рис. 4.
Складемо матриці суміжності вершин вихідних графів.
| x 1 | x 2 | y 1 | y 2 | y 3 | |||||||
| x 1 | 0 | 1 | y 1 | 1 | 1 | 0 | |||||
| A 1 | = | x 2 | 1 | 0 | A 2 | = | y 2 | 0 | 0 | 1 | |
| y 3 | 1 | 0 | 0 | ||||||||
| x 1 y 1 | x 1 y 2 | x 1 y 3 | x 2 y 1 | x 2 y 2 | x 2 y 3 | |||
| x 1 y 1 | X Ú Y | X | X | Y | 0 | 0 | ||
| x 1 y 2 | X | X ÚY | X | 0 | Y | 0 | ||
| Axy | = | X 1 y 3 | X | X | X ÚY | 0 | 0 | Y |
| X 2 y 1 | Y | 0 | 0 | XÚY | X | X | ||
| X 2 y 2 | 0 | Y | 0 | X | X ÚY | X | ||
| X 2 y 3 | 0 | 0 | Y | X | X | X ÚY |
| x 1 y 1 | x 1 y 2 | x 1 y 3 | x 2 y 1 | x 2 y 2 | x 2 y 3 | |||
| x 1 y 1 | a 1,11 Ú a 2,11 | a 2,12 | a 2,13 | a 1,12 | ||||
| x 1 y 2 | a 2,21 | a 1,11 Úa 2,22 | a 2,11 | a 1,12 | ||||
| A * | = | x 1 y 3 | a 2,31 | A 2,32 | a 1,11 Úa 2,33 | 0 | 0 | a 1,12 |
| x 2 y 1 | a 1,21 | 0 | 0 | a 1,22 Úa 2,11 | a 2,12 | a 2,13 | ||
| x 2 y 2 | 0 | a 1,21 | 0 | a 2,21 | a 1,22 Úa 2,22 | a 2,23 | ||
| x 2 y 3 | 0 | 0 | a 1,21 | a 2,31 | a 2,32 | a 1,22 Ú a 2,33 |
Зауважимо, що в матрицях Axy і A * на головній діагоналі розташовуються елементи, рівні логічної сумі значень елементів матриць суміжності вершин обох графів. Це визначається тим, що на головній діагоналі розташовані елементи, для яких K ik = K jl = 1.
Таким чином, матриця суміжності вершин результуючого графа приймає вигляд:
| x 1 y 1 | x 1 y 2 | x 1 y 3 | x 2 y 1 | x 2 y 2 | x 2 y 3 | |||
| x 1 y 1 | 1 | 1 | 0 | 1 | 0 | 0 | ||
| x 1 y 2 | 0 | 0 | 1 | 0 | 1 | 0 | ||
| A | = | x 1 y 3 | 1 | 0 | 0 | 0 | 0 | 1 |
| x 2 y 1 | 1 | 0 | 0 | 1 | 1 | 0 | ||
| x 2 y 2 | 0 | 1 | 0 | 0 | 0 | 1 | ||
| x 2 y 3 | 0 | 0 | 1 | 1 | 0 | 0 |
Операція твори графів. Нехай G 1 (X, E 1) і G 2 (Y, E 2) - два графа. Твором G 1 × G 2 графів G 1 і G 2 називається граф з множиною вершин X 'Y, а дуга з вершини (x i, y j) у вершину (x k, y l) існує тоді і тільки тоді, коли існують дуги (x i, x k) Î E 1 і (y j, y l) Î E 2.
Виконання операції добутку розглянемо на прикладі графів, зображених на рис. 5. Безліч вершин Z результуючого графа визначається як декартово добуток множин X 'Y. Безліч Z містить такі елементи: z 1 = (x 1 y 1), z 2 = (x 1 y 2), z 3 = (x 1 y 3), z 4 = (x 2 y 1), z 5 = ( x 2 y 2), z 6 = (x 2 y 3).
Визначимо безліч дуг результуючого графа. Для зручності розгляду складемо таблицю, в першому стовпці якої вказуються дуги графа G 1, у другому - дуги графа G 2, а в третьому і четвертому - дуги результуючого графа.
| G 1 | G 2 | (X 1, y 1) ® (x 2, y 1) | (Z a, z b) |
| (X 1, x 2) | (Y 1, y 1) (Y 1, y 2) (Y 2, y 3) (Y 3, y 2) | (X 1, y 1) ® (x 2, y 1) (X 1, y 1) ® (x 2, y 2) (X 1, y 2) ® (x 2, y 3) (X 1, y 3) ® (x 2, y 2) | (Z 1, z 4) (Z 1, z 5) (Z 2, z 6) (Z 3, z 5) |
| (X 2, x 1) | (Y 1, y 1) (Y 1, y 2) (Y 2, y 3) (Y 3, y 2) | (X 2, y 1) ® (x 1, y 1) (X 2, y 1) ® (x 1, y 2) (X 2, y 2) ® (x 1, y 3) (X 2, y 3) ® (x 1, y 2) | (Z 4, z 1) (Z 4, z 2) (Z 5, z 3) (Z 6, z 2) |
Операція твори володіє наступними властивостями.
1. G 1 × G 2 = G 2 × G 1.
2. G 1 × (G 2 × G 3) = (G 1 × G 2) × G 3.
Розглянемо виконання операції добутку графів в матричній формі.
Нехай G 1 (X, E 1) і G 2 (Y, E 2) - два графа, що мають n x і n y вершин відповідно. Результуючий граф G 1 × G 2 має n x × n y вершин, а його матриця суміжності вершин - квадратна матриця розміром (n x × n y) '(n x × n y). Позначимо через a a b = A (ij) (kl) елемент матриці суміжності вершин, що вказує на наявність дуги (ребра), що з'єднує вершину z a = (x i y j) c z b = (x k y l). Цей елемент може бути обчислений за допомогою матриць суміжності вершин вихідних графів наступним чином:
a a b = A (ij) (kl) = a 1, ik Ù a 2, jl, (3)
де a 1, ik, a 1, ik - елементи матриці суміжності вершин графів G 1 і G 2 відповідно.
Приклад 5. Виконати операцію твори на графах, наведених на рис. 5.
Складемо матриці суміжності вершин вихідних графів.
| x 1 | x 2 | y 1 | y 2 | y 3 | |||||||
| x 1 | 0 | 1 | y 1 | 1 | 1 | 0 | |||||
| A 1 | = | x 2 | 1 | 0 | A 2 | = | y 2 | 0 | 0 | 1 | |
| y 3 | 0 | 1 | 0 | ||||||||
| x 1 y 1 | x 1 y 2 | x 1 y 3 | x 2 y 1 | x 2 y 2 | x 2 y 3 | |||
| x 1 y 1 | a 1,11 Ù a 2,11 | a 1,11 Ùa 2,12 | a 1,11 Ù a 2,13 | a 1,12 Ùa 2,11 | a 1,12 Ù a 2,12 | a 1,12 Ù a 2,13 | ||
| x 1 y 2 | a 1,11 Ù a 2,21 | a 1,11 Ù a 2,22 | a 1,11 Ù a 2,23 | a 1,12 Ù a 2,21 | a 1,12 Ù a 2,22 | a 1,12 Ù a 2,23 | ||
| A | = | x 1 y 3 | a 1,11 Ù a 2,21 | a 1,11 Ù a 2,22 | a 1,11 Ù a 2,23 | a 1,12 Ù a 2,31 | a 1,12 Ù a 2,32 | a 1,12 Ù a 2,33 |
| x 2 y 1 | a 1,21 Ù a 2,11 | a 1,21 Ù a 2,12 | a 1,21 Ù a 2,13 | a 1,22 Ù a 2,11 | a 1,22 Ù a 2,12 | a 1,22 Ù a 2,13 | ||
| x 2 y 2 | a 1,21 Ù a 2,21 | a 1,21 Ù a 2,22 | a 1,21 Ù a 2,23 | a 1,12 Ù a 2,21 | a 1,12 Ù a 2,22 | A 1,12 Ù a 2,23 | ||
| x 2 y 3 | a 1,21 Ù a 2,31 | a 1,21 Ù a 2,32 | a 1,21 Ù a 2,33 | a 1,22 Ù a 2,31 | a 1,12 Ù a 2,32 | A 1,12 Ù a 2,33 |
| x 1 y 1 | x 1 y 2 | x 1 y 3 | x 2 y 1 | x 2 y 2 | x 2 y 3 | |||
| x 1 y 1 | a 1,11 Ù A 2 | a 1,12 Ù A 2 | ||||||
| x 1 y 2 | ||||||||
| A | = | x 1 y 3 | ||||||
| x 2 y 1 | a 1,21 Ù A 2 | a 1,22 Ù A 2 | ||||||
| x 2 y 2 | ||||||||
| x 2 y 3 | ||||||||
| x 1 y 1 | x 1 y 2 | x 1 y 3 | x 2 y 1 | x 2 y 2 | x 2 y 3 | |||
| x 1 y 1 | 0 | 0 | 0 | 1 | 1 | 0 | ||
| x 1 y 2 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| A | = | x 1 y 3 | 0 | 0 | 0 | 0 | 1 | 0 |
| x 2 y 1 | 1 | 1 | 0 | 0 | 0 | 0 | ||
| x 2 y 2 | 0 | 0 | 1 | 0 | 0 | 0 | ||
| x 2 y 3 | 0 | 1 | 0 | 0 | 0 | 0 |
ЛІТЕРАТУРА
1. Бєлоусов А.І., Ткачов С.Б. Дискретна математика: Підручник для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: изд-во МГТУ ім. Н.Е. Баумана, 2001 .- 744 с. (Сер. Математика в технічному університеті; Вип XIX).
2. Горбатов В.А. Фундаментальні основи дискретної математики. Інформаційна математика .- М.: Наука, Фізматліт, 2000 .- 544 с .- ISBN 5-02-015238-2.
3. Зарубін В.С. Математичне моделювання в техніці: Учеб. для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: Із МГТУ ім. Н.Е. Баумана, 2001 .- 496 с. (Сер. Математика в технічному університеті; вип. XXI, заключний).