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

В 90-е бандитские. Когда был кризис платежей реальными деньгами. Были фирмы которые занимались взаимозачетами. Сейчас это не актуально.

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

это характеристика графа
это вредно для экономики капитализма - уменьшает денежные потоки

(0)
1. Теоретически - характеристика графа. В реальности у взаиморасчетов еще куча параметров (дата платежа как минимум), из-за которых эта сумма может не быть характеристикой графа.
2. Сделать это несложно. В модели. В реальности модель не особо нужна.
3. Сейчас почти бесполезно. Контрагенты бывают разные и, если в цепочке есть, например, банкрот, то хрен вам, а не исполнение цепочки.
4. Сбербанк такую услугу предложить не может. Он не знает картины взаиморасчетов, да и разбазаривать данные о состоянии счетов права не имеет.

Есть случай когда примерно так всё и работает: биржевая торговля и клиринг. Но там куча упрощений (как минимум - расчеты через центрального контрагента, расчеты "день-в-день" и т.п.).

(3) Для экономики это полезно, но только когда все участники договорились о правилах, но эти правила не подойдут всем.

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

(3) Как называется и, если не в лом, ссылку.

хотя нет, не характеристика, легко строится контр-пример

ИМХО бюджету Украины это не поможет.

(5) Бартер в России запрещен, а вот так взаимозачетами вполне можно, приббыль и НДС с выручки же насчитается ;-)

О реализации товарной биржи с такой идеей выступал Герман Стерлигов в 2008 году, как видим воз и ныне там. Как говорится все хорошо при такой схеме, до того момента пока не пошли возвраты, у начального движка все равно должны быть деньги ;-)

(0) А если если "а" должен "б" некоторую сумму, а "б" должен "а" другую некоторую сумму, то как это отражать?
То есть они оба друг другу должны, например один за сырье, а второй за товар.

(11) вот тут как раз делается типичный взаимозачет

(0) Многосторонние взаимозачеты- ложное понятие и неадекватное название.

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

Даже когда оформляют единый многосторонний текст договора.
Сделок все равно несколько, а не одна. И по ним возникают разные виды обязательств.

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

(0) Попытка решения только математическими методами- заведомо неполное и не всегда пригодное решение.

Короче, дурь и никогда не взлетит в массовом масштабе.

(0) Смотри УПП. Там есть алгоритм, при расчете себестоимости товаров и материалов. Из расчета исключаются материалы которые за отчетный период вернулись на исходный склад.

Очевидно, что сумма всех "должны мне"-"должен я"=0

1. Выдаем всем одинаковую сумму "кредита" в размере максимального долга.
2. Все гасят свои долги своим соседям
3. Отнимаем от всех сумму кредита из п.1, у кого то получится отрицательно, у кого то положительно, но в сумме по прежнему 0.
4. Теперь распределяем долги тех у кого "отрицательный баланс" по тем у кого "положительный" любым алгоритмом распределения
5. Вуаля - взаимных долгов нет ни по какому кругу=профит

(0)
1. зависит:
http://i58.fastpic.ru/big/2014/0314/09/97b12d25eeb92d2dd4041de44cf33009.png
2. похоже, что NP-полная;
3. вопрос к контрагентам;
4. чем больше цикл тем сложнее организовать;

(0) денег никто не получит, но налоги придется заплатить...

(17) Если правильно понял Вашу мысль, то Вы предлагаете:
- завести "клиринговый центр";
- перевести все долги на него;
- в "центре" провести чистый взаимозачет.
Но это не совсем то, о чем речь в (0), в чем можно убедиться, проделав вышеуказанное для примера из (18).

навеяло анекдот про двух ковбоев, сто баксов и кучу лошадиного авна ;)))

(10) >>О реализации товарной биржи с такой идеей выступал Герман Стерлигов в 2008 году, как видим воз и ныне там.

Воз не там. Уже давным давно банкрот. Т.е. "не взлетело".

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

Путин лавку прикрыл.

>>- насколько это "полезно" контрагентам?

Если долг безнадежный, и на него есть какой-то покупатель, то очевидно, что с паршивой овцы хоть шерсти клок.