Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [network-flow]

For questions about networks that inhibit source and sink nodes and a notion of flow.

440 questions
4
votes
1 answer

Creating network of max flow with 10 nodes, 18 directed edges

I'm given the following network: I'm attempting to build a network with maximum flow using weights 1-18 such that the loss of an individual node (not the source or sink) causes the least disruption to the flow. I know that the max-flow min-cut…
Learner
  • 691
  • 1
  • 4
  • 19
3
votes
1 answer

Convert capacitated network flow problem

Assume a capacitated network flow problem with graph $G = (N,A)$ and capacities $u_{ij}$ (finite), costs for each path of $c_{ij}$ and I/O of $b_{i}$. How can it be shown there is an equivalent transportation problem with a source node for every arc…
GBa
  • 1,046
2
votes
2 answers

Solving project selection with a network flow algorithm

I am currently studying network flow algorithms and one of its application is supposed to be "Project Selection". A (more) complete description is given here, but the problem basically is this: There is a graph $G$ with a number of projects $P$ as…
dtech
  • 823
1
vote
0 answers

traffic flow: red/green light or stop and move?

I live in the burbs and every day twice I drive through a 4-way intersection (E/W - N/S) that is controlled by a red light at which one has to stop from all directions and may pass in the order of arrival. The lines are unbearably long in the…
hyportnex
  • 761
1
vote
1 answer

Some help with understanding Fulkerson algorithm for maximum flow

I'm learning flow networks. I learned Fulkerson algorithm, but there exists one point that is difficult for me. Sorry for image, but I think this is best the way I can explain my problem. This is an example of Fulkerson algorithm execution from the…
Alexander R.
  • 133
1
vote
0 answers

Prove that if the residual graph doesn't contain a path from $u$ to $v$, then $e=(u,v)$ crosses some minimum cut

Prove: given a flow network $N=(G,s,t,c)$ with a maximum flow $f^*$ and a given edge $e=(u,v)$, then there's no path from $u$ to $v$ in $N_{f^*}$. I've seen this thread, but the only answer there is wrong. I tried building a minimum cut myself,…
sadcat_1
  • 249
1
vote
1 answer

Disconnecting set in the maximal flow problem

I was going through a theorem presented in Ford and Fulkerson's famous paper on the maximum flow problem. Even though the theorem is intuitive, there is a step stated in the proof that I could not quite follow. (Ford, L. R., & Fulkerson, D. R.…
whitepanda
  • 196
1
vote
0 answers

Find maximal flow with even flow on every edge.

I don't know if this question has been asked before, but I've searched for previous posts with the same question and didn't find any - though if I missed such one, I'd appreciate the reference. Let $G=(V,E)$ be a flow network with source-$s$,…
Tamir Shalev
  • 321
1
vote
0 answers

Max Flow - Changing the capacity of an edge

Let $G=(V,E)$ be a flow network from $s$ to $t$. I have a maximum flow $f\colon E\to Z$ that was calculated using Ford-Fulkerson. How can I efficiently update $f$ when I need to subtract the capacity of a specific edge $e^* \in E$ by 1…
Lee
  • 811
0
votes
1 answer

One question about a network optimization problem.

The network model for this problem is as follows: and from the model, we see that it formed a circle and hence without any calculations, the upper and lower bounds for cell Delta/Ph.D. must be equal. My question is that is the analysis above…
Brain Zhang
  • 689
0
votes
1 answer

Duality of max-flow and min-cut: when infinite capacity exists

I am wondering if the celebrated duality between max-flow and min-cut actually tolerates infinite valued capacities. Here is a simple example where it seems not: source s, sink t, five other nodes a, b, c, d, e s -> a: capacity 3 s -> b: 3 a -> c:…
Janathan
  • 3
0
votes
1 answer

Ford-Fulkerson algorithm with a little changes

Why if we don't use residual graph in Ford-Fulkerson to finding maximum flow give no any approximation of optimal solution? With such a modification our algorithm do find a augmenting path and increase flow,continue until we have no augmenting…
tstt
  • 341
0
votes
0 answers

Can there be an edge with a positive capacity directly from the source to the destination in a network?

I was hoping to use this in a proof of mine. I do not see any problems with this being the case, however, I have never run into example graphs with this so I was curious.
BKS_headphonesman
  • 31
0
votes
1 answer

Push–Relabel Maximum Flow Algorithm $x_f(s)\leq0$

I'm looking at Push–Relabel Maximum Flow Algorithm (or Goldberg-Tarjan Algorithm) and trying to solve some homework question. As part of the answer I'm trying to prove $x_{f}(s)\leq0$ during the entire algorithm run (where $s$ is the source, and…
Idra
  • 70
0
votes
1 answer

$S \subset V$, $\sum_{v \in S}(f^{out}(v) - f^{in}(v)) = f^{out}(S) - f^{in}(S)$.

Show that for any flow $f$ in a netowrk $N$ with vertice set $V$, arc set $A$, and source and sink sets $X,Y$ respectively that for any $S \subset V$, $\sum_{v \in S}(f^{out}(v) - f^{in}(v)) = f^{out}(S) - f^{in}(S)$. Clearly by the definition of a…
IntegrateThis
  • 3,778
1
2