Операции на графах
Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).
|
x1y1 |
< p>x1y2 |
x1y3 |
x2y1 |
x2y2 |
x2y3 | |||
|
x1y1 |
a1,11Ù a2,11 |
a1,11Ùa2,12 |
a1,11Ù a2,13 |
a1,12Ùa2,11 |
a1,12Ù a2,12 |
a1,12Ù a2,13 | ||
|
x1y2 |
a1,11Ù a2,21 |
a1,11Ù a2,22 |
a1,11Ù a2,23 |
a1,12Ù a2,21 |
a1,12Ù a2,22 |
a1,12Ù a2,23 | ||
|
A |
= |
x1y3 |
a1,11Ù a2,21 |
a1,11Ù a2,22 |
a1,11Ù a2,23 |
a1,12Ù a2,31 |
a1,12Ù a2,32 |
a1,12Ù a2,33 |
|
x2y1 |
a1,21Ù a2,11 |
a1,21Ù a2,12 |
a1,21Ù a2,13 |
a1,22Ù a2,11 |
a1,22Ù a2,12 |
a1,22Ù a2,13 | ||
|
x2y2 |
a1,21Ù a2,21 |
a1,21Ù a2,22 |
a1,21Ù a2,23 |
a1,12Ù a2,21 |
a1,12Ù a2,22 |
A1,12Ù a2,23 | ||
|
x2y3 |
a1,21Ù a2,31 |
a1,21Ù a2,32 |
a1,21Ù a2,33 |
a1,22Ù a2,31 |
a1,12Ù a2,32 |
A1,12Ù a2,33 |
Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A2 на один из элементов a1,ij матрицы A1. С учетом этого матрицу A можно представить так:
|
x1y1 |
x1y2 |
x1y3 |
x2y1 |
x2y2 |
x2y3 | |||
|
x1y1 |
a1,11ÙA2 |
a1,12ÙA2 | ||||||
|
x1y2 | ||||||||
|
A |
= |
x1y3 | ||||||
|
x2y1 |
a1,21ÙA2 |
a1,22ÙA2 | ||||||
|
x2y2 | ||||||||
|
x2y3 | ||||||||
Таким образом, матрица смежности вершин графа G1×G2 имеет вид:
|
x1y1 |
x1y2 |
x1y3 |
x2y1 |
x2y2 |
x2y3 | |||
|
x1y1 |
0 |
0 |
0 |
1 |
1 |
0 | ||
|
x1y2 |
0 |
0 |
0 |
0 |
0 |
1 | ||
|
A |
= |
x1y3 |
0 |
0 |
0 |
0 |
1 |
0 |
|
x2y1 |
1 |
1 |
0 |
0 |
0 |
0 | ||
|
x2y2 |
0 |
0 |
1 |
0 |
0 |
0 | ||
|
x2y3 |
0 |
1 |
0 |
0 |
0 |
0 |
Скачать рефератДругие рефераты на тему «Математика»:
Поиск рефератов
Последние рефераты раздела
- Анализ надёжности и резервирование технической системы
- Алгоритм решения Диофантовых уравнений
- Алгебраическое доказательство теоремы Пифагора
- Алгоритм муравья
- Векторная алгебра и аналитическая геометрия
- Зарождение и создание теории действительного числа
- Вероятностные процессы и математическая статистика в автоматизированных системах