Задача о k-центрах в графе: постановка и алгоритмы

Задача о k-центрах в графе - это классическая задача размещения: нужно выбрать $k$ вершин-«центров» так, чтобы любая вершина графа оказалась как можно ближе к ближайшему из них. Она возникает в логистике (где поставить $k$ складов), в проектировании сетей (где разместить серверы или ретрансляторы) и в кластеризации данных. Формально это минимаксная оптимизационная задача, и в общем случае она NP-трудна, поэтому на практике решают её приближённо. Разберём строгую постановку, почему точное решение тяжело и как работает классический жадный алгоритм с гарантией качества.

Постановка задачи

Дан связный граф $G = (V, E)$ с заданными расстояниями $d(u, v)$ между вершинами (длинами кратчайших путей) и число $k$. Требуется выбрать множество центров $C \subseteq V$ размера $|C| = k$ так, чтобы минимизировать наибольшее расстояние от любой вершины до ближайшего центра.

Введём функцию покрытия - расстояние от вершины $v$ до множества центров $C$:

$d(v, C) = \min_{c \in C} d(v, c).$

Тогда стоимость размещения $C$ - это радиус покрытия:

$\operatorname{cost}(C) = \max_{v \in V} d(v, C),$

а сама задача о k-центрах формулируется как

$\min_{\substack{C \subseteq V \\ |C| = k}} \; \max_{v \in V} \; \min_{c \in C} d(v, c).$

Оптимальное значение $r^* = \operatorname{cost}(C^*)$ называют оптимальным радиусом: при размещении $k$ центров никакая вершина не окажется дальше $r^*$ от ближайшего из них. Структура «мин-макс-мин» и делает задачу нетривиальной.

Чтобы прочувствовать постановку, удобно сразу прогнать конкретный граф: задать рёбра, число $k$ и посмотреть, какие центры минимизируют максимальное расстояние. Инструмент ниже соберёт корректный запрос с пошаговым разбором.

Минимаксный критерий и его смысл

Ключевая особенность задачи о k-центрах - именно минимаксный (а не суммарный) критерий. Мы минимизируем худший случай: расстояние до самой неудачно расположенной вершины. Это отличает её от задачи о k-медианах, где минимизируют сумму $\sum_{v} d(v, C)$, и от задачи о покрытии множества.

Минимаксный критерий уместен там, где важна гарантия для каждого потребителя, а не средняя по всем. Если центры - это пожарные части или станции скорой помощи, то «средняя» близость бесполезна: критично, чтобы даже самая удалённая точка обслуживалась за приемлемое время. Поэтому задача о k-центрах - это модель «справедливого» размещения с гарантией наихудшего случая.

Связь с радиусом и эксцентриситетом

При $k = 1$ задача вырождается в поиск одной вершины с минимальным эксцентриситетом. Напомним, эксцентриситет вершины - это $\varepsilon(v) = \max_{u} d(v, u)$, и наименьший эксцентриситет по графу есть радиус:

$r(G) = \min_{v \in V} \varepsilon(v).$

При $k = 1$ оптимальный радиус покрытия $r^*$ совпадает с радиусом графа $r(G)$, а единственный центр - это центральная вершина графа. Подробнее о том, как считать эти величины, - в разборе про радиус и диаметр графа и отдельно про эксцентриситет вершины. Задача о k-центрах обобщает эту идею: вместо одной «удобной» точки мы ищем $k$ точек, совместно покрывающих граф с минимальным радиусом.

С ростом $k$ оптимальный радиус $r^*$ монотонно не возрастает: добавление центра не может ухудшить покрытие. В предельном случае $k = |V|$ можно поставить центр в каждую вершину и получить $r^* = 0$.

Почему задача NP-трудна

Точное решение задачи о k-центрах в общем случае невозможно за полиномиальное время (если $P \ne NP$). Доказательство - сведение от задачи о доминирующем множестве. Доминирующее множество размера $k$ существует тогда и только тогда, когда $k$ центров покрывают граф с радиусом $r^* \le 1$. Поскольку проверка существования доминирующего множества заданного размера NP-полна, NP-трудной оказывается и задача о k-центрах.

Более того, доказано, что задачу нельзя приблизить с коэффициентом лучше $2$: не существует полиномиального алгоритма, гарантирующего решение с радиусом строго меньше $2r^*$ (опять же при $P \ne NP$). Это делает значение $2$ особенным - и хорошая новость в том, что эта граница достижима.

Жадный алгоритм Гонзалеса (2-приближение)

Существует простой жадный алгоритм (farthest-first traversal, алгоритм Гонзалеса), который гарантирует радиус не более $2r^*$ - то есть достигает теоретического предела приближения.

Идея - «расставлять центры как можно дальше друг от друга»:

1. Выбираем произвольную вершину первым центром: $C = \{c_1\}$.
2. Пока $|C| < k$: находим вершину $v$, наиболее удалённую от текущего множества центров (максимизирующую $d(v, C)$), и добавляем её в $C$.
3. После выбора $k$ центров итоговый радиус покрытия равен $\max_v d(v, C)$.

Интуиция гарантии: алгоритм всегда «затыкает» самую дальнюю дыру в покрытии. Когда мы добавили $k$ центров, оставшийся максимум $d(v, C)$ не превышает расстояния между двумя ближайшими из выбранных «далёких» точек, а оно, в свою очередь, ограничено $2r^*$ через неравенство треугольника.

Доказательство оценки 2r*

Покажем, почему алгоритм Гонзалеса не превосходит $2r^*$. Пусть после работы алгоритма нашлась вершина $x$ с $d(x, C) = R$ - это и есть полученный радиус. По жадному правилу любые два выбранных центра отстоят друг от друга не менее чем на $R$, и сама $x$ отстоит от всех центров не менее чем на $R$. Значит, у нас есть $k + 1$ точка (k центров плюс $x$), попарно удалённых не менее чем на $R$.

В оптимальном решении эти $k + 1$ точку покрывают всего $k$ центров, поэтому по принципу Дирихле какие-то две из них $a, b$ попадают в зону одного оптимального центра $c^*$. Тогда $d(a, c^*) \le r^*$ и $d(b, c^*) \le r^*$, откуда по неравенству треугольника

$R \le d(a, b) \le d(a, c^*) + d(c^*, b) \le 2r^*.$

Следовательно, радиус, выданный алгоритмом, не превосходит $2r^*$. Эта оценка точная и совпадает с нижней границей неприближаемости.

Параметрический подход и бинарный поиск

Альтернатива жадному методу - свести оптимизацию к серии задач разрешимости. Зафиксируем порог $R$ и спросим: можно ли покрыть граф $k$ центрами с радиусом $\le R$? Это «задача о порогах»: строим пороговый граф $G_R$, оставляя ребро между вершинами, если $d(u, v) \le R$, и проверяем, хватит ли $k$ доминирующих центров.

Перебирая кандидатов $R$ (а их не больше $\binom{n}{2}$ различных значений расстояний) бинарным поиском, можно найти минимальный допустимый порог. На этой идее основан точный алгоритм Ху и приближённый алгоритм с тем же коэффициентом $2$. Для учебных целей бинарный поиск по значениям расстояний - наглядный способ понять, что оптимальный радиус всегда равен одному из попарных расстояний в графе.

Частые ошибки

• Минимизируют сумму расстояний вместо максимума. Сумма $\sum_v d(v, C)$ - это уже задача о k-медианах, у неё другие оптимумы и другие алгоритмы.
• Считают, что жадный алгоритм даёт точный оптимум. Он гарантирует лишь $\le 2r^*$; реальный оптимум часто меньше.
• Забывают, что центры обязаны быть вершинами графа. В «вершинной» постановке $C \subseteq V$; если центр можно ставить в любой точке ребра, это уже непрерывная (абсолютная) задача о центрах.
• Путают $k$-центры с $k$-кликами или $k$-раскраской - это разные задачи, совпадает лишь буква $k$.
• Применяют задачу к несвязному графу без оговорок. Если граф несвязен, вершины из разных компонент недостижимы, $d(v, C) = \infty$, и нужно отдельно оговаривать покрытие по компонентам.

FAQ

Чем k-центры отличаются от k-медиан? Критерием. В k-центрах минимизируют максимум расстояния (худший случай), в k-медианах - сумму расстояний (средний случай). Оптимальные размещения и алгоритмы у них разные, хотя постановки внешне похожи.

Можно ли решить задачу точно? Для небольших графов - да, полным перебором всех $\binom{n}{k}$ подмножеств вершин или бинарным поиском по порогу $R$. Для больших - нет: задача NP-трудна, и в общем случае ограничиваются 2-приближённым алгоритмом.

Почему именно коэффициент 2 считается оптимальным? Доказано, что приблизить задачу лучше чем в $2$ раза за полиномиальное время невозможно (при $P \ne NP$), а жадный алгоритм Гонзалеса этот коэффициент $2$ достигает. Поэтому $2$ - одновременно нижняя и верхняя граница приближаемости.

Коротко

Задача о k-центрах в графе - это выбор $k$ вершин-центров, минимизирующий максимальное расстояние от любой вершины до ближайшего центра: $\min_{|C|=k} \max_v \min_{c} d(v, c)$. При $k = 1$ ответом служит центр графа с радиусом $r(G)$. Задача NP-трудна (сведение к доминирующему множеству) и неприближаема лучше чем в $2$ раза. Зато жадный алгоритм Гонзалеса, расставляющий центры «как можно дальше друг от друга», гарантирует радиус не более $2r^*$ - и это оптимальная достижимая граница.