Выбор минимальных сечений

Для структуры, представленной на рис. 3.26, не сложно показать, какие сечения являются минимальными. Однако, если число элементов и их связей будет достаточно велико, то выбор минимальных сечений – трудоемкий процесс – число возможных сочетаний элементов возрастает по степенной зависимости.

Рассмотрим метод направленного выбора минимальных сечений, использующий элементы теории графов. Структура представляется в виде замкнутого графа, имеющего один вход А и один выход Е (рис. 3.27, а).

Замкнутым называется граф, не содержащий элементы, по которым не проходит ни один путь, связывающий вход графа с выходом. Ребрами такого графа служат элементы, надежность которых известна.

Пусть имеется граф, содержащий m ребер и M вершин. Разорвем ребра графа так, чтобы часть вершин (N) была присоединена только к входу графа, а остальные (M-N) вершин – к выходу графа (рис. 3.27, б). Этим самым нарушена связь между входом и выходом графа и образованы две структуры, называемые деревьями: N – дерево (дерево, содержащее N вершин) и (M–N) – дерево. При этом «оборванные» ребра образуют минимальные сечения. На рис. 3.27,б минимальное сечение образуют элементы 3, 5, 6.

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

Алгоритм определения минимальных сечений:

1. Составляется матрица непосредственных связей вершин – ребер графа.

2.Составляется массив N – деревьев графа последовательным присоединением к N_i – дереву вершин, непосредственно связанных с одной из вершин, уже принадлежащих N_{i –1} – дереву.

3. Для каждого N_i – дерева выбираются сечения.

4. Составляется массив сечений, из которого выбираются минимальные.

Пример 3.12. Определить минимальные сечения, содержащиеся в структуре, представленной на рис. 3.27,а.

Решение. 1. Составляется матрица непосредственных связей вершин и ребер графа. Например, вершина А непосредственно связана с ребрами 1, 2, 3; вершина В – с ребрами 1, 4, 6 и т.п. Матрица связей для рассматриваемого графа будет иметь вид:

Вершины Ребра, связанные с вершиной

А 1 2 3

В 1 4 6

С 2 4 5

D 3 5 7

E 6 7

2. Составляется массив N – деревьев.

Первое N ₁– дерево – вершина А. Затем к ней непосредственно присоединяются три вершины В, C, D, являющиеся последующими N – деревьями AB, AC, AD. Далее, к дереву АВ присоединяется вершина D, поскольку она связана с одной из вершин N ₂– дерева, а именно А. Тогда получим N ₃– дерево ABD. Кроме того, к N ₂– дереву присоединяется вершина С и так далее, пока не будут рассмотрены все вершины, за исключением Е – выход графа (если вершину Е присоединить к N – дереву, то образуется связанная структура).

Таким образом, определяется массив N – деревьев графа:

A, AB, AC, AD, ABC, ABD, ACD, ABCD.

3. Для каждого N_i – дерева определяются сечения. По матрице ребра – вершины в столбик выписываются все ребра, непосредственно связанные с вершинами N – деревьев (табл. 3.3).

Таблица 3.3

Массив N – деревьев графа

N – дерево	A	AB	AC	AD	ABC	ABD	ACD	ABCD
Ребра		23 46	1 3 45	12 57	3 6 5	2 46 57	1 4 7	6 7
Сечения

4. Выбираются минимальные сечения из множества полученных сечений. Для этого все сечения представляются в порядке возрастания числа элементов и уточняется, не содержатся ли в сечениях с большим числом элементов сечения с меньшим числом элементов. Так, сечение, образованное деревом ABD = 24567 содержит сечение, образованное деревом ABCD = 67. Поэтому сечение 24567 исключается. Оставшиеся сечения являются минимальными. Для приведенного примера минимальные сечения: 67, 123, 147, 356, 1345, 2346. Других минимальных сечений в графе не содержится.

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

При составлении матриц непосредственных связей ребра, которые входят в вершину, отмечаются знаком «–»; ребра, которые выходят из вершины – знаком «+». В таблице N – сечений (аналогичной табл. 3.3) ребра, входящие в совокупность ребер N – четное число раз, независимо от присвоенного им знака, вычеркиваются. Кроме того, вычеркиваются также ребра, входящие в совокупность ребер N – дерева со знаком «–».

Многие реальные объекты имеют такую структуру соединения (или взаимодействия) элементов, которая не может быть сведена ни к последовательно-параллельной, ни к параллельно-последовательной схеме.

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

Метод состоит в том, что рассматриваются все взаимоисключающие способы появления отказов в объекте. Применение этих методов покажем на типовых примерах расчета.