2014 dxdy logo

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

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




 
 максимальное количество связей в графе
Сообщение12.06.2015, 13:03 
Возникла следующая задача.

Рассматривается неориентированный граф. Каждой вершине поставлено в соответствие некоторое натуральное число, которое назовем весом вершины.
Необходимо каждому ребру поставить в соответствие неотрицательное целое число (назовем его количеством связей, порожденных ребром) так, чтобы
1) сумма количеств связей, порожденных ребрами выходящими из одной вершины, не превосходила веса этой вершины;
2) общее количество связей в графе было максимальным, т.е. должна быть максимальной сумма количеств связей, порожденных всеми ребрами графа.


Буду признателен за любую информацию по этой задаче.

 
 
 
 Re: максимальное количество связей в графе
Сообщение12.06.2015, 14:05 
Аватара пользователя
Вроде бы линейное программирование, нет? (причём, похоже, ввиду единичных коэффициентов вполне должен работать жадный алгоритм)

-- 12.06.2015, 14:08 --

(Оффтоп)

xelAlex в сообщении #1026329 писал(а):
назовем его количеством связей, порожденных ребром

Больше похоже на "кратность" ребра :-)

 
 
 
 Re: максимальное количество связей в графе
Сообщение12.06.2015, 14:52 
Эту задачу, безусловно, можно сформулировать как задачу линейного программирования. Но поскольку получится достаточно специфическая матрица, обладающая рядом интересных свойств, то возникает вопрос: не имеет ли эта задача более "хорошего" решения?
Меня эта задача интересует в первую очередь с теоретической точки зрения, в частности, интересно какие здесь можно сформулировать общие закономерности, какие-то характерные частные случаи, примеры и т.д. Задача возникла в прикладной области (я не спец в диск мат) и мне нужно понять, что с ней делать. Вариантов, собственно говоря, два:
1) Найти книжку или статью, где эта задача исследована;
2) Попытаться исследовать ее самостоятельно.

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

 
 
 
 Re: максимальное количество связей в графе
Сообщение12.06.2015, 15:07 
Аватара пользователя
Задача сводится к поиску макс. потока в графе - вместо каждой вершины делаем две вершины, соединенные ребром с заданной пропускной способностью, ребра тоже раздваиваем.

-- Пт июн 12, 2015 14:07:58 --

https://en.wikipedia.org/wiki/Maximum_f ... capacities

 
 
 
 Re: максимальное количество связей в графе
Сообщение13.06.2015, 09:51 
Xaositect
Большое спасибо.

 
 
 
 Re: максимальное количество связей в графе
Сообщение13.06.2015, 20:34 
Xaositect
Что брать в качестве источника и стока, если сводить к задаче о максимальном потоке?

 
 
 
 Re: максимальное количество связей в графе
Сообщение14.06.2015, 10:59 
Аватара пользователя
Да, что-то я не посмотрел внимательно.

 
 
 
 Re: максимальное количество связей в графе
Сообщение14.06.2015, 12:26 
Xaositect
Я кажется нашел. По-моему моя задача сводится к задаче о циркуляции потока.

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


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