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


Группирование ребер - часть 3


Здесь минипутем является субдерево, в котором каждый листик представляет собой терминал, т.е. дерево Штайнера. Оказалось, что никакой эвристики для нахождения “хороших” групп ребер для деревьев Штайнера не найдено.

До этого момента мы рассматривали нижние границы, базируясь на методике группирования ребер в рамках минипроходов. Теперь обратимся к верхним границам. Не удивительно, что лемма 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-трудным. Таким образом, верхняя граница всетерминальной надежности может быть получена путем использования ограничения группирования дуг для достижимости.




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