Центр графа

Question

Для неориентированного дерева с невесомыми ребрами с N вершинами и N-1 ребрами и числом K найдите K узлов, чтобы каждый узел дерева находился на расстоянии S по крайней мере от одного из K узлов.Кроме того, S должен быть наименьшим возможным S, так что если бы было S ' Я попытался решить эту проблему, однако я чувствую, что мойПредполагаемое решение не очень быстро.Мое решение: установите x = 1, найдите узлы, которые находятся на расстоянии x от каждого узла, и пусть узел, имеющий наибольшее количество узлов на расстоянии, будет одним из K узлов.пересчитать для каждого узла, не считая уже покрытых узлов.делать это, пока я не найду число K узлов.Затем, если каждый узел покрыт, мы закончили, увеличим x.

Answer 1

Эта проблема называется p-center, и вы можете найти в Интернете несколько статей о ней, таких как this .Это действительно NP для общих графов, но многочлен на деревьях, как взвешенных, так и невзвешенных.

Answer 2

Вы говорите, N узлов и N-1 вершин, поэтому ваш граф является деревом.Вы на самом деле ищете подключенное K-подмножество узлов, минимизирующее самый длинный край.

Алгоритм полинома может быть таким: Сортировать все ваши ребра по возрастающему расстоянию.Затем выполните цикл по краям:

• , если ни один из двух узлов не входит в группу, создайте новую группу.
• В противном случае, если один узел находится в 1 существующей группе, добавьте другой кгруппа
• , в противном случае оба узла находятся в 2 разных группах, затем объедините группы

Когда группа достигнет K, разорвите цикл, и у вас будет подключенное K-подмножество.

Тем не менее, вы должны заметить, что ваша группа может содержать более K узлов.Вы можете представить себе проблему наличия 4 узлов, закрытых два на два.Не было бы точного решения вашей задачи с тремя подмножествами.

Answer 3

Для меня это похоже на проблему кластеризации.Попробуйте это с помощью алгоритма k-Means (wikipedia) , где k равно вашему K. Поскольку у вас есть дерево и все вершины соединены, вы можете использовать в качестве измерения расстояния расстояние / количество ребер между вашими вершинами.,Когда алгоритм конвертируется, вы получаете K узлов, которые должны быть найдены.Затем вы можете определить S, перебирая все k кластеров.Там вы рассчитываете максимальное расстояние для каждого узла в кластере до центрального узла.И общее максимальное значение должно быть S.

Обновление: Но на самом деле я вижу, что алгоритм k-средних не дает глобального оптимума, поэтому этот алгоритм также не даст наилучшего результата ...