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

@Зеленый1 · Регистрация: 21.04.2011

Author24 — интернет-сервис помощи студентам

Господа, подскажите пожалуйста, как реализовать эту задачу. Я так понимаю суть ее заключается ее в том, что,s необходимо найти такое множество ребер во взвешенном графе, которое бы охватывало все вершины, при этом чтобы оно было минимальной стоимости.

valeriikozlov · 13.05.2012, 19:52

Сообщение от Зеленый1

при этом чтобы оно было минимальной стоимости.

при этом количество ребер должно быть минимальным.

@Зеленый1 · 13.05.2012, 20:01 **[ТС]**

valeriikozlov, скажите, это тоже самое, что минимальное остовное дерево?

valeriikozlov · 13.05.2012, 21:42

Сообщение от Зеленый1

это тоже самое, что минимальное остовное дерево?

Нет не тоже самое. Минимальное остовное дерево - обязательно связанный граф.

Минимальное реберное покрытие графа - когда количество ребер минимально и достигается условие: любая вершина графа является концевой вершиной хотя бы одного из ребер. Но в этом случае, при количестве вершин 4 и более, граф будет несвязанным.
Например есть вершины: 1, 2, 3, 4. Минимальное реберное покрытие будет например таким (указаны ребра между вершинами):
1 2
3 4
т.е. всего два ребра.
А минимальное остовное дерево для этих же вершин состояло бы из 3-х ребер.

@Зеленый1 · 13.05.2012, 21:57 **[ТС]**

valeriikozlov, благодарю за советы! Подскажите пожалуйста, с чего начать решать эту задачу и как.

valeriikozlov · 14.05.2012, 06:30

Сообщение от Зеленый1

Подскажите пожалуйста, с чего начать решать эту задачу и как.

Сначало опишите что подается на вход программы (полное условие задачи).

@Зеленый1 · 14.05.2012, 07:03 **[ТС]**

Пользователь рисует граф, ставит вершины по нажатию на левую кнопку мыши и ребра на правую. После того как нарисовал ребро, пользователь вводит его вес. На форме есть кнопка, по нажатию на которую по нажатию необходимо выделить цветом те ребра, которые входят в реберное покрытие. Все данные заносятся в память после того, как пользователь их ввел, то есть обратиться к определеднному ребру или вершине можно без проблем. Всю интерфесную часть реализовал, пока что в качестве алгоритма я использовал поиск минимального остовного дерева, все работает отлично.

valeriikozlov · 15.05.2012, 06:53

Сообщение от Зеленый1

пока что в качестве алгоритма я использовал поиск минимального остовного дерева, все работает отлично.

Ну и отлично )

@Зеленый1 · 15.05.2012, 11:05 **[ТС]**

valeriikozlov, так а вы же сказали, что это задача нахождения Минимального Реберного покрытия и Минимального остовного дерева - это разные задачи, или я что-то не совсем так понял..?)

valeriikozlov · 15.05.2012, 13:00

Сообщение от Зеленый1

так а вы же сказали, что это задача нахождения Минимального Реберного покрытия и Минимального остовного дерева - это разные задачи, или я что-то не совсем так понял..?)

Да все правильно, это разные задачи. Но ведь Вы сами пишите:

Сообщение от Зеленый1

все работает отлично.

Я так и не увидел что Вам именно нужно (условие задачи не увидел)?
Могу только предположить:
- или минимальное реберное покрытие
- или реберное покрытие с минимальным весом (склоняюсь к этому варианту, т.к. у Вас задается вес ребер)

@Зеленый1 · 15.05.2012, 15:27 **[ТС]**

Сообщение от valeriikozlov

Я так и не увидел что Вам именно нужно (условие задачи не увидел)?

Описал и так по-моему исчерпывающе задачу.. В моей существующей программе надо заменить алгоритм Крускала на новый алгоритм, а про то что покрытие должно быть минимально по стоимости написал ещё в первом сообщении..

valeriikozlov · 15.05.2012, 15:36

Сообщение от Зеленый1

а про то что покрытие должно быть минимально по стоимости написал ещё в первом сообщении..

ну да писал, не спорю:

Сообщение от Зеленый1

необходимо найти такое множество ребер во взвешенном графе, которое бы охватывало все вершины, при этом чтобы оно было минимальной стоимости.

но еще писал название темы:

Сообщение от Зеленый1

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

а это совсем разные вещи.

@Зеленый1 · 15.05.2012, 15:48 **[ТС]**

valeriikozlov, ок, понятно, запутался в терминах. Мне нужно найти

Сообщение от valeriikozlov

реберное покрытие с минимальным весом

valeriikozlov · 15.05.2012, 15:57

Какое может быть максимальное количество вершин и максимальное количество ребер?

@Зеленый1 · 15.05.2012, 16:01 **[ТС]**

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

valeriikozlov · 15.05.2012, 18:07

Нужно найти минимальное остовное дерево (это Вы уже сделали). Потом осталось "немного": исключить некоторые ребра, что реберное покрытие было минимального веса.
Вообще-то "немного" оказывается довольно сложная задача. А простой перебор для 100 ребер это очень долго. Даже поискал алгоритмы через поисковики - ничего конкретного нет

@Зеленый1 2 / 2 / 2 Регистрация: 21.04.2011 Сообщений: 100
		1
	Минимальное реберное покрытие графа 13.05.2012, 14:03. Показов 9152. Ответов 15 Метки нет (Все метки) Господа, подскажите пожалуйста, как реализовать эту задачу. Я так понимаю суть ее заключается ее в том, что,s необходимо найти такое множество ребер во взвешенном графе, которое бы охватывало все вершины, при этом чтобы оно было минимальной стоимости. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	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 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	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 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	14.05.2012, 06:30	6
	Сообщение от Зеленый1 Подскажите пожалуйста, с чего начать решать эту задачу и как. Сначало опишите что подается на вход программы (полное условие задачи). 1

@Зеленый1 2 / 2 / 2 Регистрация: 21.04.2011 Сообщений: 100
	14.05.2012, 07:03 [ТС]	7
	Пользователь рисует граф, ставит вершины по нажатию на левую кнопку мыши и ребра на правую. После того как нарисовал ребро, пользователь вводит его вес. На форме есть кнопка, по нажатию на которую по нажатию необходимо выделить цветом те ребра, которые входят в реберное покрытие. Все данные заносятся в память после того, как пользователь их ввел, то есть обратиться к определеднному ребру или вершине можно без проблем. Всю интерфесную часть реализовал, пока что в качестве алгоритма я использовал поиск минимального остовного дерева, все работает отлично. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	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 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	15.05.2012, 13:00	10
	Сообщение от Зеленый1 так а вы же сказали, что это задача нахождения Минимального Реберного покрытия и Минимального остовного дерева - это разные задачи, или я что-то не совсем так понял..?) Да все правильно, это разные задачи. Но ведь Вы сами пишите: Сообщение от Зеленый1 все работает отлично. Я так и не увидел что Вам именно нужно (условие задачи не увидел)? Могу только предположить: - или минимальное реберное покрытие - или реберное покрытие с минимальным весом (склоняюсь к этому варианту, т.к. у Вас задается вес ребер) 1

	15.05.2012, 18:07

@Зеленый1 2 / 2 / 2 Регистрация: 21.04.2011 Сообщений: 100
	15.05.2012, 15:27 [ТС]	11
	Сообщение от valeriikozlov Я так и не увидел что Вам именно нужно (условие задачи не увидел)? Описал и так по-моему исчерпывающе задачу.. В моей существующей программе надо заменить алгоритм Крускала на новый алгоритм, а про то что покрытие должно быть минимально по стоимости написал ещё в первом сообщении.. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	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 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	15.05.2012, 15:57	14
	Какое может быть максимальное количество вершин и максимальное количество ребер? 0

@Зеленый1 2 / 2 / 2 Регистрация: 21.04.2011 Сообщений: 100
	15.05.2012, 16:01 [ТС]	15
	valeriikozlov, а это очень важно? просто не было такого условия в задаче, давайте возьмем штук 100 и вершин, и ребер. 0