НГУ

Форумы НГУ
Текущее время: Ср дек 02, 2020 8:59 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Паросочетание с запретами
СообщениеДобавлено: Пт апр 23, 2010 9:44 am 
Не в сети
Начинающий автор

Зарегистрирован: Сб сен 16, 2006 11:23 am
Сообщения: 290
Известен ли алгоритм, эффективно строящий наибольшее паросочетание в двудольном графе с запретами на пары рёбер? То есть обыкновенное паросочетание, но в нём не могут быть одновременно рёбра номер 1 и номер 3, например.

_________________
No regret, no remorse, no mercy.
Я мёртв.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 25, 2010 12:32 am 
Не в сети
Опытный автор

Зарегистрирован: Вт авг 29, 2006 4:53 am
Сообщения: 443
Откуда: Кирилл Василевский
В исходном двудольном графе можно рёбра интерпретировать как вершины нового графа, а запреты на пары рёбер - как рёбра между соответствующими вершинами нового графа. Таким образом, если можно запрещать вообще любую пару рёбер, то видно, что это эквивалентно задаче о построении наибольшего независимого множества на произвольном графе. То есть всё плохо. :(


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 25, 2010 12:35 pm 
Не в сети
Начинающий автор

Зарегистрирован: Сб сен 16, 2006 11:23 am
Сообщения: 290
Да, действительно. Я задумывался об эквивалентности максимальной клики\независимого множества и этой задачи, но почему-то был уверен, что обратной сводимости не будет. Хотел об этом написать, и вдруг понял, что она есть. Если мы рассмотрим произвольный граф и попытаемся найти наибольшее независимое множество, то проинтерпретируем вершины как несмежные рёбра другого графа, а рёбра как подобный "запрет". Тогда у нас получится двудольный граф с некоторой системой запретов, то есть исходная задача, причём сведение полиномиально.

_________________
No regret, no remorse, no mercy.
Я мёртв.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 25, 2010 2:03 pm 
Не в сети
Опытный автор

Зарегистрирован: Вт авг 29, 2006 4:53 am
Сообщения: 443
Откуда: Кирилл Василевский
Можно полюбопытствовать, и что ж Вы теперь делать будете? Кодить экспоненциальный алгоритм или менять формулировку задачи?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 26, 2010 1:12 am 
Не в сети
Начинающий автор

Зарегистрирован: Сб сен 16, 2006 11:23 am
Сообщения: 290
А хз. Что задача решается за экспоненту слишком тривиально. Возможно, получится наложить ограничения, чтобы добится полиномиальности.

Скажем так, меня бы устроило нахождение n-клики в n-дольном графе, но это тоже не выглядит эффективно разрешимым. Есть и ещё ограничения, но весьма специфические, поскольку исходная задача лежит вообще в теории расписаний.

_________________
No regret, no remorse, no mercy.
Я мёртв.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB