私は自分が書いた小さな Python スクリプトを使用して、ルームメイト間の借金を管理しています。それは機能しますが、不足している機能がいくつかあります。その 1 つは、不必要に複雑な債務構造を単純化することです。たとえば、次の加重有向グラフが何人かの人々を表し、矢印が彼らの間の負債を表す場合 (アリスはボブに $20 とチャーリーに $5 の借りがあり、ボブはチャーリーに $10 の借りがあるなど):
このグラフを次のグラフに簡略化する必要があることは明らかです。
10 ドルがアリスからボブに、そしてボブからチャーリーに、アリスがチャーリーに直接渡すことができたとしても意味がありません。
したがって、一般的な場合の目標は、債務グラフを取得して単純化することです (つまり、ノードは同じでエッジが異なる新しいグラフを作成します)。
- 内側と外側の両方を指すエッジを持つノードはありません (無駄なお金の交換はありません)
- すべてのノードは、元のグラフと同じ「フロー」を持っています (お金がどこに行き着くかという点では同じです)。
「フロー」とは、すべての入力からすべての出力を差し引いた値を意味します (これを表す専門用語はありますか? 私はグラフ理論の専門家ではありません)。上記の例では、各ノードのフロー値は次のようになります。
- ボブ: +10
- アリス: -25
- チャーリー: +15
1 番目と 2 番目のグラフでは、各ノードを通るフローが同じであることがわかるため、これは適切なソリューションです。他にもいくつかの簡単なケースがあります。たとえば、最も低い値のエッジを削除し、他のすべてのエッジからその値を差し引くことで、サイクルを単純化できます。
これ：
これに単純化する必要があります：
この問題を誰も研究していないとは思えません。それに関する情報を見つけるためにどの用語を検索すればよいかわかりません（グラフ理論の専門家ではありません）。私は何時間も無駄に探していたので、私の質問は次のとおりです。加重有向グラフに対して上記で指定された条件に従って単純化 (新しいグラフ) を生成するアルゴリズムは何ですか?