В модифицированной матрице расстояний после вычеркивания 3 -й строки и 1 -го столбца остается один нулевой элемент, соответствующий звену (рис. 1.23).

Рисунок 1.23 - Текущая матрица расстояний для 5-го шага алгоритма

5 - й шаг. Поскольку в текущей матрице расстояний имеется только один нулевой элемент, соответствующий звену , то это звено является последним в определяемом маршруте длиной =300.

Дерево решений теперь может быть изображено так, как это показано на рис. 1.24.

Рисунок 1.24 -Дерево решений на 5-м шаге алгоритма

Построенный полный маршрут является оптимальным, если его длина не превосходит длины любого маршрута, соответствующего другим звеньям дерева, что и имеет место в данном примере. Он состоит из следующих звеньев или пар вершин и имеет суммарную длину =300. Этот оптимальный маршрут является минимальным гамильтоновым циклом, который изображен на рис. 1.25.

Рисунок 1.25 - Минимальный гамильтонов цикл графа

2 ОПРЕДЕЛЕНИЕ МНОЖЕСТВА ПУТЕЙ МЕТОДОМ ПОСТРОЕНИЯ ДЕРЕВА

Для графа (см. рис. 2.1) построим дерево путей из вершины 1. Данная вершина является корнем дерева и размещается на нулевом ярусе. Значение ранга пути здесь R = 0. На первом ярусе (R = 1) размещаются вершины 2, 3, 4, 5. которые имеют непосредственную связь с вершиной 1. Далее на втором ярусе от вершины 2 размещаются вершины, которые связаны с вершиной 2, а именно 4 и 5. Вершина 1 исключается из рассмотрения, поскольку путь в вершину 2 прошел через вершину 1. От вершины 3 на втором ярусе записываются вершины 4 и 5, от вершины 4 — вершины 2, 3 и 5. А от вершины 5 – 2, 3, 4. Аналогично записываются вершины на остальных ярусах дерева.

Построенное дерево для вершины-истока 1 представлено на рис. 2.2.

Как видим, в дереве есть четыре пути первого ранга (R = 1): a, e, g, h; десять путей второго ранга (R = 2): ab, , ed, , , gj, gc, , , hf. на третьем ярусе (R = 3) записаны пути третьего ранга: abc, abj, , , , edf, , , , gjd, , gcf, , , , hfb. В конце концов, пути четвертого ранга (R = 4): , abjd, , , , , gjdf, , hfbj.

Естественно, из дерева можно получить множество путей из фиксированной вершины в любую вершину графа последовательным просмотром ярусов дерева. Так,

=a++edf++++gjdf+gcf+++hf;

=+abj+++e++gj++++hfbj;

=ab++++g+++hfb;

=abjd++ed+++gjd+gc+h;

Рисунок 2.1 – Граф сети

Рисунок 2.2 - Дерево путей из вершины истока 1.

3 АНАЛИЗ СТРУКТУРНОЙ НАДЕЖНОСТИ СЕТИ ЭЛЕКТРОСВЯЗИ

Рассчитаем надежность связи между первой и всеми другими вершинами графа (1-2, 1-3, 1-4, 1-5). Будем считать заданный нами параметр р=0,817 равным для всех ребер графа показанном на рис. 3.1. Тогда получаем:

Из результатов видно, что самая большая надежность у пути (1,4) равная 0,972.

Рисунок 3.1 – Надежность связи