Минимизация сети

Матрица достижимости.

Для ориентированного графа G, имеющего N вершин также рассматривается матрица достижимости C(G) размера N x N, элементы которой определяются так:

C(i,j)=1- если вершина vj достижима из vi

C(i,j)=0- в противном случае.

Пример построения матрицы достижимости:

Рисунок 13 – Ориентированный граф.

Матрица достижимости.

Задача минимизации сети состоит в нахождении ребер, со­единяющих все узлы сети и имеющих минимальную суммар­ную длину.

На ребрах, соединяющих узлы 1, 2, 3, указаны длины. Узел 3 соединен с узлами 1 и 2 минимальной длиной 4+6 = 10. Если соединить узлы 1 и 2, то возникает цикл и получающаяся сеть не будет минимальной. Отсутствие циклов в минимальной сети дало ей название "минимальное дерево-остов".