Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.10.2010, 17:12
Shl Shl вне форума
Новичок

Отправить личное сообщение для Shl Посмотреть профиль Найти все сообщения от Shl
 
Регистрация: 08.10.2010
Сообщений: 2

Паросочетание максимального веса в двудольном графе
Добрый день.
К какой задаче можно свести задачу поиска паросочетания максимального веса в двудольном графе (взвешены ребра) или существуют алгоритмы решения конкретно этой задачи?
  #2  
Старый 08.10.2010, 17:55
гость

 
Сообщений: n/a

Сообщение от Shl Посмотреть сообщение
Добрый день.
К какой задаче можно свести задачу поиска паросочетания максимального веса в двудольном графе (взвешены ребра) или существуют алгоритмы решения конкретно этой задачи?
существуют. min cost max flow, или венгерский, например
  #3  
Старый 23.10.2010, 14:27
Shl Shl вне форума
Новичок

Отправить личное сообщение для Shl Посмотреть профиль Найти все сообщения от Shl
 
Регистрация: 08.10.2010
Сообщений: 2

А как найти все возможные решения задачи о назначениях?
Венгерским методом легко найти одно решение, но, очевидно, их может быть много.
Говоря конкретнее, как найти все наибольшие паросочетания?

В результате работы венгерского алгоритма есть некая подматрица исходной матрицы, состоящая лишь из 0, соответствующих возможным назначениям. Логика подсказывает, что поочередно удаляя из графа, соответствующего этой матрице, дуги, а затем строя по ней наибольшее паросочетание (используя алгоритм Куна, например), мы получим все наибольшие паросочетания, часть из которых будут длины N (N- число вершин в каждой из долей), что будет соответствовать искомым паросочетаниям.Но вот матриц таких будет слишком много ((N^2)!), а для каждой из них ещё и алгоритм Куна надо запускать.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Наибольшее паросочетание Fredo Реализация, исходники, языки 1 02.05.2010 20:56
Задана на двудольном графе Dronbas Графы 0 14.11.2008 14:52
Паросочетание в недвудольном графе гость Графы 8 05.09.2008 20:43
Покрытие в двудольном графе NiK Графы 2 24.08.2008 01:09
Паросочетание максимального веса гость Графы 5 30.07.2007 11:40