максимальное количество связей в графе

[xelAlex]

Возникла следующая задача.

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

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

[Geen]

Вроде бы линейное программирование, нет? (причём, похоже, ввиду единичных коэффициентов вполне должен работать жадный алгоритм)

-- 12.06.2015, 14:08 --

(Оффтоп)

xelAlex в сообщении #1026329 писал(а):

назовем его количеством связей, порожденных ребром

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

[xelAlex]

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

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

[Xaositect]

Задача сводится к поиску макс. потока в графе - вместо каждой вершины делаем две вершины, соединенные ребром с заданной пропускной способностью, ребра тоже раздваиваем.

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

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

[xelAlex]

Xaositect
Большое спасибо.

[xelAlex]

Xaositect
Что брать в качестве источника и стока, если сводить к задаче о максимальном потоке?

[Xaositect]

Да, что-то я не посмотрел внимательно.

[xelAlex]

Xaositect
Я кажется нашел. По-моему моя задача сводится к задаче о циркуляции потока.