Помогите люди добрые... (задача о графе)

Мне надо решить задачу...а я не могу(( Выручите меня пожалуста кто чем сможет, я на вас молиться буду!

Задан раф G=<V,E>положительный целый вес W(e) каждого ребра е принадлежащего Е , подмножества R и положительное целое число В
Вопрос:
Существует ли в графе G дерево, содержащее все вершины из R, что сущ весов ребер этого поддерева не привосходит В?

Люди добрые..я сам в этом ваще не рулю...помогите пожалуйста, очень вас прошу!

 

Надо полагать "сумма весов ребер"?
Если так и есть, то я бы осуществил это дело так:

создаем граф Г
инициализируем S нулем (значение суммы весов ребер графа Г)
добавляем в граф Г все вершины из R
пока не получился связанный граф
{
найти ребро с минимальным весом, исходящее из одной из вершин графа
добавить к графу вершину, в которую ведет это ребро (если она не добавлена)
добавить к S вес найденного ребра
}
условие выполнится, если S <= B

 

GIo
Я не понял - задача чисто абстрактная? Или алгоритмическая?
Если абстрактная, то видимо нужно задать вопрос на каком-то математическом форуме или поискать в графах.
Если алгоритмическая, см. пост 2.

 

dr_dred
Видимо, не совсем так.
По-моему, в граф Г не надо сразу добавлять все вершины из R, а то у тебя получится, что алгоритм каждый раз будет находить ребро с минимальным весом и добавлять его, хотя, возможно, это и не надо. Т.е. он соберет все ребра с минимальным весом, пока не наберет связанный граф (к тому же, так могут появиться циклы).

Вот моя версия (если GIo нужно объяснение, то см. алгоритм Прима):

создаем граф Г
инициализируем S нулем (значение суммы весов ребер графа Г)
добавляем в граф Г любую вершину из R
пока Г не содержит в себе R
{
найти ребро с минимальным весом, исходящее из вершины из Г,
и входящее в вершину не из Г
добавить к графу Г вершину, в которую ведет это ребро
добавить к S вес найденного ребра
}
условие выполнится, если S <= B

 

GIo
В развитие топика maxdiver:
http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2005
Если сумма весов минимального покрывающего дерева будет больше твоего B, то искомое дерево не существует. Если <= B, то существует и является искомым.

 

crypto

Не согласен. Ведь задача как стоит: "дерево, содержащее все вершины из R", а не остовное дерево. Так что сумма весов ребер остовного дерева может превосходить B, а вот некоторое поддерево остовного дерева будет содержать все вершины R и "весить" меньше B.

 

maxdiver
Дык минимальное покрывающее дерево как-раз и содержит все вершины исходного графа.
Формулировка проблемы.

 

crypto
Я говорю про задачу в первом посте

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

 

maxdiver
Подмножество R выпало из поля зрения Тогда может быть свести задачу к нахождению минимального остовного дерева для подграфа заданного графа с множеством вершин R?

 

crypto
Видимо, это не пройдет. Если вообще отбросить все вершины не из R и все соответствующие ребра, то вместе с ними мы можем потерять и более короткие пути.
Всё-таки весь граф нужно сохранять целиком, просто условие завершения алгоритма Прима должно измениться - не когда получим все V, а когда получим >=R, как в посте №4.

 

maxdiver
Похоже на то... А что-то топикстартер у нас молчит?

 

Чуваки спасибо большое.....
))) Но когда я написал что я не рулю в этом....я имел в виду что ваще нехрена не понимаю...это моя курсовая задача....я даже код не могу составить((((((((( Вот так вот у меня все хренова! (( Спосибо вам большое! =) Да же не знаю ваще как эту задачу теперь сдавать....(

 

GIo
Ты хотя бы скажи, на каком языке
Могу запросто написать на C++, там писать-то нечего.

 

Буду очень благодарен... на С++

 

maxdiver
от чего могут циклы появиться?

вроде старался все учесть

 

maxdiver
пожалуй, я все таки не соглашусь

 

dr_dred
Ну если я правильно понял твой алгос, то вот тест, на котором он завалится:
вершина_1, вершина_2, вес_ребра:

1 2 1
2 3 2
1 3 3
2 4 4

Твой алгос возьмёт все рёбра, а мой - только с весами 1,2,4

GIo
Завтра напишу прогу.

 

maxdiver

Спасибо тебе большое! Я на тебя молиться буду))

 

maxdiver
понято, спасибо, потесть свой алгоритм на этом примере:

V:
1 2 1
2 3 3
1 4 2

R: (vertex1, vertex2, ..., vertexn)
1,2,3

B=4

По-моему не прокатит тоже.

Если интересно, для разработки программы могу предложить использовать w32topl.dll. Она содержит функции для работы с графами. Прототипов функций нигде не нашел, но могу пояснить что какая функция делает в кратце (которые знаю).

 

maxdiver
к твоему алгоритму надо добавить удаление лишних веток, не соединяющих вершины R. Главное тут ничего лишнего не удалить))