[
Операції на графах
]
Білоруський державний університет інформатики і радіоелектроніки
Кафедра інформатики
РЕФЕРАТ
На тему:
«Операції на графах»
МІНСЬК, 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
1,
x
2,
x
3,
x
4}.
Складемо матриці суміжності вершин допоміжних графів
G
'1
і
G'
2.
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
Матриця
A = A
'1
È A'
2
має вигляд
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
Отримана матриця суміжності вершин
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
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 = 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
Знайдемо матрицю суміжності вершин
A = A
1
Ç A
2
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
Отримана матриця суміжності вершин
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).
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
Обчисливши елементи матриці згідно (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
(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).
Визначимо безліч дуг результуючого графа. Для цього виділимо групи вершин безлічі
Z,
компоненти яких збігаються. У розглянутому прикладі п'ять таких груп: дві групи з збігаються компонентами з безлічі
X,
і три групи, що мають співпадаючі компоненти з
Y.
Розглянемо групу вершин результуючого графа, які мають загальну компоненту
x
1:
z
1
= (x
1
y
1),
z
2 =
(x
1
y
1),
z
3
= (x
1
y
3).
Відповідно до визначення операції декартового добутку графів, безліч дуг між цими вершинами визначається зв'язками між вершинами безлічі
Y.
Таким чином, дуга
(y
1,
y
1)
у графі
G2
визначає наявність дуги
(z
1,
z
1)
у результуючому графі. Для зручності розгляду всіх дуг результуючого графа складемо таблицю, в першому стовпці якої перераховуються вершини з однаковими компонентами, у другому - дуги між незбіжними компонентами, а в третьому і четвертому - дуги в результуючому графі.
№ п.п.
Групи вершин з співпадаючими компонентами
Дуги для незбіжних компонент
Дуга
(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
Для побудови матриці суміжності результуючого графа скористаємося співвідношенням (2). У цьому співвідношенні перший доданок
K
ik
× a
2, jl
вказує на наявність дуг для вершин, у яких співпадають компоненти з безлічі
X.
Для пояснення сказаного, розглянемо допоміжну матрицю
Axy,
в якій елементи, для яких
K
ik
= 1, помічені символом X. Ці елементи приймають значення, рівні значенням
відповідних
елементів матриці
A
2
суміжності вершин графа
G
2,
так, як це показано для матриці
A *.
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
Другий доданок
K
jl
× a
1, ik
співвідношення
(2) вказує на наявність дуг для груп вершин, у яких співпадають компоненти з безлічі
Y.
У матриці
Axy
елементи, для яких
K
jl
= 1 помічені символом
Y.
Ці елементи приймають значення, рівні значенням відповідних елементів матриці
A
1
суміжності вершин графа
G
1,
так, як це показано для матриці
A *.
Зауважимо, що в
матрицях
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
'G
2,
представлений на рис. 4
Операція
твори
графів.
Нехай
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)
Результуючий граф
G
1 ×
G
2
зображено на рис.5.
Операція твори володіє наступними властивостями.
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
Побудуємо матрицю
A
суміжності вершин результуючого графа, кожен елемент якої обчислюється згідно співвідношенню (4.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
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
Для зручності розгляду розділимо матрицю
A
на чотири квадратні підматриці. Зауважимо, що кожна підматриць може бути отримана шляхом логічного елементів матриці множення
A
2
на один з елементів
a
1, ij
матриці
A
1.
З урахуванням цього матрицю
A
можна представити так:
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
Таким чином, матриця суміжності вершин графа
G
1
×
G
2
має вигляд:
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
Неважко переконатися, що отриманої матриці суміжності вершин відповідає граф
G
1
× G
2,
представлений на рис. 5.
ЛІТЕРАТУРА
1. Бєлоусов А.І., Ткачов С.Б.
Дискретна математика
:
Підручник
для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: изд-во МГТУ ім. Н.Е. Баумана, 2001 .- 744 с. (Сер.
Математика
в технічному університеті; Вип XIX).
2. Горбатов В.А. Фундаментальні
основи дискретної математики
.
Інформаційна
математика
.- М.:
Наука
, Фізматліт, 2000 .- 544 с .- ISBN 5-02-015238-2.
3. Зарубін В.С.
Математичне
моделювання
в техніці: Учеб. для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: Із МГТУ ім. Н.Е. Баумана, 2001 .- 496 с. (Сер. Математика в технічному університеті; вип. XXI, заключний).
Будь ласка, не зберігайте тестовий текст.
Ваш ip: 3.143.4.181 буде збережений.
категорії
за типом
за алфавітом
завантажені
© Усі права захищені
написати до нас