Прежде всего давайте осмыслим — что мы имеем.
Мы имеем произвольный ориентированный взвешенный мультиграф с петлями, веса дуг в котором строго больше нуля.
Напомним, что мы имеем дело с графом D ≝ ⟨Ω, V, φ(V)⟩,
где
Ω — множество субъектов (вершины),
а V ⊂ (Ω×Ω) — множество обязательств (дуги)
и φ: V → Q, причём ∀v∈V ∃ε∈Q: ε = φ(v), а (Q ⊂ ℚ): (q ∈ Q) ∧ (q>0) — множество обязательств (дуги) весовая функция на множестве дуг.
Введём ещё два обозначения:
входящую степень вершины μ обозначим как in(μ),
а внешнюю степень вершины μ как ех(μ).
Тут можно вспомнить, что тогда
μ — чистый водоём, если (in(μ) ≠ 0)∧(ех(μ) = 0),
μ — чистый источник — (in(μ) = 0)∧(ех(μ) ≠ 0),
а μ — изолированная вершина — (in(μ) = 0)∧(ех(μ) = 0).
Заметим, между прочим, что ответ на проверочный вопрос, который был задан в статье, с которой всё началось, отрицательный. Как видно из определения, чистые источники, чистые водоёмы и изолированные вершины образуют множества, которые не имеют общих элементов.
Если v' = (μ, ψ), где μ∈Ω и ψ∈Ω, то условимся, что μ это источник, а ψ — водоём, а вес v' будет φ(v').
Юридически это значит, что ψ имеет кредиторское требование к μ уплатить сумму φ(v').
Поскольку φ: V → Q, причём ∀v∈V ∃ε∈Q: ε = φ(v), а (Q ⊂ ℚ): (q ∈ Q) ∧ (q>0), то есть ∀ε: (ε > 0), а это значит, что на всех элементах множества Q, мы можем найти НОД (Q) — наибольший общий делитель всех тех сумм (со школы это должен, обязан помнить любой, кто получил хотя бы среднее образование), которые должны один другому субъекты из множества V. Разумеется, все числа в Q могут оказаться взаимно простыми, но тогда НОД (Q) = 1.
Причём в школе и рассказывают как алгоритм Евклида нахождения наибольшего общего делителя, так и бинарный алгоритм. Оба они легко расширяются с двух на любое конечное число чисел. А кто не помнит... а вот не надо было учиться на уроках математики «на отцепись», ибо ваша учёба в школе была нужна не вашим учителям и не вашим родителя, а вам, что, между прочим, вам также постоянно повторяли, но в любом случае это проще посмотреть в сети, чем мне заниматься тут рассказом об этом, явно уходя в сторону.
В принципе, можно и не искать НОД (Q), а просто в дальнейшем полагать соответствующую величину равной наименьшему весу в множестве V или вообще 1, так как это — минимальный возможный вес любого ребра графа, который задан подобным образом, минимум множества Q. Я не буду тут показывать, что Q является частично упорядоченным множеством вам придётся в это просто поверить... или, что лучше — доказать самим.
Давайте теперь введём некоторые операции на множестве дуг.
⓵ Удаление петель
Первым делом удалим из исходного графа все дуги вида w = (ω, ω). Это — так называемые петли. Если они есть, конечно.
Юридическое значение петли — такое обязательство, кредитор по которому совпадает с должником. Удаление таких дуг есть просто прекращение обязательства совпадением кредитора и должника в одном лице.
Итогом этой операции является уже ориентированный взвешенный мультиграф без петель, веса дуг в котором строго больше нуля.
Если граф представлен матрицей смежностей, то операция сводится просто к приравниванию нулю всех диагональных элементов.
⓶ Сложение дуг
Произведём ещё одну операцию. Во всех случаях, когда есть дуги
t' = (μ,ψ) с весом φ(t') и t" = (μ,ψ) c с весом φ(t"),
обе их заменим на дугу
t = (μ,ψ) с весом φ(t) = φ(t') + φ(t").
Юридически это означает, что мы заменили два обязательства, одно — μ уплатить в пользу ψ сумму φ(t') и другое — μ уплатить в пользу ψ сумму φ(t") на одно обязательство μ уплатить в пользу ψ сумму φ(t) = φ(t') + φ(t"). Это — также новация обязательств.
⓷ Вычитание дуг
Произведём ещё одну операцию, подобную той, которую мы только что описали.
Во всех случаях, когда есть дуги t' = (μ,ψ) с весом φ(t') и t" = (ψ,μ) с весом φ(t"), обе их заменим на дугу с весом φ(t) = |φ(t') - φ(t")|
если φ(t') > φ(t"), то t = (μ,ψ),
если φ(t') < φ(t"), то t = (ψ,μ),
если φ(t') = φ(t"), то обе дуги удаляем.
Юридически это означает, что мы прекращаем по крайней мере одно из двух обязательств, одно — μ уплатить в пользу ψ сумму φ(t') и другое — ψ уплатить в пользу μ сумму φ(t") зачётом встречных однородных требований на меньшую из двух сумм, а если это обязательства строго равные, то прекращаем оба эти обязательства всё тем же зачётом встречных однородных требований.
После того, как мы проведём все возможные операции, описанные в 1, 2 и 3, мы получим уже ориентированный взвешенный граф. В нём уже нет ни петель, ни кратных дуг, то есть дуг, инцидентных одним и тем же вершинам.
Заметим, что и операция 1, и операция 2, и операция 3 по крайней мере не увеличивают количество дуг и, следовательно, не увеличивают ни у одной вершины её степеней.
Меня могут спросить, а почему сложение и вычитание дуг не объединить в одну операцию, просто считая сложение разнонаправленных дуг сложением большей дуги с меньшей, у которой вес меняет знак? Алгоритмически, программа, если написана, на матрице смежностей так и сделает, но вот юридически всё равно придётся различить эти две операции, ведь операция сложения есть новация обязательств, а операция вычитания — прекращение встречных однородных кредиторских требований зачётом.
Как верно заметил Александр Привалов, надо рассмотреть такое подмножество дуг V', каждый элемент которого инцидентен вершине, которая не является чистым водоёмом.
Юридически это означает, что это множество таких обязательств уплатить некоторую сумму, каждое из которых имеет своим кредитором такого субъекта, который также имеет долговые обязанности уплатить некоторую сумму к какому-то иному субъекту.
Заметим, что если ∀V': (V' ⊂ V) ⇒ (V'= Ø), то следует считать, между прочим, что задача решена.
Юридически такая ситуация значит, что ни один должник уже не является никому кредитором, а ни один кредитор уже не является никому должником: у нас одни чистые источники (должники), одни чистые водоёмы (кредиторы) и какая-то часть — те, кто никому не должен и им никото не должен. А это — решение задачи и никакие оптимизации тут уже не нужны. Нужно просто исполнять обязательства по построенной конфигурации.
Но если ∃V' ≠ Ø, то в нём есть хотя бы одна дуга. Возьмём же любую
v' ∈ V'.
Кстати, предлагаю доказать следующую Лемму для полученного нами ориентированного взвешенного графа (уже без петель и кратных дуг), то есть после проведения всех возможных операций 1, 2 и 3. Это не так сложно, если вы вполне вчитались в то, что написано выше
Лемма о неодинокой дуге
Пусть D' ≝ ⟨Ω, V, φ(V)⟩ — ориентированный взвешенный граф,
пусть V' ⊂ V, пусть ∀v∈V': ((v= (μ,ψ)) ⇒ (ех(ψ) ≠ 0))
Тогда верно, что V' всегда содержит не менее двух дуг.
Если v' = (μ, ψ), где μ∈Ω и ψ∈Ω, то условимся, что μ это источник, а ψ — водоём, а вес v' будет φ(v').
Юридически это значит, что ψ имеет кредиторское требование к μ уплатить сумму φ(v').
Постольку поскольку v' ∈ V', то ех(ψ) >0, а это значит, что ∃u ∈ V': u = (ψ, η) и φ(u) > 0.
Юридически это значит, что η имеет кредиторские требования к ψ уплатить сумму φ(u), в то время как ψ имеет кредиторские требования к μ на сумму φ(v').
⓸ Хождение разменной монеты
Поскольку φ: V → Q, причём ∀v∈V ∃ε∈Q: ε = φ(v), а (Q ⊂ ℚ): (q ∈ Q) ∧ (q>0), то есть ∀ε: (ε > 0), а это значит, что на всех элементах множества Q, мы можем найти НОД (Q) — наибольший общий делитель всех тех сумм (со школы это должен, обязан помнить любой, кто получил хотя бы среднее образование), которые должны один другому субъекты из множества V. Разумеется, все числа в Q могут оказаться взаимно простыми, но тогда НОД (Q) = 1.
Пусть θ = НОД (Q), тогда мы можем произвести следующую операцию:
дополнительно к v' = (μ, ψ) c весом φ(v') образовать v" = (μ, ψ) с весом φ(v')-θ, а вес v' = (μ, ψ), изменить, сделав его φ(v') = θ.
Заметим, что это можно сделать всегда, так как θ = НОД (Q).
Ранее мы оговорили, впрочем, что НОД (Q) можно и не искать, а просто установить θ = 1 или θ = min (Q). Тут вполне можно поступить и иным образом: установить θ = min (φ(μ, ψ), φ(ψ, η)), а то, что (ψ, η) всегда существует, видно из... доказанной вами Леммы о неодинокой дуге.
Юридически это означает, что некоторое обязательство уплатить сумму φ(v') мы представили в виде двух обязательств между теми же субъектами с сохранением их места в этих обязательствах: уплатить сумму φ(v')-θ и уплатить сумму θ. В сумме всё равно получается исходная сумма φ(v'). Это опять — новация первоначального обязательства v'.
Тут стоит опять заметить, что если при этом φ(v')-θ = 0, то такую дугу мы просто изымаем, потому что юридически это означает, что ψ имеет кредиторские требования к μ в сумме 0.
В принципе, можно поступить иначе:
сначала проверить не верно ли, что вес φ(v') = θ, а если φ(v') = θ,
то операцию с выделением дуги с таким весом просто пропустить. Новация такого обязательства не нужна,
Назовём дугу v', вес которой φ(v') = θ, разменной монетой.
Согласно Лемме о неодинокой дуге, которую вы, конечно же, успели доказать, у субъекта ψ есть непременно кредитор λ, причём на сумму φ((ψ,λ)) ⩾ θ. Пусть же ψ «расплатится» с λ разменной монетой.
Как это будет выглядеть в виде операции на графе?
Это значит, что вместо дуги v' = (μ,ψ), вес которой φ(v') = θ, мы строим две дуги: v'₊ = (μ,λ) с весом θ и v'₋ = (λ,ψ) с весом θ.
Юридически это значит, что субъект ψ уступил своё право кредиторского требование, которое он имел к μ в сумме θ, а субъект λ взял на себя обязательство уплатить μ сумму θ.
Обратим внимание, что у нас образовались дуги: (ψ,λ) с весом φ((ψ,λ)) ⩾ θ и только что построенная нами дуга v'₋ = (λ,ψ) с весом θ.
Ясно, что при этом мы имеем полное право применить операцию 3 и вместо дуг (ψ,λ) с весом φ((ψ,λ)) ⩾ θ и дуги v'₋ = (λ,ψ) с весом θ, мы получаем дугу (ψ,λ) с весом φ((ψ,λ)) - θ ⩾ 0. Если этот вес равен нулю, то по указанной ранее причине, мы такую дугу выбрасываем.
Юридически это означает, что сразу после уступки субъектом ψ права кредиторского требования в пользу субъекта λ и получения к λ права кредиторского требования уплатить в пользу субъекта ψ сумму θ (как раз за эту уступку!), мы прекратили обязательства зачётом встречных кредиторских требования ψ к λ в кредиторские требования λ к ψ на сумму θ.
Затем повторяем все операции, там, где они применимы, на всём графе: 1, 2, 3 и 4. Пока и поскольку ∀V': (V' ⊂ V) ⇒ (V'≠ Ø).
А поскольку при каждом применении операции 4 сумма всех весов обязательно уменьшается на θ ⩾ 1 (а проверьте! а то вдруг я вру!), то в результате мы получаем на каждом применении всего алгоритма ориентированный взвешенный граф со строго уменьшающейся суммой весов всех рёбер.
Осталось доказать, что
в конце концов наш граф сведётся именно к тому, задача найти который и стоит перед нами.
Путь это не так,
мы применили весь алгоритм, не можем его больше применить и есть такой субъект ψ, который не является ни изолированным, ни чистым источником, ни чистым водоёмом.
Это в силу Леммы о неодинокой дуге, которую вы, без сомнения, блестяще доказали, — иначе откуда вы знаете, что я прав в этой лемме, ведь её сформулировал я, а доказывать не стал? — означает, что
∃v'∃v": (v' = (μ,ψ), φ(v'))∧(v" = (ψ,λ), φ(v"))∧(φ(v') ⩾ 1)∧(φ(v") ⩾ 1);
то есть в силу такого предположения
(in(ψ) >0)∧(ex(ψ) >0).
Но это значит, что мы имеем право применить операцию 4, снова уменьшив φ(v") на θ ⩾ 1. Это означает, что наше первоначальное предположение неверно:
или неверно, что алгоритм неприменим,
или неверно, что ∃ψ: (ex(ψ)>0)∧(in(ψ)>0).
Это значит, что мы построили требуемый алгоритм, ну а в силу обычных уже просто бухгалтерских балансов, которые сводятся к тому, что каждой вершине графа присваивают разность суммы весов входящих и суммы весов исходящих вершин, мы получим замечательный граф: сумма его весов будет равна минимальной сумме потребных денег, которая позволяет произвести все оставшиеся расчёты с полным соблюдением балансов.
И вот тут надо бы остановиться, потому что в заключение стоит попытаться понять что надо сделать для того, чтобы такой алгоритм вообще был реализуем и каких нормативных правил в данном случае не хватает.
Это я предлагаю обдумать уже юристам. К математике это отношение точно не имеет, хотя интересоваться этим и математикам никак не противопоказано, равно как и интересоваться математикой юристам.
Да, и в заключение к этой части.
Мне пеняют, что я нагружаю юристов формализмами математики, которые-де они читать не способны. На это я скажу вот что.
Во-первых, люди-юристы не глупее людей-математиков и всё, на что способны люди, занимающиеся математикой, вполне даже доступно и людям, занимающимся юриспруденцией. Что касается лентяев и откровенных глупцов, то они есть не только среди юристов, но и среди математиков. Это — раз.
Во-вторых, а кто вообще сказал, что юрист существует в безвоздушном пространстве и кроме юриспруденции вообще нет ничего? А я вот как раз считаю иначе. Есть, например, математика. А кроме, например, студентов-юристов есть в том же университете и студенты-математики. Кто и когда запрещает им общаться и взаимодействовать друг с другом, решая общую задачу? Лично я никогда такого идиотского запрета вовсе не вводил. Мало того, они вполне даже взаимодействуют друг с другом на всевозможных в том числе не вполне отвечающих требованиям здорового образа жизни посиделках, почему бы им не заняться не трёпом, а решением вполне даже интересных для тех и других задач? Это — два.
В-третьих, я рассматриваю современный труд как труд исключительно общественный, в том числе и в сфере умственного труда, а не как натуральное хозяйство на грядке единоличника-математика (есть такие, есть... между прочим, выглядят весьма... странно!) или юриста (кстати, тоже престранные личности). Отчего бы не приобрести ещё и навыки нормального общественного труда, взаимодействия между разными специалистами, между прочим, стирая при этом проклятье разделения труда и становясь уже специалистом и в иной области?
Между прочим, коммунистическое общество будет состоять вовсе не из пахарей на единоличных нивах, а из ярких индивидуальностей, но отнюдь не из индивидуалистов. Это — три.