Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Наибольшее по включению паросочетание 
:(
    Опции темы
tiktak
Дата 9.11.2011, 18:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 9.11.2011

Репутация: нет
Всего: нет
Здравствуйте, уважаемые форумчане!
Наибольшее паросочетание - паросочетание, не являющееся подмножеством никакого другого паросочетания (т.е. если добавить еще одно ребро в паросочетание, то оно уже перестанет быть таковым). Понятно, что таких паросочетаний может быть несколько. Требуется найти минимальное по мощности из них.

Понятно, что эту задачу можно решить перебором.
Вопрос: существует ли полиномиальный алгоритм решения этой задачи? Если да, то не могли бы направить в сторону соответствующей литературы/сайта?

//Не путать с максимальным паросочетанием (наибольшим по мощности)!
//Максимальное паросочетание есть наибольшее по включению, но не обязательно наименьшее по мощности из них.
PM MAIL   Вверх
maxdiver
Дата 10.11.2011, 19:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18
Вкратце - нет, не существует.

http://en.wikipedia.org/wiki/Edge_dominating_set:
Цитата
A minimum maximal matching is a minimum edge dominating set

Цитата
Determining whether there is an edge dominating set of a given size for a given graph is an NP-complete problem (and therefore finding a minimum edge dominating set is an NP-hard problem). Yannakakis & Gavril (1980) show that the problem is NP-complete even in the case of a bipartite graph with maximum degree 3, and also in the case of a planar graph with maximum degree 3.
PM MAIL WWW ICQ   Вверх
tiktak
Дата 10.11.2011, 22:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 9.11.2011

Репутация: нет
Всего: нет
Спасибо за ответ.
PM MAIL   Вверх
esperanto
Дата 11.11.2011, 13:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4
Вместо не существует, верно сказать не известно на сегодняшний день. Возможно что существует
--------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0487 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.