# Questions tagged [network-flow]

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

302 questions
Filter by
Sorted by
Tagged with
2k views

### Help with linear algebra network flow (picture)

I've been stuck on this problem for hours. I keep starting and stopping because I'm not exactly sure what I'm doing. The examples the teacher worked in class were much more straight forward. If ...
202 views

My question is below: Consider a network of n queues with a Poisson arrival process of parameter t from outside the network, and independent exponentially distributed service times of ...
395 views

### Flow network: Source with in degree and sink with out degree

I have a flow network G with a single source s and a single sink t, but out-degree(t) is not 0 and in-degree(s) is not 0. Does removing all the edges leaving t and/or entering s change the capacity ...
234 views

178 views

### Flow Graphs: Why do you need the symmetry property of a graph?

$$\begin{gather} f(u,v) \le c(u,v) \tag{Capacity constraint} \\ f(u,v) = -f(v,u) \tag{Symmetry} \\ \sum_{\large{v \in V, v \ne s,t}} f(u,v) = 0 \tag{Conservation of flow} \end{gather}$$ When you are ...
1k views

### How to show that union and intersection of min cuts in flow chart is also a min cut

The proof of this is everywhere skipped and said to be collorary of Ford-Fulkerson theorem. It's usually something like: Let $A$ and $B$ be low cuts of a flow chart. Then $A \cup B$ and $A \cap B$ ...
60 views

### Graph theory: Linking graph characteristics and minimal cut

I'm currently working on a research involving Graph theory. More specifically, I would like to make an analytical or theoretic connection between different characteristics of the graph (e.g. size, ...
2k views

### 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, ...
65 views

### what is a flow in the context of the Ford-Fulkerson algorithm?

I am learning about the Ford Fulkerson algorithm, but having a hard time getting an intuitive feel for what a "flow" is. Is the "flow" the amount that travels between two adjacent nodes on a graph? Or ...
2k views

### Determine whether a graph has a unique max flow

Is there a characterization result/some sufficient conditions that ensure that a graph has a unique max flow? Note that it does not say anything about the min-cuts: a path with all edges having ...
121 views

### Decomposing flows on a graph as a sum of cycle flows and source flows

I am reading a paper where they say the following is "easy" but I can't seem to see why. Let $G$ be a finite undirected graph on an edge set $V$ and let $E$ be its set of oriented edges (i.e. each ...
173 views

### Prove / Disprove: If the Residual Graph $G_f$ Contains no Path from $u$ to $v$ then $e$ Crosses Some Minimum Cut

Let $G = (V,E)$ be a flow network. Let $e = (u,v)$ be an edge in $E$ and let $f$ be a maximum flow in $G$. Prove or Disprove: If the residual graph $G_f$ contains no directed path from $u$ to $v$ ...
126 views

### Network's flow - a couple of issues

There are three requirements for the path to be a flow - capacity constraints, skew symmetry, and the flow conservation ( http://en.wikipedia.org/wiki/Flow_network ). Ok, but what if the network ...
94 views

### What would a Tutte Polynomial =0 represent?

So I'm working on proving (via contradiction) that the flow number $\phi(G)$ of a bridgeless graph $G$ is always defined. I'm using the flow polynomial, and I got to a point where I have $0=T(0,1-u)$. ...
458 views

### Which cut does the “minimum cut” refer to?

My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
254 views

### Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?

I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book. Which does "cut" most commonly refer to? p.s. I am aware that "cut" itself can be defined to ...
7k views

### Do “cut set” and “edge cut” mean the same thing?

The definitions I have are: A cut set of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in $Y$. ...
465 views

### Max - Flow and Min - Cut, Minimize the number of visible boxes

Suppose that you are given a set of boxes, with each box as a rectangular parallelepiped with side lengths as (i1, i2, i3). And each side length is between half a meter and one meter. How should a ...
2k views

### Using maximum flow algorithm to check existence of a matrix

Using the maximum flow algorithm, I have to determine if there exists a $3\times 3$ matrix $P$ (such that all elements are $\geq 0$). I'm given: The maximum values of the row sums The column sums The ...
387 views

### Two-commodity minimum cost flow with antisymmetric costs

I'm looking at a minimum-cost flow problem in directed acyclic graphs. We are given a DAG plus a cost function that maps an edge to a real-valued cost, and a capacity function that maps an edge to a ...
91 views

### planarity of graph as a consequence of its flow

Is it possible to distinguish planar and non-planar graphs (networks as a matter of fact) by flows? That is, is there a flow criterion for a graph being planar or not?
2k views

2k views

### Network flow: Why is min-cut determined by unsaturated edges?

Suppose we have an oriented graph and max-flow has been determined. I found that to determine min-cut or minimum s-t cut can then be found by labeling graph nodes such that nodes belonging to source ...
5k views

### Network Flow Problem - How to solve with a matrix?

Find the general flow pattern of the network. Assuming that the flows are all nonnegative, what is the smallest possible value for $x_4$? Points of Intersection: Flow In = Flow Out A: $x_1+x_4 = x_2$...
308 views

### Max flow in a flow network such that $e \in E$ has the maximum flow it can have.

Given a flow network $G=(V,E)$, source $s$ , sink $t$ and capacity function $c:E \to \mathbb{R}^+ \cup \{0\}$ ; as well an edge $e=(u,v) \in E$. I need to find an efficient algorithm which finds among ...
5k views

### What's an intuitive explanation of the max-flow min-cut theorem?

I'm about to read the proof of the max-flow min-cut theorem that helps solve the maximum network flow problem. Could someone please suggest an intuitive way to understand the theorem?
1k views

### maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...
2k views

### Min-cut Max-flow $\Rightarrow$ Dilworth's theorem

Dilworth's theorem states that given a finite partially ordered set, the length of the maximal anti-chain, is equal to the minimal number of chains needed to partition the set. I need to prove that ...
2k views

### Does the greedy method guarantee max flow in a directed tree?

Consider a directed tree $G$ with a root node $s$. Let $s$ be the source node of $G$ and its leaves the sink nodes (call these leaves $t$). (And of course edges have their respective capacities like ...
686 views

### Probability of global epidemic

Consider $\mathbb{Z}^2$ as a graph, where each node has four neighbours. 4 signals are emitted from $(0,0)$ in each of four directions (1 per direction) . A node that receives one signal (or more) at ...
2k views

### Min cut Max flow - Finding the cut with least vertices

Suppose a network $N = (G,c,s,t)$ where $c$ is real. How do you find all min-cuts? (or how do you find the cut with the least number of vertices) I've tried messing with the capacity, but since it ...
202 views

### Maximum Flow in Dynamic graphs

I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in $G$ now new node added/deleted with related ...
926 views

93 views

### Does the sparsest cut always have a solution?

How do I prove that the sparsest cut always has an optimal solution which is the cut for some vertex-subset? It looks like it should be a kind of fundamental theorem for sparsest cut. But I didn't ...
518 views

### The flow/cut gap theorem for multicommodity flow

Let's start out by reviewing very popular max-flow min-cut theorem Max-flow min-cut theorem: The maximum value of an $s-t$ flow is equal to the minimum capacity of an $s-t$ cut. For details: Max-...
248 views

1k views

### Construct dual network for conversion of min-cut problem to shortest path problem

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...
978 views

### network flow as a linear combination

How would I write the flow of the following graph as a linear combination of flows along s,t-paths and t,s-paths and cycles? The values of the edges in the graph represent the flow along that edge. I'...
2k views

### What is the restriction matrix used for in the stepping stone method?

Let's say that we want to solve a classic transportation problem without capacities using the stepping stone method. (Problem definition: A bipartite graph with supply nodes a1...m, demand nodes b1......
4k views

### 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 ...