Примеры сетевых топологий
Группирование ребер
Пусть G=(V,E) является графом (или диграфом, или мультиграфом). Секция G содержит k графов G1,….,Gk с Gi=(V,Ei), где набор ребер Е поделен на k классов Е1,…,Еk. Группа ребер G из k графов G1,….,Gk получается путем выделения набора ребер Е в k+1 класс Е1,…,Еk, и определения Gi=(V,Ei). Главное, на что здесь следует обратить внимание, достаточно просто:
Лемма 4.1. Если G имеет группу ребер по k графам G1,….,Gk, а Rel является любой сопряженной мерой надежности, то
Неравенство в лемме 4.1 возникает из-за того, что существуют рабочие состояния G, в которых ни один Gi не работает. Сделаем несколько замечаний, чтобы применение леммы 4.1 было эффективным при получении нижней границы надежности. Рассмотрим группу ребер G из G1,….,Gk. Если любой Gi находится в нерабочем состоянии, когерентность (сцепление) гарантирует, что Rel(Gi)=0; в данном случае включение Gi в группу ребер не окажет влияния на ограничение и Gi может быть просто опущено. Таким образом, нам нужно в случае группы ребер заботиться только о работоспособных субграфах.
Нашей целью является получение эффективно вычислимых границ; следовательно, необходимо, чтобы мы вычисляли (или хотя бы устанавливали границы) Rel(Gi) для каждого Gi. Одним из таких решений, предложенных Полесски [V. P. Polesskii, “A lower boundary for the reliability of information networks”, Problems of Information Transmission, 7, (1971), 165-171], является алгоритм группирования ребер G с минипроходами. Надежность минипрохода легко вычисляется. Это дает решение, в котором мы формируем группу ребер G с максимально возможным числом минипроходов, а затем применяем лемму 4.1. Эта базовая стратегия активно использовалась.
Важно заметить, что в то время как вычислимые ограничения требуют, чтобы ребра имели равную вероятность сохранения работоспособности, здесь это предположение не требуется; нужно только вычислить вероятность для минипрохода, как произведение вероятностей работоспособности ребер, составляющих минипроход. Принимая это во внимание, можно модифицировать нашу задачу группирования ребер, потребовав, чтобы в группу входили наиболее надежные проходы, а не максимально возможное число минипроходов.
Ничего не стоит также, чтобы любая группа ребер работоспособных субграфов G1,….,Gk, для которых легко вычислить Rel(Gi), предоставляла возможность эффективного вычисления нижней границы. Это приводит к задачам, таким как группирование ребер для последовательно-параллельных графов, или к частичным k-деревьям при фиксированном k. Этот последний подход, кажется, еще не изучен в литературе, следовательно, мы сосредоточимся на формировании групп ребер с минипроходами.
Используя теорему Таттла и Нэш-Вильямса, Полесски заметил, что граф с n вершинами и с-связанными ребрами имеет, по крайней мере,
Для двухтерминальной надежности минипроходы являются лишь s,t-проходами. Теорема Менгера утверждает, что максимальное число s,t-проходов с разделенными ребрами равно мощности минимального s,t-разреза. Таким образом, используя методики сетевых потоков, можно найти максимум группирования ребер. Проблема нахождения наилучшего группирования ребер, даже если все вероятности работоспособности ребер равны, является сложной из-за того факта, что минипроходы демонстрируют большую вариацию мощности.
Обратимся к k-терминальной надежности, где ситуация не столь удовлетворительна.
Здесь минипутем является субдерево, в котором каждый листик представляет собой терминал, т.е. дерево Штайнера. Оказалось, что никакой эвристики для нахождения “хороших” групп ребер для деревьев Штайнера не найдено.
До этого момента мы рассматривали нижние границы, базируясь на методике группирования ребер в рамках минипроходов. Теперь обратимся к верхним границам. Не удивительно, что лемма 4.1 имеет “дуальный” вид для верхних границ при замене набора проходов на набор разрезов:
Лемма 4.2. Пусть G=(V,E) является графом (или диграфом, или мультиграфом). Пусть Rel является когерентной мерой надежности. Пусть С1,…,Сs является группой ребер G набора разрезов. Тогда
где ре - вероятность работоспособности ребра е.
Лемма 4.2 дает верхнюю границу, так как отказ для любого разреза при группировании ребер вызывает отказ G, но отказ G может случиться, даже когда ни один из наборов разрезов в группе не дает отказа.
Нахождение максимального набора разрезов, разъединяющих ребра, достаточно прямолинейно - просто следует пометить каждый узел его расстоянием от s. Если t получает метку l, формируем набор разрезов Сi, содержащий все ребра между вершинами, помеченными i-1 и вершинами, помеченными i для 1 Ј i Ј l. В результате получается l s,t-разрезов, разъединяющих ребра. Нахождение ”хороших” наборов разрезов для определения верхних границ методом группирования ребер оказывается более сложным, чем для нижних границ. В последнее время Вагнер [D.K.Wagner, “Disjoint (s,t)-cuts in a network”, Networks 20, (1990), 361-372] предложил алгоритм с полиномиальным временем для нахождения набора s,t-разрезов, разъединяющих ребра, с минимальной стоимостью при максимальной мощности.
Обратившись к верхним границам все- и k-терминальной надежности с привлечением группирования ребер миниразрезами, мы сталкиваемся с главной трудностью: даже для всетерминальной надежности нахождение максимальной группировки посредством миниразрезов является NP-трудным. Таким образом, верхняя граница всетерминальной надежности может быть получена путем использования ограничения группирования дуг для достижимости.
Выделяются два потенциальных метода улучшения стратегии группирования ребер. Первый - заключается в рассмотрении более надежных субграфов для группировки; второй - связан c расширением рассматриваемых наборов проходов и разрезов с целью разрешения некоторых пересечений ребер (таким образом, теряя независимость наборов ребер в группировке). Мы рассматриваем второе расширение, которое используется более активно в следующем подразделе. Для первого метода оказалось выполнено мало работы. Используя эффективный точный алгоритм для достижимости в случае бесцикловых ориентированных графов, Раманатхан и Кольбурн [A.Ramanathan, and C.J.Colbourn, “Bounds on all-terminal reliability via arc packing”, Ars Combinatoria 23A, (1987), 91-94] получили улучшения верхних границ достижимости, а также всетерминальных верхних границ надежности. Однако использование группирования ребер с привлечение не минимальных проходов или набора разрезов не развивается, частично из-за нехватки точных алгоритмов для ограниченных классов, частично по причине трудности нахождения подходящей группы ребер.
