Абсолютный P-центр неорграфа , (разделено)

Всем привет!
Не могу решить задачу : Нахождение абсолютного p-центра в неориентированном графе.

http://rain.ifmo.ru/cat/view.php/theory/graph-location/centers-2004

Цитата

Идея этого алгоритма состоит в построении специальных областей Φλ(Vk), где Vk ∈ V — множество из k вершин, таких, что любая вершина vi ∈ Vk достижима из любой точки этой области путем, длина которого не привосходит λ, а если vi ∈ Vk, то ни для какой точки Φλ(Vk) это не выполняется (другими словами области не пересекаются).

Любая точка графа попадает в некоторую область Φλ(Ø) = {y ∈ G: ∀X ⊆ V y∈ Φλ(X)} — область, из которой ни одна вершина не доступна путем не превосходящим λ.

Для того, что бы построить эти области, сначала строят множества Qλ(xi) = {y ∈ G: l(y,xi) ≤ λ}, т. е. множество всех точек, из которых xi достижима не более чем за λ. Тогда Φλ(Vk) можно выразить как через Qλ(xi) следующим образом

Φλ(Vk) = (∩Qλ(xi)) \ (∪Qλ(xj)),
где xi ∈ Vk, а xj ∈ Vk.

Выберем некоторое δ > 0. Положим λ = δ.
Построим множества Qλ(xi) для всех xi.
При помощи Qλ(xi) построим области Φλ(Vk).
Построим двудольный граф G′ = (V′ ∪ V, E′), где V′ — множество вершин, каждая из которых соответствует некоторой области Φλ(Vk), а E′ — множество дуг, такое, что дуга между вершиной-областью и вершиной xi существует тогда и только тогда, когда xi может быть достигнута из этой области.
Найти наименьшее доминирующее множество графа G′.
Если число областей в этом множестве больше, чем p, то увеличить λ на δ и вернуться к шагу 2; в противном случае остановиться. Области этого множества образуют абсолютный p-центр графа G, а λ является абсолютным p-радиусом.
Погрешность в определении центра и соответствующей λ линейно зависит от δ. В процессе работы этого алгоритма будут также найдены абсолютные (n-1)-, (n-2)- и т. д. центры.

Определим множества Qλ(xi) как множества вершин, из которых xi достижима не более чем за λ, а области Φλ(Vk) как множество вершин такое, что любая вершина из Vk достигается из любой вершины Φλ(Vk) не более чем за λ, и нет такой вершины xj ∈Φλ(Vk), из которой достижима менее чем за λ вершина не принадлежащая Vk. Тогда результатом работы данного алгоритма будет обычный (не абсолютный) p-центр.

Проблема в том, что я никак не могу построить эти самые области Φλ(Vk).

Эта тема была разделена из темы "нахождение центра ориентированного графа"

лучше наверное создайте новую тему

Сообщение отредактировано: FasterHarder - 17.04.08, 11:55