我有一个带有边缘流量的有向图,我想通过消除所有循环流来简化它。这可以通过在任何给定周期内找到每个边缘上的最小流量并将周期内每个边缘的流量减少该最小值来完成,从而删除流量为零的边缘。当所有循环流都被移除后,图将是无环的。
例如,如果我有一个具有顶点A、B和C的图,其中从A→B流出1,从B→C流出2,从C→A流出3,则我可以用没有从A→B流出的流,从B→C流出1和从C→A流出2来重写它。图中的边数已经从3减少到2,并且生成的图是无环的。
哪种算法(如果有)可以解决这个问题?
例如,如果我有一个具有顶点A、B和C的图,其中从A→B流出1,从B→C流出2,从C→A流出3,则我可以用没有从A→B流出的流,从B→C流出1和从C→A流出2来重写它。图中的边数已经从3减少到2,并且生成的图是无环的。
哪种算法(如果有)可以解决这个问题?