Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/20: Рейтинг темы: голосов - 20, средняя оценка - 4.55
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
#1

Минимальное реберное покрытие графа

13.05.2012, 14:03. Просмотров 3697. Ответов 15
Метки нет (Все метки)

Господа, подскажите пожалуйста, как реализовать эту задачу. Я так понимаю суть ее заключается ее в том, что,s необходимо найти такое множество ребер во взвешенном графе, которое бы охватывало все вершины, при этом чтобы оно было минимальной стоимости.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2012, 14:03
Ответы с готовыми решениями:

Минимальное покрытие отрезка отрезками. Рекурсия и динамическое программирование
"Дыра" и отрезки на прямой заданы целыми координатами своих концов. ...

Найти минимальное расстояние между вершинами 1 и N графа
Dev-C++ не компилирует программу Решил написать алгоритм 0,1-BFS void...

Построить для заданного графа минимальное основное дерево
Построить для заданного графа минимальное основное дерево. Помогите на С++...

По заданной матрице смежности простого графа построить каркас этого графа с использованием поиска в ширину
Задание: заданно матрицу смежности простого графа. Построить каркас этого...

Покрытие множеств
Добрый день, новичок на этом форуме =) нуждаюсь в помощи с задачей на покрытия...

15
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
13.05.2012, 19:52 #2
Цитата Сообщение от Зеленый1 Посмотреть сообщение
при этом чтобы оно было минимальной стоимости.
при этом количество ребер должно быть минимальным.
0
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
13.05.2012, 20:01  [ТС] #3
valeriikozlov, скажите, это тоже самое, что минимальное остовное дерево?
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
13.05.2012, 21:42 #4
Цитата Сообщение от Зеленый1 Посмотреть сообщение
это тоже самое, что минимальное остовное дерево?
Нет не тоже самое. Минимальное остовное дерево - обязательно связанный граф.

Минимальное реберное покрытие графа - когда количество ребер минимально и достигается условие: любая вершина графа является концевой вершиной хотя бы одного из ребер. Но в этом случае, при количестве вершин 4 и более, граф будет несвязанным.
Например есть вершины: 1, 2, 3, 4. Минимальное реберное покрытие будет например таким (указаны ребра между вершинами):
1 2
3 4
т.е. всего два ребра.
А минимальное остовное дерево для этих же вершин состояло бы из 3-х ребер.
1
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
13.05.2012, 21:57  [ТС] #5
valeriikozlov, благодарю за советы! Подскажите пожалуйста, с чего начать решать эту задачу и как.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
14.05.2012, 06:30 #6
Цитата Сообщение от Зеленый1 Посмотреть сообщение
Подскажите пожалуйста, с чего начать решать эту задачу и как.
Сначало опишите что подается на вход программы (полное условие задачи).
1
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
14.05.2012, 07:03  [ТС] #7
Пользователь рисует граф, ставит вершины по нажатию на левую кнопку мыши и ребра на правую. После того как нарисовал ребро, пользователь вводит его вес. На форме есть кнопка, по нажатию на которую по нажатию необходимо выделить цветом те ребра, которые входят в реберное покрытие. Все данные заносятся в память после того, как пользователь их ввел, то есть обратиться к определеднному ребру или вершине можно без проблем. Всю интерфесную часть реализовал, пока что в качестве алгоритма я использовал поиск минимального остовного дерева, все работает отлично.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 06:53 #8
Цитата Сообщение от Зеленый1 Посмотреть сообщение
пока что в качестве алгоритма я использовал поиск минимального остовного дерева, все работает отлично.
Ну и отлично )
1
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
15.05.2012, 11:05  [ТС] #9
valeriikozlov, так а вы же сказали, что это задача нахождения Минимального Реберного покрытия и Минимального остовного дерева - это разные задачи, или я что-то не совсем так понял..?)
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 13:00 #10
Цитата Сообщение от Зеленый1 Посмотреть сообщение
так а вы же сказали, что это задача нахождения Минимального Реберного покрытия и Минимального остовного дерева - это разные задачи, или я что-то не совсем так понял..?)
Да все правильно, это разные задачи. Но ведь Вы сами пишите:
Цитата Сообщение от Зеленый1 Посмотреть сообщение
все работает отлично.
Я так и не увидел что Вам именно нужно (условие задачи не увидел)?
Могу только предположить:
- или минимальное реберное покрытие
- или реберное покрытие с минимальным весом (склоняюсь к этому варианту, т.к. у Вас задается вес ребер)
1
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
15.05.2012, 15:27  [ТС] #11
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Я так и не увидел что Вам именно нужно (условие задачи не увидел)?
Описал и так по-моему исчерпывающе задачу.. В моей существующей программе надо заменить алгоритм Крускала на новый алгоритм, а про то что покрытие должно быть минимально по стоимости написал ещё в первом сообщении..
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 15:36 #12
Цитата Сообщение от Зеленый1 Посмотреть сообщение
а про то что покрытие должно быть минимально по стоимости написал ещё в первом сообщении..
ну да писал, не спорю:
Цитата Сообщение от Зеленый1 Посмотреть сообщение
необходимо найти такое множество ребер во взвешенном графе, которое бы охватывало все вершины, при этом чтобы оно было минимальной стоимости.
но еще писал название темы:
Цитата Сообщение от Зеленый1 Посмотреть сообщение
Минимальное реберное покрытие графа
а это совсем разные вещи.
0
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
15.05.2012, 15:48  [ТС] #13
valeriikozlov, ок, понятно, запутался в терминах. Мне нужно найти
Цитата Сообщение от valeriikozlov Посмотреть сообщение
реберное покрытие с минимальным весом
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 15:57 #14
Какое может быть максимальное количество вершин и максимальное количество ребер?
0
Зеленый1
2 / 2 / 2
Регистрация: 21.04.2011
Сообщений: 100
15.05.2012, 16:01  [ТС] #15
valeriikozlov, а это очень важно? просто не было такого условия в задаче, давайте возьмем штук 100 и вершин, и ребер.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 18:07 #16
Нужно найти минимальное остовное дерево (это Вы уже сделали). Потом осталось "немного": исключить некоторые ребра, что реберное покрытие было минимального веса.
Вообще-то "немного" оказывается довольно сложная задача. А простой перебор для 100 ребер это очень долго. Даже поискал алгоритмы через поисковики - ничего конкретного нет
1
15.05.2012, 18:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2012, 18:07

Найти покрытие полным перебором
Всем доброго времени суток. Программирование С++ изучаю недавно. Дали...

Определить, существует ли покрытие C' из C мощности не более K
УСЛОВИЕ. Задано семейство C подмножеств конечного множества S и положительное...

Покрытие шахматной доски ходом коня
4. Покрытие шахматной доски ходом коня.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru