Здравствуйте, nvoynov, Вы писали:

N>Может путаю терминологию (очень давно "числил методы") двудольный наверное не получается — у агента есть один товар, а нужен ему другой, т.е. ребра могут быть двунаправленными.

Так как раз двудольный и ориентированный.
Двудольность заключается в том, что все вершины принадлежат к двум подмножествам — агенты и товары, и рёбра есть только между агентами и товарами, но не внутри агентов или внутри товаров.
А ориентированность — в том, что одни рёбра означают предложение, другие спрос; и естественно задать тип отношения направлением ребра.

К>>Задача номер один: разбить орграф на циклы.
К>>Задача номер два — совсем тривиальная — ввести брокера и представить обход цикла как работу через брокера.

N>и по идее это большая система предложений, соответственно ребра могут быть а могут не быть как в прямом так и обратном направлении ...

N>в любом случае это граф, наверное товаров (что на что можно поменять) и в нем нужно искать циклы, а потом выбирать наименьшие ...

Я сформулировал наиболее общий случай. Скажем, один агент выставляет множество предложений и множество же заявок.
Это может означать, что
— нужно удовлетворить все заявки (т.е. мы разбиваем граф на циклы, разбивая множество рёбер-заявок)
— нужно удовлетворить ровно одну заявку (т.е. мы разбиваем множество вершин-агентов)
— нужно удовлетворить хотя бы одну заявку агента, чтобы он "имел навар с яиц" (т.е. мы не разбиваем, а покрываем множество вершин-агентов)

А возможно, что условия задачи провозглашают, что у агента ровно одна заявка и ровно одно предложение.
В таком случае заявка-агент-предложение является ребром.
И тогда у нас получается просто орграф из вершин-товаров и рёбер-агентов.
И мы разбиваем его на циклы, разбивая (или покрывая) множество рёбер.

Покрытие рёбер значит, что несколько циклов могут проходить через одно ребро — т.е. агент неоднократно наваривается на бартере. (Как в первом случае — двудольного графа, так и во втором).

Тут для уточнения нужно или вводить кратность рёбер, или вес — и требовать, чтобы ток денежного эквивалента по контуру был одинаков во всех рёбрах, а сумма токов через ребро равнялась весу этого ребра.
Здравствуйте, ТОЭ и законы Кирхгофа!

Кстати, а может, действительно можно припахать электротехнику?

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

Ну а раз такая пьянка, то мне начинает казаться, что решения всегда есть, и задача уточняется до поиска кратчайших циклов, а не до поиска любых циклов.

Резисторы?
Точно! Каждое ребро представляет резистор и источник тока.