Графы: неполное минимальное остовное дерево

Встала следующая задача:



Дан неориентированный связный граф G=(V,E), где V - вершины, E - ребра. Каждое ребро имеет определенный вес(целое положительное число). Дано подмножество

M вершин того же самого графа, т.е. M является правильным подмножеством множества V (M<V). Нужно построить минимальное остовное дерево для M, т.е. связный ацикличный граф P=(W,I) где M<W<V и I<E с минимальным общим весом ребер I.



Сначала я решил, что это частный случай обыкновенного остовного дерева и решается соответственно например тем же алгоритмом Прима. Через некоторое время понял, что не все так просто..



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



Если кому интересно: задача возникла в процессе написания оптимизатора команд SQL(вернее HQL: Struts,Hibernate,MySQL муть та еще!).

 

не совсем понятно - путь от M(i) до M(j) может проходить через узел V(k), который отсутствует в M.

что тогда происходит с путем - M(i) соединяется с M(j), или связь разрывается?



имхо тебе надо на основе графа G построить граф U(M,x) а к нему применять стандартные алгоритмы.

только вот как формировать ребра графа U - it all depends...

 

Max

Соединяется. Понятно, что в общем случае только вершинами из M не обойтись, поэтому я и написал:

 

Stiver

насколько я понимаю, остов графа должен пройти через все его вершины, isn't it?

тогда при построении остова для M ты должен получить P=(M,I).

а ты в условии пишешь P=(W,I), да еще и M<W.

 

Max

Да, конечно. P должен пройти через все вершины из M, но не обязан проходить _только_ через них.



Например:

G=(V,E): V={1,2,3,4} E={(1-2),(1-3),(2-3),(3-4)}



Вес ребер описывается функцией g: g(1-2)=4,g(1-3)=3,g(2-3)=2,g(3-4)=5



M={1,2,4}



В результате получаем:

P=(W,I): W={1,2,3,4} I={(1-3),(2-3),(3-4)} где M<W<=V, I<E

 

Stiver

тебе надо просто выполнить 3 этапа:



1. сворачиваем граф G=(V,E) к графу P(M,J). Входными данными является множество вершин M, выходными - множество ребер J.

M и J представляются ссылками на исходные множества V,E.

Для приведенного тобой примера получим:

M={1,2,4}

J={(1-2),(1-3-4),(2-3-4)}

то есть, ты представляешь ребро как бы двумя вершинами множества M, но при этом хранишь информацию о том, что это ребро представляет собой в графе G.

алгоритмически это несложно - типа волнового алгоритма и вперед



2. Применяешь стандартный алгоритм к графу P.



3. После получения остова, разворачиваешь граф P к графу G'. То есть делаешь задачу обратную п. 1.

Изначально W=M. В процессе разворота (анализа ребер J), может оказаться, что в ребре J присутствует ссылка на вершину V, которая отсутствует в W. При этом добавляешь ее в W. Ну и попутно разворачиваешь ребра - получишь множество I.



з.ы. надеюсь, понятно написал

 

Stiver

вот, я тебе картинку даже нарисовал от нефиг делать

слева направо:

1. исходные данные

2. сворачиваем граф

3. строим остов

4. разворачиваем остов



_903167063__struct.gif

 

Stiver

лажанулся я немного, не спал я еще - после свертки будет еще ребро {1,3,4} между вершинами 1 и 4 - ну да один хрен, представь себе, что при построении остова оно "ушло", дальше рисунок правильный.

смысл надеюсь понятен.

 

Max

Объяснил понятно, спасибо. А картинки так и вовсе замечательные В первом посте ты правда забыл ребро 1-3-2, а во втором ребро 1-3-4, но это в данном случае несущественно.



Непонятно другое: как ты из второй картинки получил третью? После второго шага(сворачивания графа) имеем

g(1-2)=4, g(1-3-2)=5, g(2-3-4)=7, g(1-3-4)=8

Если применить алгоритм Прима с началом в вершине 1 (или Крускала), то получим(в неразвернутом виде)

P=({1,2,4},{(1-2),(2-3-4)}), а вовсе не P=({1,2,4},{(1-3-2),(2-3-4)}) как у тебя на рисунке! В этом-то и беда.

Я тоже сначала пошел этим путем, см.

но он как видно не работает. Или я ошибаюсь?



Добавил: когда писал, твоего последнего поста еще не было

 

Stiver

Непонятно другое: как ты из второй картинки получил третью?

от балды - веса я не рассматривал.

просто хотел показать как это дело сворачивается/разворачивается.



но он как видно не работает. Или я ошибаюсь?



я уже совсем плохо врубаюсь, но давай посчитаем по алгоритму Прима от точки 1, то есть U={1}, V={2,4}.



1. Берем ребро с минимальным весом между U и V, то есть (1-2).

U={1,2}, V={4}



2. Опять берем ребро, теперь это будет (2-4)

U={1,2,4}, V={}



3. V={} - the end



итого получили остов из ребер (1-2) и (2-4), детально их можно записать как (1-2) и (2-3-4)



после разворота получим остов (1-2),(2-3),(3-4).



и че тут тебя смущает?

 

Max

?! Эээ.. Вопрос был получить _минимальное_ остовное дерево. Найти _произвольное_("от балды") остовное дерево и я могу

То что ответ не является минимальным остовным деревом.

G({(1-2),(2-3),(3-4)})=11 тогда как G({(1-3),(2-3),(3-4)})=10.

 

Stiver



тю, так тогда еще проще



строишь минимальный остов для исходного графа G=(V,E).

как пишут в умных книжка - очевидно(!) , что пересечение данного остова с множеством вершин M графа P(M,J) (ребра J мы пока не знаем) будет являться также минимальным остовом для графа P (т.к. множество M в точности входит в V, а J в E).



для определения J делаем следующее - пробегаем волновым алгоритмом по всем путям между вершинами M в множестве ребер минимального остова и все пробегаемые ребра копируем в J



that's all... вроде как...



added: пока бегаешь по остову (соответственно по вершинам V), проверяешь, что если пробегаемая вершина не входит в M, то добавляешь ее туда

 

Stiver

Эта задача называется задачей Штейнера на графах. Вот что пишет Ф.Кристофидес в книге "Теория Графов. Алгоритмический подход":

Задача Штейнера для обычных неориентированных графов рассмартивалась Хакими [Hakimi S.L. (1971), Steiner's problem in graphs and its implementation, Networks 1, p. 113.] и Дрейфусом и Вагнером [Dreyfus S.E., Wagner R.A. (1972), The Steiner problem in graphs, Networks, 1, 195.]. Они нашли точные алгоритмы решения таких задач. Однако эти алгоритмы с вычислительной точки зрения не являются эффективными процедурами, хотя они и значительно лучше, чем последовательный просмотр минимальных остовных деревьев всех подграфов G' графа G. В любом случае (как и в случае задач с евклидовым расстоянием) максимальный размер задач Штейнера, для решения которых требуется разумное вычислительное время, не превышает 10 вершин (в подмножестве вершин которое нужно соединить). С этой точки зрения задачу Штейнера на графе можно рассматривать как нерешенную проблему, и она в этой книге больше рассматриваться не будет.



Хотя книга вышла в 1978 году, но я сомневаюсь что число вершин для которого можно решить эту задачу за разумное время(с учетом возросшего быстродействия ЭВМ) стало больше 15.

 

Black_mirror

Эта задача называется задачей Штейнера на графах

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



в постановке задачи Stiver'а это не так, и это внатуре используется при оптимизации запросов -

например, определить наилучший порядок использования индексов таблицы в процессе выборки.

 

Max

Ты говоришь о задаче Штейнера с евклидовым расстоянием, я же процитировал абзац о Задаче Штейнера для обычных неориентированных графов, только в отличии от первого сообщения Stiver'а в книге написано M<=W<=V, то есть не исключается вариант что M совпадает с W или W совпадает с V.

 

Black_mirror

...В любом случае (как и в случае задач с евклидовым расстоянием) максимальный размер задач Штейнера, для решения которых требуется разумное вычислительное время, не превышает 10 вершин (в подмножестве вершин которое нужно соединить). С этой точки зрения задачу Штейнера на графе можно рассматривать как нерешенную проблему...



так тогда получается, что предложенный алгоритм в моем посте от Мар 11, 2005 15:29:25 является неверным?

еще раз прикинул - вроде все должно работать, причем довольно шустро.

Кто раскритикует?



з.ы. а Relf тут случаем не бывает?

 

Лучше использовать метод Дж. Краскала для нохождения остовного дерева. Для графа G c учетом выхода из цикла когда все вершины M будут задействованы. После обходом в глубину удоляем все ветви дерева, которые заканчиваются на вершину не принадлежашию M.

 

А вобще стришь остовного дерева любым способом. А потом отсекаем не нужные ветки.

 

Max

Обязательно раскритикуем Может оно и очевидно, но к сожалению неверно. Ты забываешь, что минимальный остов должен быть связным графом(потому и называется - остовное _дерево_). Совершенно необязательно, что ограничение данного полного минимального остовного дерева на M будет связным. На самом деле даже нет гарантии, что существует такое минимальное остовное дерево для G, что его пересечение с M будет связным. Именно поэтому при решении в лоб требуется

Всех подграфов графа G, а не просто G!. То же самое относится и к



Pavia

В общем случае получится не дерево, а лес деревьев.



Black_mirror



Спасибо большое, попробую теперь поискать информацию по задаче Штейнера.

То есть M должно быть не больше 10, или W? А от размера V зависимости нет? Если M тогда мне это подойдет, в 10 вершин я точно уложусь.

Равенства конечно возможны и разрешены, я просто не хотел обсуждения здесь экстремальных случаев.

 

Stiver

В книге указывалось что M, но книга 1978 года, может за прошедшее время китайцы придумали как быстро решать эту задачу для M значительно больше 10 8)