Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4. Абсолютный центр

Соотношение (5.3) определяют числа разделения для любой вершины Мы обобщим теперь это определение на случай «искусственных» точек, которые можно помещать на дугах.

Рис. 5.2. Размещение на дуге.

Итак, если (см. рис. 5.2) представляет дугу графа с весом (длиной) то точка у, помещаемая на этой дуге, может быть определена посредством задания длины участка причем должно выполняться равенство

Числа разделения точки у независимо от того, является она вершиной графа или искусственной точкой дуги

графа определяются следующим образом:

а для соответствующее выражение получается из соотношения (5.2).

Точка у, для которой

называется абсолютным внешним центром графа; и аналогично определяется у — абсолютный внутренний центр.

Число внешнего разделения абсолютного внешнего центра называется абсолютным внешним радиусом: и число внутреннего разделения абсолютного внутреннего центра называется абсолютным внутренним радиусом:

Пример. Рассмотрим неориентированный граф показанный на рис. 5.3, где все веса вершин и длины ребер равны единице.

Рис. 5.3. Абсолютный центр.

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

Нетрудно видеть, что центром является каждая вершина и что радиус равен 2.

Если теперь выбрать точку на ребре так, что следовательно, то расстояния от этой точки до вершин графа даются таблицей

Значит, наибольшее число разделения равно Таким образом, точка более «центральна», чем любая из вершин графа В действительности точка является абсолютным центром графа так же, как и все точки, расположенные в середине ребер и Ни одна из вершин графа не является абсолютным центром. Таким образом, в общем случае может быть один или больше абсолютных центров, которые располагаются или в вершинах, или на дугах графа.

<< Предыдущий параграф Следующий параграф >>
Оглавление