Радиус, диаметр и центр графа

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

Эксцентриситет вершины графа – расстояние до максимально удаленной от нее вершины. Для графа, для которого не определен вес его ребер, расстояние определяется в виде числа ребер.

Радиус графа – минимальный эксцентриситет вершин, а диаметр графа – максимальный эксцентриситет вершин.

Центр графа образуют вершины, у которых эксцентриситет равен радиусу. Центр графа может состоять из одной, нескольких или всех вершин графа.

Периферийные вершины имеют эксцентриситет, равный диаметру.

Простая цепь с длиной, равной диаметру графа, называется диаметральной.

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

Теорема 12.3. Если диаметр дерева четный, то дерево имеет единственный центр, и все диаметральные цепи проходят через него, если диаметр нечетный, то центров два и все диаметральные цепи содержат ребро, их соединяющее.

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

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

Решение. В данной задаче удобно использовать матрицу расстояний S. Элемент этой квадратной симметричной матрицы равен расстоянию между вершиной i и вершиной j. Для графа, показанного на рис. 12.1, матрица расстояний имеет следующий вид:

. (12.2)

Вычислим эксцентриситет каждой вершины. Эту величину можно определить как максимальный элемент соответствующего столбца матрицы расстояний (или строки – поскольку матрица S симметрична). Получаем

№

 

Радиус графа r – минимальный эксцентриситет вершин. В данном случае r = 2. Такой эксцентриситет имеют вершины № 2, № 4 и № 5. Эти вершины образуют центр графа. Диаметр графа d – максимальный эксцентриситет вершин. В данном случае d = 3. Такой эксцентриситет имеют вершины № 1 и № 3, это периферия графа. В исследованном графе вершины оказались либо центральными, либо периферийными. В графах большего порядка существуют и другие вершины.

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

Теорема 12.4. Пусть – матрица смежности графа G без петель и , где . Тогда равно числу маршрутов длины k от вершины к вершине .

Решение задач теории графов с помощью различных преобразований матрицы смежности называют алгебраическим методом.

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

Решение. Матрица смежности данного графа равна:

.

Будем заполнять матрицу расстояний, рассматривая степени матрицы смежности. Единицы матрицы смежности показывают пары вершин, расстояние между которыми равно единице (т.е. они соединены одним ребром).

.

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

.

Согласно теореме между вершинами 2 и 3, 1 и 4 и т.д. имеется некоторое число маршрутов длиной 2 (поскольку степень матрицы равна двум). Число маршрутов здесь не используется, важен сам факт наличия маршрута и его длина, на что и указывает ненулевой элемент степени матрицы, не совпадающий с элементом, отмеченным при вычислении маршрута меньшей длины. Проставляем 2 в незаполненные элементы матрицы расстояний и получаем следующее приближение:

.

Осталось неизвестным расстояние между вершинами 1 и 3. Будем умножать матрицу смежности саму на себя до тех пор, пока в матрице не появится ненулевой элемент . Тогда соответствующий элемент матрицы расстояний равен степени матрицы смежности: . На следующем шаге получаем

,

следовательно, , и окончательно

.

Полученная матрица совпадает с матрицей расстояний S (12.2), найденной непосредственными вычислениями по рисунку.