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

Задача Штейнера на графах относится оказывается к NP-hard проблемам, а значит быстрого алгоритма для общего случая не существует. Но вроде бы есть хорошие эвристические методы, например J.E.Beasley пишет в An SST-based algorithm for the Steiner problem in graphs, Networks, vol.19, no.1, 1989, pp1-16

 

Stiver

Объясню по другому. Берем граф G. Строим для него остевое дерево. Хотя бы по алгоритму Прима. Получаем некоторое дерево. Дальше удаляем лишние ветви.

Как пример пусть у нас получилось такое дерево.



(1)

|

(2)

/ | \

(3)(4)(5)

| |

(6) (7)

| |\

(8) (9)(10)



^Некоторое дерево.



Нам задано M=[2,4,5,6]. То есть мы должны удалить узлы [9,10,7,8,1] и их ребра соответственно. Чтобы не мучиться с 1 то мы должны начинать строить дерево с узла принадлежащего M.



Дальше обходом в глубину удаляем те вершины, которые не принадлежат M и из которых не выходят ребра.

получаем, то что нужно:

(2)

/ | \

(3)(4)(5)

|

(6)

 

Так как, картинка съехала опишу ребра.

Некоторое дерево

1-2

2-3

2-4

2-5

3-6

6-8

5-7

7-9

7-10

Нужный нам граф.

2-3

3-6

2-4

2-5

 

Pavia

Да, я тебя действительно неправильно понял. Но эта идея еще менее работоспособная. Возьми простейший пример:



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

g(1-2)=3, g(2-3)=3, g(1-3)=4 (g - вес ребер)

M={1,3}



и посмотри, что получится.

 

Stiver

Совершенно необязательно, что ограничение данного полного минимального остовного дерева на M будет связным



если я у связного дерева отрежу ветку, то данная ветка также будет являться связным деревом, isn't it?



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



не пойму, каким образом данный алгоритм может повлиять на связность дерева?

 

Max

Вполне может быть, что мы друг друга просто не поняли. Покажи твой алгоритм пожалуйста на примере, хотя бы на том, который я Pavia дал. А то хоть тресни не понимаю, каким образом ты собираешься добавлять

 

Stiver

вот, лови прогу в аттаче.

писалось абы работало, так что

1. на делфях(ой!)

2. алгоритмически не оптимально

3. защита от дурака по минимуму, так что аккуратно.



типа readme:

данные читаются из input.txt, там:

первая строчка - число узлов в графе

дальше ребра в формате [нач.узел]-[кон.узел],[вес]. нумерация узлов с нуля!

последней строчкой идут узлы в M.



на выходе (output.txt):

список ребер минимального остова;

список вершин скорректированного множества M + его ребра





549442771__graph.zip

 

Код (Text):

1. вход:
2.  граф G=(V,R)
3.  подмножество вершин M <V
4.  
5. начало
6.  построить отстовное дерево O=(V,P) для G
7.  пока в графе O есть вершина принадлежащая V\M из которой исходит одно ребро
8.   удалить данную вершину вместе с ребром из графа O
9. вывести граф O
10. конец

Max

ты это хотел сказать?

 

Max

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



M nodes=0,1,2

M ribs:

0-1

1-2



что естественно неправильно.

 

Stiver

а что тебе собсно не нравится?

ты и получил минимальное дерево.



added:

я имел ввиду что при входных данных

nodes=3

0-1,3

1-2,3

0-2,4

M=0,2



получаем на выходе минимальное остовное дерево по алгоритму прима

prime tree

0-1

1-2



результат, то есть M в данном случае точно равен минимальному остовному дереву

 

Black_mirror

ты это хотел сказать?

нет, причем тут вообще "одно ребро"

алгоритм такой:

Код (Text):

1.  
2.   построить отстовное дерево O=(V,P) для G
3.   для каждой пары вершин V_i,V_k do
4.     найти путь R=(N,L) от V_i до V_k в графе O
5.     отмаркировать вершины N и ребра L в графе O
6.   end;
7.   сохранить в результат все отмаркированные вершины и ребра
8.  

з.ы. при поиске пути между вершинами, ребра P рассматриваются как неориентированные

 

Max

Ну да? А по-моему 0-2 явно минимальнее

это тоже самое, что написал Black_mirror, только он немного упростил описание

 

Stiver

Ну да? А по-моему 0-2 явно минимальнее



ниче не понял 8)

у тебя в графе три вершины. остов должен пройти через все три. получается, что должно быть два ребра. ты же приводишь одно ребро.

 

Stiver

...или ты имел ввиду, что в конечном результате должно получиться 0-2 ?

тогда можно попробовать "закоротить" вершины, примерно так:

Код (Text):

1.  
2. для каждой пары вершин (i,k) do
3.   если существует ребро (i,k) в исходном графе, то
4.     определить путь из i в k
5.     если для каждого узла пути не существует других ребер, окромя входящих в путь, то
6.       если вес пути больше веса ребра, то
7.         удалить путь
8.         добавить ребро i-k

че та быстро не соображу, будет это работать?

 

Max

Ты опять не прав.



Могу привести контр пример, когда это не так.

G

(1-3)=4

(3-4)=3

(3-2)=3

(1-2)=5

M=1,2,4;

 

для Max

Еще раз объясню условие, как я его понял. Нулжно построить дерево такое, чтобы содержало все вершины M(подмножиства V). Оно должно быть наименьшим среди всего леса деревьев для множесва, которое может состоять из M и любых вершин V.

 

Pavia

Могу привести контр пример, когда это не так



на таком примере моя прога безо всяких доделок вроде правильно работает - если нумеровать узлы от 1, то получится

1-3

3-4

3-2



этож вроде и есть минимальный остов, или я опять не прав?



з.ы. мож ты не так понял - алгоритм в моем посте выше - это дошлепок к алгоритму, уже реализованному в программе, для того чтобы пофиксить случай, который привел Stiver

 

Max

А если удаляемый "дошлёпком" путь содержит узлы из M?

Может быть, вообще не стоит начинать алгоритм с нахождения минимального остовного дерева? Ведь оно не всегда содержит в себе искомое дерево. Выходит, сначала убираем рёбра, потом снова добавляем.

 

Max

Я думал это новый код. Ну тогда добавим еще один узил, правда не уверен надо код целиком смотреть.

nodes=6

1-2,5

1-3,4

1-5,3

2-3,3

3-5,3

5-4,3

M=1,2,4

Твая прога в атаче выдает полу пустой файл.

 

выдалось немножко времени - сочинил новый вариант.

проверяем...



Artem

Может быть, вообще не стоит начинать алгоритм с нахождения минимального остовного дерева?



теоретически, можно сначала минимизировать число узлов/ребер, а потом уже химичить.

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

а это не есть быстро, так что думаю быстрее будет сначала построить полный минимальный остов, а потом мудрить с ним.

можно было бы все это проверить, да времени нету - в командировку сегодня еду.

I'll be back...

882702002__graph.zip