Многогранные комплексы и матроидные порты

В случае проблемы достижимости Прован [J.S.Provan, “Polyhedral combinatorics and network reliability”, Math. Oper. Res., 11 (1986) 36-61] замечает, что F-комплекс является “многогранным комплексом” и использует теорему Биллеры и Ли, чтобы получить эффективно вычисляемые ограничения надежности, которые жестче для многогранных комплексов.

Структура матроида для всетерминальной проблемы и многогранная структура достижимости позволяют получить существенное улучшение по сравнению с ограничениями Крускала-Катона для общей когерентной проблемы надежности. Пусть для связного графа с n вершинами, имеющего k терминалов, и набор ребер Е, |E|=m, F является его F-комплексом. Блокирующий комплекс F* из F является {E\S:SО2E\F }. F-вектор (F0,...,Fm) из F и F-вектор

удовлетворяет условию

для 0 Ј i Ј m. Чари показал, что субкомплекс F(m-n+1), полученный путем удаления всех наборов из F с мощностью, превосходящей m-n+1, является оболочечным комплексом. Следовательно, задав ограничение на отдельный коэффициент Fm-n+1, можно применить стратегию Балл-Прована к этой k-терминальной проблеме, для того чтобы ограничить (F0,…,Fm-n+1). Что можно сказать об остальных коэффициентах? Чари далее доказал, что F*(n-2), полученный из F* путем удаления всех наборов с мощностью, превосходящей n-2, также является оболочечным. Следовательно, границы Балл-Прована могут быть применены снова для ограничения (F*0,…,F*n-1) или эквивалентно ограничить (Fm,…,Fm-n+2).

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

Содержание раздела