[|Процедуры формирования множеств сечений как для направления связи, так и для графа в целом являются несколько более простыми, чем аналогичные процедуры для связных подграфов [1]. Данное обстоятельство связано, прежде всего, с тем, что для большинства реальных сетевых топологий количество соответствующих связных подграфов (путей и остовых деревьев) обычно сопоставимо или существенно больше количества несвязных подграфов (сечений в направлении и в целом) [2].]
Множества сечений в направлении связи формируются на основе ранее использованных сечений вершин графа [3]. При этом данные сечения разбиваются на три группы. Первая содержит только сечение вершины–истока, вторая – только сечение вершины–стока, а третья – все оставшиеся. Производится последовательный перебор всех комбинаций третей группы, порядок которых варьируется от одного до значения на три единицы меньшего числа вершин в графе. Для каждой комбинации проверяется два условия. Первое – если комбинация содержит все вершины, входящие в первую группу (сечение вершины–истока), то она отбрасывается. Второе – если комбинация не включает в себя сечений, не содержащих вершины, входящие во вторую группу (сечение вершины–стока), то она также отбрасывается. Данные условия позволяют существенно сократить количество не минимальных сечений, но полностью, как показали исследования, эту проблему не устраняют.
Каждая из полученных комбинаций третьей группы дополняется первой (сечением вершины–истока) и после удаления дублированных ребер сохраняется как сечение графа в направлении [4]. Следует заметить, что в отличие от подхода, описанного в [3], необходимо дополнительно проверять сохраняемые сечения на минимальность, так данная процедура формирует сечения, способные потенциально содержать в себе минимальные. Отметим, что подобная процедура также достаточно просто реализуется в программной среде MathCad, а в качестве исходных данных используются, как и при формировании простых путей, матрица смежностей и две вершины – исток и сток.
Множества сечений для графа в целом формируются на основе перебора всех допустимых комбинаций ребер от первого порядка до порядка, в общем случае соответствующего числу ребер в графе сети [5, 6]. При этом для сокращения количества рассматриваемых комбинаций используется прием, когда комбинация являющаяся сечение в дальнейшем не порождает комбинации более высокого порядка. Для каждой комбинации проверяется два условия. Первое – является ли она сечением, то есть на основе метода поиска в ширину осуществляется контроль связности графа, не включающего ребра данной комбинации. Второе – выполняется проверка на минимальность данной комбинации, то есть является ли она подмножеством уже найденных сечений или нет [7]. Реализация данной процедуры также достаточна проста в пакете математического моделирования MathCad, а исходные данные аналогичны используемым при формировании множества остовых деревьев – матрица смежностей. Отметим, что в отличие от метода формирования сечений в направлении связи, этот метод оказывается более громоздким вследствие как несколько большего количеств сечений, так и более разветвленной процедуры образования комбинаций для проверки.
1. Филин Б. П. Методы анализа структурной надежности сетей связи // Москва : Радио и связь, 1988. – 208 с.
2. Татт У. Теория графов / пер. с англ. – Москва : Мир, 1988. – 424 с.
3. Chaturvedi S. K. Network Reliability. Measures and Evaluation. Wiley, 2016. 237 p.
4. Батенков К. А. Общие подходы к анализу и синтезу структур сетей связи // Современные проблемы телекоммуникаций: Материалы Российской научно-технической конференции. 2017. С. 19–23.
5. Батенков К. А. Числовые характеристики структур сетей связи // Труды СПИИРАН. 2017. № 4 (53). С. 5–28.
6. Батенков К. А. К вопросу оценки надежности двухполюсных и многополюсных сетей связи // Современные проблемы радиоэлектроники: сб. науч. тр. Красноярск: Сиб. федер. ун-т. 2017. C. 604–608.
7. Батенков К. А. Анализ и синтез структур сетей связи по детерминированным показателям устойчивости / К. А. Батенков, А. А. Батенков // Труды СПИИРАН. 2018. № 3 (58). С. 128–159.
Полный текст статьи доступен по ссылке.
;){kind=link}