Оценим значение Рассмотрим граф на рис. 8.2. Это граф класса Операция дублирования любой вершины степени 2 (на рис. 8.2 изображена штрихпунктиром) приводит к графу класса Применяя эту операцию многократно, получаем серию графов класса которых Рассмотрим также графы на рис. 8.3 и 8.4 а, 8.4 б. Используя операцию дублирования для графов на рис. 8.3 и 8.46, получаем серии графов класса Следовательно, для для для Можно показать, что полученные для числа М неравенства являются равенствами для указанных значений N и справедлива следующая теорема об экстремальных графах класса
ТЕОРЕМА. Для экстремальных графов класса
Экстремальный образующий граф в случае изображен на рис. 8.3.
Доказательство этой и других теорем, характеризующих экстремальные графы, описаны в работах [4,286,288].
Указанная теорема имеет большое значение для решения задачи так как позволяет вычислять нижнюю границу числа ребер и кроме того определяет единственное решение для экстремальных графов, описывающих компьютерные сети большой размерности.
При любой экстремальный граф строится на базе графа, изображенного на рисунке 8.3, с помощью операции дублирования вершины степени 2 в этом графе.
Таким образом мы описали все основные этапы комбинаторного алгоритма синтеза топологической структуры:
— вычисление нижней границы числа ребер в графе;
— генерация остовных двухсвязных подграфов заданного графа;
— вычисление нижней оценки стоимости сети;
— проверка ограничений
Схема комбинаторного алгоритма приведена на рисунке 8.5.