ВУЗ:
Составители:
Рубрика:
Так как для рассматриваемого примера в матрице все перестановочные коэффициенты отрицательны или равны ну-
лю, то переставлять вершины первой части с вершинами других частей не надо.
Для определения возможности перестановки вершин v ∈ V
2
по формуле (1) вычисляем перестановочные коэффициенты
и заполняем матрицу ∆R
2
размерности N
2
× (m – (N
1
+ N
2
)). В нашем случае
.
Максимальное значение ∆R
2
имеет для пары вершин {v
4
, v
7
}, поэтому в матрице смежности вершины v
4
и v
7
меняются
местами. Полученная матрица смежности имеет вид
В соответствии с матрицей перестраивается граф (рис. 3).
Как видно из рис. 3, число внешних связей сократилось на три по сравнению с первой итерацией: Q
1
= 5, а Q
2
= 2.
На следующей итерации матрица
2
R
′
∆ имеет вид:
2
R
′
∆
=
Так как все элементы матрицы
2
R
′
∆ отрицательны, и других матриц ∆R строить не требуется, то на этом решение задачи
разбиения графа на три части заканчивается.
Содержание отчета
1.
Название лабораторной работы.
2.
Цель работы.
3.
Исходные данные согласно варианту.
4.
Представление исходного графа матрицей смежности.
5.
Выполнение итерационного этапа последовательно-итерационного алгоритма разбиения графа.
6.
Расчет критерия оптимальности.
7.
Вывод по результатам работы.
8.
Список использованной литературы.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Как составляется матрица смежности?
2.
Что понимают под степенью вершины?
3.
Какие основные ограничения накладываются на компоновку вершин?
V
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
