Алгоритм выбора минимальных сечений

 

Требуется выделить все минимальные сечения для рассмотренной структуры типа «мостик». Несложно показать, какие сечения являются минимальными. однако, если число элементов и их связей достаточно велико, то выбор минимальных сечений – трудоемкий процесс - число возможных сочетаний возрастает по степенной зависимости. Поэтому выбор минимальных сечений также следует переложить на плечи ПК.

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

В графе отсутствуют параллельные и последовательные элементы.

Граф содержит:

m = 7– число ребер;

M=5– вершин.

Разорвем ребра графа так, чтобы часть вершин (N; у нас N=3: A,B,C) была присоединена только ко входу графа, а остальные (M-N) – к выходу графа. Этим самым нарушится связь между входом и выходом графа и образованы две структуры, называемые (деревьями): подграфами.

N=3 подграф – это совокупность 3-х вершин и ребер, связанных с этими 3-мя вершинами.

N=K подграф – это совокупность вершин и ребер присоединенных ко входу и связанных с этими N вершинами.

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

если для данного N=3 подграфа, связанного со входом, перечислить все ребра, непосредственно связанные со всеми его вершинами, то ребра, связывающие вершины данного N=3 подграфа встречаются дважды. Эти ребра исключаются, оставшиеся ребра и будут «висячими», оборванными, т.е. образовывать минимальное сечение.

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

Для построения N=3 подграфов к вершинам N=2 подграфов последовательно присоединяются по одной вершине, связанной с каждой вершиной данного N=2 подграфа и так далее.

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

(N=1) – подграф – вершина А

(N=2) – подграфы – вершины А+В, А+С, А+Д

(N=3) – подграфы – вершины АB+C, АB+D, АC+Д

(N=4) – подграф – вершина АB+D

· Для каждого подграфа определяются сечения. Для этого по матрице связей вершины-ребра

Вершины	Ребра, связанные с вершиной
A	1,2,3
B	1,4,6
C	2,4,5
D	3,5,7

выписываются все ребра, непосредственно связанные с вершинами данного подграфа.

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

· Составляется массив подграфов, начиная с N=1 графа, последовательным присоединением к каждому подграфу N=K-1, K=2,3, вершин, непосредственно связанных с одной из вершин этого N=K-1-го подграфа.

N=1 подграф – это вход графа, вершина А.

N=K подграф	N=1 подграф	подграфы	подграфы	N=4 подграф
Вершины N=K	A	AB	AC	AD	ABC	ABD	ACD	ABCD
Ребра		123 146	123 245	123 357	123 146 245	123 146 357	123 245 357	123 146 245 357
Сечения

 

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