g9 (542472), страница 4
Текст из файла (страница 4)
Построим теперь матрицу 
:
7 8 2
|
| 4 | 2 | 0 | |
| 1 | 1 | 1 | -1 | 4 |
| -2 | 0 | -4 | -2 | 3 |
| 1 | 3 | -1 | -3 | 6 |
3 - максимальный элемент. Выбранный элемент (6, 7).
Меняем местами 6 и 7 строки и столбцы в исходной матрице.
| 4 | 3 | 7 | 6 | 8 | 2 | |
| 4 | 0 | 2 | 2 | 1 | 1 | 1 |
| 3 | 2 | 0 | 1 | 3 | 2 | 0 |
| 7 | 2 | 1 | 0 | 1 | 0 | 0 |
| 6 | 1 | 3 | 1 | 0 | 2 | 2 |
| 8 | 1 | 2 | 0 | 2 | 0 | 3 |
| 2 | 1 | 0 | 0 | 2 | 3 | 0 |
Получаем матрицу 
.
Для матрицы снова вычисляем числа 
и 
и строим матрицу .
Построим теперь матрицу :
6 8 2
|
| 1 | -2 | -4 | |
| -1 | -2 | -5 | -7 | 4 |
| 2 | -3 | -4 | -2 | 3 |
| -2 | -3 | -4 | -6 | 7 |
Поскольку в матрице нет положительных элементов, то из исходного графа удаляем подграф, соответствующий матрице смежности из трех вершин. Для рассмотрения остается матрица размерности 3.
Полученный подграф - 
.
Теперь рассматриваем матрицу:
| 6 | 8 | 2 | |
| 6 | 0 | 2 | 2 |
| 8 | 2 | 0 | 3 |
| 2 | 2 | 3 | 0 |
Полученный подграф - 
.
Таким образом исходный граф из 9 вершин разбит на 3 подграфа по 3 вершины в каждом. Получили:
.
Сделали 5 итераций.
Число внешних связей между подграфами 
.
Эвристический алгоритм.
Это приближенный алгоритм получения оптимального решения. Разберем этот алгоритм на матрице малой размерности.
| 4 | 3 | 6 | 7 | 8 | 2 | |
| 4 | 0 | 2 | 1 | 2 | 1 | 1 |
| 3 | 2 | 0 | 3 | 1 | 2 | 0 |
| 6 | 1 | 3 | 0 | 1 | 2 | 2 |
| 7 | 2 | 1 | 1 | 0 | 0 | 0 |
| 8 | 1 | 2 | 2 | 0 | 0 | 3 |
| 2 | 1 | 0 | 2 | 0 | 3 | 0 |
Стягиваем вершины 3 и 6 и назовем эту вершину 1 = { 3, 6 }.
Стягиваем вершины 1 = { 3, 6 } и 8 и назовем эту вершину 1 = { 3, 6, 8 }.
Остался граф - 
.
Сумма внешних связей равна 11( не оптимальное решение ).
Запишем теперь все выше изложенное в матричном виде:
| 4 | { 3, 6 } | 7 | 8 | 2 | |
| 4 | 0 | 3 | 2 | 1 | 1 |
| { 3, 6 } | 3 | 0 | 2 | 4 | 2 |
| 7 | 2 | 2 | 0 | 0 | 0 |
| 8 | 1 | 4 | 0 | 0 | 3 |
| 2 | 1 | 2 | 0 | 3 | 0 |
| 4 | { 3, 6, 8 } | 7 | 2 | |
| 4 | 0 | 4 | 2 | 1 |
| { 3, 6, 8 } | 4 | 0 | 2 | 5 |
| 7 | 2 | 2 | 0 | 0 |
| 2 | 1 | 2 | 0 | 0 |
Вычеркиваем из матрицы те строки и столбцы, которые содержат 3 вершины. Остается нужная нам матрица 3 x 3.
| 4 | 7 | 2 | |
| 4 | 0 | 2 | 1 |
| 7 | 2 | 0 | 0 |
| 2 | 1 | 0 | 0 |
Алгоритм.
-
в матрице
![]()
находим максимальный элемент, определяющий индексы строки и столбца, где находится максимальный элемент; -
проверяем объединение
![]()
- ой и ![]()
- ой строки: ![]()
. Если да, то переход к ( 3 ), иначе ( 5 ); -
объединяем
![]()
- ю и ![]()
- ю строки, ![]()
- й и ![]()
- й столбцы. Производим пересчет связей. Понижается размерность ![]()
на 1. Вес объединенной строки равен сумме весов объединенных вершин; -
если количество объединенных строк равно количеству блоков(подграфов), то переходим к ( 6 ), если нет, то к ( 1 );
-
вычеркиваем этот элемент и определяем максимальный элемент в оставшейся матрице. Возврат в ( 1 );
-
получено оптимальное решение.
находим максимальный элемент, определяющий индексы строки и столбца, где находится максимальный элемент;
- ой и 
. Если да, то переход к ( 3 ), иначе ( 5 );
- ю и 
Замечание.
Вес объединенных строк равен сумме весов объединенных вершин.
- количество вершин в подграфе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
