2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задачка с графом
Сообщение01.02.2007, 13:56 
Здравствуйте. Есть двудольный граф. G(V1,V2).
Все связи между вершинами V1 V2 взвешены. Задача. Выбрать
Связи такие, чтобы сумма весов была максимальна.
При этом внутри каждого множества вершин связей нет.
Одна вершина множества V1 V2 может быть связана со многими
вершинами другого множества.
Подскажите где искать метод решения. Я нашел для другого типа графов,
поиск кратчайшего пути (аналогично длиннейшего). Но мне надо именно для двудольного и при этом как такового "пути" нет. В результате мы должны получить решение задачи о свадьбах (Холл), но с учетом "максимальных предпочтений". Заранее спасибо.

 
 
 
 
Сообщение02.02.2007, 08:59 
Аватара пользователя
Уточните условие. Почему нельзя выбрать все ребра (ну или все ребра с положительным весом) - они и дадут максимальную сумму весов.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group