Графы: 3.6. Радиус и диаметр

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

Для фиксированной вершины целое число

соответствует расстоянию от до вершины (или вершин), наиболее удаленной от Интуитивно понятно, что вершина является относительно центральной, если относительно мало. Поэтому естественно назвать

радиусом графа и считать вершину центром графа, если

Рис. 3.30.

На рис. 3.30, показаны графы, имеющие соответственно радиусы 1 и 3. Граф может иметь несколько центров. Например, на рис. каждая вершина является центром.

Диаметром связного графа является максимальное расстояние между парами вершин или в символической записи

Графы, показанные на рис. 3.30, имеют соответственно диаметры 2 и 3. Из второго примера видно, что радиус и диаметр связного графа могут быть равны.

Упражнения

(см. скан)

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

Если является сильно связным графом, то радиус, диаметр и центр формально определяются в точности, как в неориентированном случае при использовании нового определения Чтобы избежать двусмысленности, радиус и диаметр в ориентированном случае будем обозначать

На рис. 3.31 показан ориентированный граф полученный из неориентированного графа рис. 3.30, а наиболее неудачной ориентацией ребер. Нетрудно видеть, что этот граф сильно связен и что вершины являются центрами.

Рис. 3.31.

Кроме того, и соответствует единственному простому пути из Таким образом, в ориентированном случае радиус

может быть меньше диаметра более чем вдвое. Это в конечном счете следует из асимметрии расстояния в ориентированном случае. (Заметим, например, что на рис. 3.31 мы имеем

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