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

Для структуры, представленной на рис. 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

D3 5 7

E6 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
Ребра	123	23 46	13 45	12 57	3 6 5	2 46 57	1 4 7	6 7
Сечения	123	2346	1345	1257	356	24567	147	67

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

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

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

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

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

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