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

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

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

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

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

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

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

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

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

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

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

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

Периферия графа - C++
Ребят, есть у кого код на нахождение периферии графа?

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

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

Построение графа - C++
Помогите пожалуйста написать программу вот задание:Построить копию заданного графа. граф произвольный на ваш выбор. Добавлено через...

Подобие графа - C++
Имеется примерно такой вот класс: class Room { private: string name; string story; vector <Room*> rooms; //указатели,...

построение графа - C++
Задача: "Задан граф дерево с корневой вершиной. Нужно, начиная с корневой вершины, обойти все концевые вершины (концевая вершина имеет...

Конденсация графа - C++
Найти число компонент сильной связности, вот может быть кто-нибудь реализовывал нечто подобное?


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

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

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