Примеры сетевых топологий


Оболочечность


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

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

Прован и Биллера доказали важный результат, связанный со структурой матроидов, который (вместе с другими результатами) накладывает ограничения на их F-векторы. Они показали, что матроиды являются “оболочечными” комплексами. Важность результата Прован-Биллера в исследованиях надежности заключается в том, что они предлагают возможность использования оболочечности для улучшения ограничений Крускал-Катона. Конечно, это требует введения структурной теоремы для оболочечных систем. Интервал [L,U] является семейством субнаборов {S:LНSНU}. Часть интервала комплекса является набором разъединенных интервалов, для которых каждый набор в комплексе принадлежит строго одному интервалу. Комплекс разделим, если он имеет секции интервалов [Li,Ui], 1 Јi Ј J с Ui в качестве базы для всех i. Оболочечные комплексы всегда являются разделимыми.

Рассмотрим оболочечный комплекс с b базами.


Начало  Назад  Вперед



Книжный магазин