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


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


Ничего не стоит также, чтобы любая группа ребер работоспособных субграфов G1,….,Gk, для которых легко вычислить Rel(Gi), предоставляла возможность эффективного вычисления нижней границы. Это приводит к задачам, таким как группирование ребер для последовательно-параллельных графов, или к частичным k-деревьям при фиксированном k. Этот последний подход, кажется, еще не изучен в литературе, следовательно, мы сосредоточимся на формировании групп ребер с минипроходами.

Используя теорему Таттла и Нэш-Вильямса, Полесски заметил, что граф с n вершинами и с-связанными ребрами имеет, по крайней мере,

деревьев связи с разъединенными ребрами. Следовательно, когда вероятности работоспособности всех ребер равны р, всетерминальная надежность графа равна, по крайней мере, 1-(1-pn-1)[c/2]. Когда вероятности для ребер не равны, граница Полесски естественным образом расширяется. Применение леммы 4.1 позволяет получить нижнюю границу все-терминальной надежности. Естественно, чтобы получить наилучшее ограничение на основе леммы 4.1, захочется иметь не только большое число минипроходов с разделенными ребрами, но также потребовать, чтобы эти минипроходы были надежны. Алгоритм Эдмондса не обязательно выдает набор деревьев связи, предоставляющий наилучшее ограничение при группировании ребер, использующем минипроходы. Фактически, проблема сложности нахождения набора деревьев связи, приводящих к наилучшим ограничениям при группировании ребер, остается открытой.

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

Обратимся к k-терминальной надежности, где ситуация не столь удовлетворительна.


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



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