8.6 Характеристики некоторых экстремальных графов. Теорема о нижней границе числа ребер

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

Пусть дан граф . содержащий вершин и ребер.

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

Обозначим через класс графов с диаметром что для любой вершины класс графов с диаметром что для любого ребра . Пусть - число ребер в экстремальных графах класса соответственно. В работах зарубежных авторов 60-80-х гг. изучались случаи, когда удаляются только вершины или только ребра. Были найдены экстремальные графы для различных значений Результаты этих исследований использовались в работе [65] при составлении алгоритмов топологической оптимизации сети. Однако в процессе совершенствования этих алгоритмов возникла необходимость найти все экстремальные графы класса

Рис. 8.2

Рис. 8.3

Рис. 8.4

Оценим значение Рассмотрим граф на рис. 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.

(см. скан)

Рис. 8.5