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

6. Кратные центры (р-центры)

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

Пусть подмножество (содержащее вершин) множества X вершин графа Через будем обозначать наикратчайшее из расстояний между вершинами множества и вершиной т. е.

Аналогично, символом обозначается

Подобно тому, как определялись числа разделения вершин (см. разд. 3), мы можем определить числа разделения для множеств вершин:

и

где числа внешнего и внутреннего разделения множества

Множество для которого

называется -кратным внешним центром графа аналогично определяется -кратный внутренний центр

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

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