12.Топологические модели систем. Оптимизация структур связей методом построения минимальных связывающих деревьев. Алгоритм Прима или Краскала. Пример реализации выбранного алгоритма.

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

Примером топологической модели первого типа может служить модель схемы электрической принципиальной, используемая для решения задач анализа динамических и статических характеристик в ПО САПР функционального анализа электронной и вычислительной аппаратуры.

Топологические модели второго типа являются описаниями функциональной структуры систем. Они используются для решения задач декомпозиции (выделения подсистем в системе) и определения структурных свойств системы.

Примерами топологических моделей второго типа служат:

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

2. ориентированный граф информационной системы предприятия, в которой источники информации (персонал, измерительные устройства), приемники (персонал, исполнительное оборудование) и устройства обработки информации (активное оборудование компьютерной сети) представлены узлами, а дуги интерпретируют каналы связи с заданным направлением передачи информации.

Минимальным связывающим деревом графа называется дерево, связывающее между собой все вершины графа и имеющее минимальный суммарный вес ребер. Для построения таких деревьев используют алгоритмы Прима и Краскала.

В алгоритме Прима на первом шаге выбирается произвольная вершина графа (так называемый корень дерева) и из множества связанных с ней ребер выбирается ребро с минимальным весом. В дерево включается корень дерева, выбранное ребро и смежная вершина. На всех последующих шагах алгоритма рассматриваются множества вершин, имеющие ребра, инцидентные уже построенному дереву, из которых выбирается ребро с минимальным весом для включения в дерево очередной вершины. Построение завершается, когда дерево включает все вершины графа.

На рис. 33 приведен граф рассматриваемой подсети и результат выполнения первого шага алгоритма Прима, для которого в качестве корня дерева была выбрана вершина 6, и из множества весов инцидентных ребер {3, 4, 6} – ребро с минимальным весом, равным 3. Построенный фрагмент дерева выделен цветом, а множество ребер, инцидентных построенному фрагменту дерева – пунктиром.

На втором шаге алгоритма из множества весов инцидентных ребер {4, 6, 5, 5, 1} выбирается ребро с весом 1, в дерево добавляется вершина 1, а множество рассматриваемых весов ребер расширяется до {4, 6, 5, 5, 4, 3, 3}. На третьем шаге из этого множества выбирается ребро с весом 3, в дерево добавляется вершина 4, а в множество, рассматриваемое на следующих шагах включаются веса всех оставшихся ребер графа (рис. 34).

На четвертом шаге алгоритма в дерево добавляется ребро с весом 2 и вершина 3; на пятом – ребро с весом 3 и вершина 7. Результат построения минимального связывающего дерева для выделенного графа подсети первого сервера приведен на рис. 35. Суммарный вес этого дерева равен 12.

Алгоритм Краскала, в отличие от алгоритма Прима, не требует прохода по всем вершинам графа. Если m – количество вершин графа, то для построения минимального дерева необходимо m-1 ребер. Изначально все вершины графа окрашивают в различные цвета. Далее, на каждом шаге алгоритма выбирают ребро минимального веса между смежными вершинами разного цвета. Выбор очередного ребра r=(v_i, v_j), где v_i и v_j имеют разные цвета, возможен, если он не образует циклов в уже сформированном дереве. При выборе ребра r=(v_i, v_j) вершина v_j и все, окрашенные в ее цвет (т. е. ранее уже включенные в построенные фрагменты дерева) перекрашиваются в цвет вершины v_i. Построение завершается, когда дерево включает все вершины графа, т. е. все вершины имеют общий цвет.