Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.61
Зеленый1
2 / 2 / 0
Регистрация: 21.04.2011
Сообщений: 100
#1

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

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

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

Найти минимальное расстояние между вершинами 1 и N графа - C++
Dev-C++ не компилирует программу Решил написать алгоритм 0,1-BFS void BFS(int** MasList, int** MasListW, int& N,int& S){ int*...

Построить для заданного графа минимальное основное дерево - C++
Построить для заданного графа минимальное основное дерево. Помогите на С++ написать задачку) Найти минимальный путь.

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

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

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

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

15
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
13.05.2012, 19:52 #2
Цитата Сообщение от Зеленый1 Посмотреть сообщение
при этом чтобы оно было минимальной стоимости.
при этом количество ребер должно быть минимальным.
0
Зеленый1
2 / 2 / 0
Регистрация: 21.04.2011
Сообщений: 100
13.05.2012, 20:01  [ТС] #3
valeriikozlov, скажите, это тоже самое, что минимальное остовное дерево?
0
valeriikozlov
Эксперт С++
4672 / 2498 / 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, благодарю за советы! Подскажите пожалуйста, с чего начать решать эту задачу и как.
0
valeriikozlov
Эксперт С++
4672 / 2498 / 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
Пользователь рисует граф, ставит вершины по нажатию на левую кнопку мыши и ребра на правую. После того как нарисовал ребро, пользователь вводит его вес. На форме есть кнопка, по нажатию на которую по нажатию необходимо выделить цветом те ребра, которые входят в реберное покрытие. Все данные заносятся в память после того, как пользователь их ввел, то есть обратиться к определеднному ребру или вершине можно без проблем. Всю интерфесную часть реализовал, пока что в качестве алгоритма я использовал поиск минимального остовного дерева, все работает отлично.
0
valeriikozlov
Эксперт С++
4672 / 2498 / 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, так а вы же сказали, что это задача нахождения Минимального Реберного покрытия и Минимального остовного дерева - это разные задачи, или я что-то не совсем так понял..?)
0
valeriikozlov
Эксперт С++
4672 / 2498 / 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 Посмотреть сообщение
Я так и не увидел что Вам именно нужно (условие задачи не увидел)?
Описал и так по-моему исчерпывающе задачу.. В моей существующей программе надо заменить алгоритм Крускала на новый алгоритм, а про то что покрытие должно быть минимально по стоимости написал ещё в первом сообщении..
0
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 15:36 #12
Цитата Сообщение от Зеленый1 Посмотреть сообщение
а про то что покрытие должно быть минимально по стоимости написал ещё в первом сообщении..
ну да писал, не спорю:
Цитата Сообщение от Зеленый1 Посмотреть сообщение
необходимо найти такое множество ребер во взвешенном графе, которое бы охватывало все вершины, при этом чтобы оно было минимальной стоимости.
но еще писал название темы:
Цитата Сообщение от Зеленый1 Посмотреть сообщение
Минимальное реберное покрытие графа
а это совсем разные вещи.
0
Зеленый1
2 / 2 / 0
Регистрация: 21.04.2011
Сообщений: 100
15.05.2012, 15:48  [ТС] #13
valeriikozlov, ок, понятно, запутался в терминах. Мне нужно найти
Цитата Сообщение от valeriikozlov Посмотреть сообщение
реберное покрытие с минимальным весом
0
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.05.2012, 15:57 #14
Какое может быть максимальное количество вершин и максимальное количество ребер?
0
Зеленый1
2 / 2 / 0
Регистрация: 21.04.2011
Сообщений: 100
15.05.2012, 16:01  [ТС] #15
valeriikozlov, а это очень важно? просто не было такого условия в задаче, давайте возьмем штук 100 и вершин, и ребер.
0
15.05.2012, 16:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2012, 16:01
Привет! Вот еще темы с ответами:

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

Покрытие графа путями - Алгоритмы
Задача такая: есть двунаправлный граф с весами (сеть дорог), есть n машин, которые расположены в k вершин ( 0 < k <= n, то есть в каждой...

построить деревянное покрытие графа - Prolog
Ребят помогите с заданием, вообще не пойму как делать...

Раскраска графа в минимальное кол-во цветов - Delphi
Здравствуйте. Скажите,как можно реализовать раскраску графа в минимальное количество цветов. Раскраска должна производиться таким...


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

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

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