8.5 Алгоритм генерации остовных двухсвязных подграфов заданного графа

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

Рассмотрим задачу нахождения всех остовных двусвязных подграфов графа с заданным числом ребер М, для которых диаметр (так как практическое значение имеют сети с малым диаметром). Предлагаемый алгоритм, основан на общем методе поиска с возвращением и необходимых и достаточных условиях для двусвязных графов с диаметром не превосходящим 3 [34,277]. Основные идеи предложенного алгоритма состоят в следующем.

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

В работе [4] предлагалась модифицированная процедура поиска с возвращением. Введем вектор , где если ребро не принадлежит решению, и в противном случае.

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

Покажем, что вычислительная сложность метода поиска с возвращением равна вычислительной сложности предложенной его модификации. Пусть частичным решением задачи является некоторый вектор . В известном методе поиска с возвращением для генерации решений требуется перебор векторов. В предложенном методе для генерации решений требуется перебор векторов. Следовательно как и метод поиска с возвращением, его модификация генерирует все решения без повторений и пропусков.

В процессе генерации для каждого графа проверяются следующие необходимые и достаточные условия двухсвязности.

Утверждение 1 (критерий двухсвязности). Граф G = (V,E) двухсвязен тогда и только тогда, когда для любой вершины

где - степень вершины - цикломатическое число графа

Следствие 1. Если - остовной подграф двухсвязного графа , то для любой вершины выполняется неравенство

Следствие 2. Если - двухсвязный граф, то для любой вершины

Утверждение и следствие 1 легко доказываются от противного; следствие 2 справедливо, так как цикломатическое число неотрицательно по определению.

Если граф удовлетворяет описанным выше условиям, то он является двухсвязным с диаметром если нет, то с помощью метода поиска с возвращением генерируется новый граф.

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

Продемонстрируем эффективность предложенного алгоритма, сравнив с помощью таблицы его результаты для случая со случаем полного перебора графов, и результатами работы алгоритма генерации двусвязных графов, указанного в [277].

Таблица

Из таблицы видно, что для случая, когда граф состоит из 7 вершин и 9 ребер, количество сгенерированных графов уменьшается в 24,9 раза по сравнению с известным алгоритмом, что существенно сокращает область допустимых решений для задачи (8.4)-(8.7), при Нижняя граница может быть также использована для вычисления нижней оценки стоимости сети. Очевидно, что вычисление нижней оценки стоимости следует начинать со случая .