Форум программистов, компьютерный форум CyberForum.ru

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

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

C++ Найти покрытие полным перебором
Найти минимальное расстояние между вершинами 1 и N графа C++
Построить для заданного графа минимальное основное дерево C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 18:07     Минимальное реберное покрытие графа #16
Нужно найти минимальное остовное дерево (это Вы уже сделали). Потом осталось "немного": исключить некоторые ребра, что реберное покрытие было минимального веса.
Вообще-то "немного" оказывается довольно сложная задача. А простой перебор для 100 ребер это очень долго. Даже поискал алгоритмы через поисковики - ничего конкретного нет
Yandex
Объявления
15.05.2012, 18:07     Минимальное реберное покрытие графа
Ответ Создать тему
Опции темы

Текущее время: 16:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru