Ветвь 1. Попарная проверка вершин и нахождение диаметра 8 страница
а – граф G3; б – граф G4
| Матрица последователей P | Матрица кратчайших расстояний M | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Микрорешение
Так как в результате разборки остался подграф с двумя вершинами, на данном этапе матрица М не изменяется. Матрица Р не изменяется, так как для кратчайшего пути между вершинами 
есть предполагаемый последовать 
. В общем случае может решаться задача поиска путей между оставшимися вершинами одним из известных алгоритмов.
| Матрица последователей P | Матрица кратчайших расстояний M | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Сборка графа
На данном этапе строится полный подграф. Из заполненной последовательности 
разборки графа добавляем в обратном порядке по одной вершине. На каждом шаге сборки выполняется расчет кратчайших путей между восстанавливаемой вершиной и уже восстановленными.
|
|
|
4) Начинаем с добавления последней удаленной вершины 
, смежные ей вершины 
(рис. 2.71). Пересчитываем значения весовых коэффициентов ребер, связывающих уже восстановленные вершины 
и 
:
;
.
Найденные значения являются искомыми минимальными расстояниями. При этом элементы матрицы последователей Р в ячейках 
и 
не изменяются, так значения 
и 
заполнены в начале алгоритма.
| Матрица последователей P | Матрица кратчайших расстояний M | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
а б
Рис. 2.71. Пример сборки неориентированного нагруженного графа. Шаг 4;
а – граф G4; б – граф G3
3) Теперь добавляем вершину 
, смежные ей вершины 
(рис. 2.72). Пересчитываем значения весовых коэффициентов ребер, связывающих уже восстановленные вершины 
и 
:
|
|
|
;
;
.
Пересчитанные значения весовых коэффициентов не меньше записанных в матрице М, кроме значения 
, которое меньше записанного в ячейках матрицы M 
и 
, поэтому заменим значение 21 в этих ячейках на 17.
Элементы матрицы последователей в ячейках 
, 
, 
, 
не изменяются, так как были заполнены в начале алгоритма. Элементы матрицы последователей в ячейках 
, 
изменяются на 
, так как найденный путь минимальной длины проходит через вершину 
.
При этом для всех вершин подграфа 
найдены кратчайшие расстояния.
| Матрица последователей P | Матрица кратчайших расстояний M | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
а б
Рис. 2.72. Пример сборки неориентированного нагруженного графа. Шаг 3;
а – граф G3; б – граф G2
2) Теперь добавляем вершину 
; смежные ей вершины 
(рис. 2.73). Пересчитываем значения весовых коэффициентов ребер, связывающих уже восстановленные вершины 
и 
:
|
|
|
;
;
;
.
Элементы матрицы последователей в ячейках 
, 
, 
, 
, 
, 
не изменяются, так как были заполнены в начале алгоритма. Пустые элементы матрицы последователей в ячейках 
, 
изменяются на 
.
| Матрица последователей P | Матрица кратчайших расстояний M | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Дата добавления: 2021-02-10; просмотров: 60; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!