# Questions tagged [network-flow]

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

296 questions
Filter by
Sorted by
Tagged with
16 views

### Maximum Flow of a network $G$

We are supposed to find the maximum flow through this network $G$. We have that $val(f) \leq c(C)$ for every cut in the network, where $c(C)$ is the capacity of the cut $C$. So I understand I am ...
22 views

### Find matrices given sums of each row and column with bounded integer entries: maximize zero-valued entries

I want to find solutions for the following problem. It seems to be a classic problem in integer programmimg and logistics, but I don't know its name. Find a matrix of m rows and n columns, with non-...
18 views

### Proof for Gossip problem

Suppose there are n people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information ...
12 views

### Size of the set T in a T-join problem

I am an undergraduate that is taking a course in combinatorial optimization and I have come onto studying T-join problem. Could someone please explain why the size of the set $|T|$ has to be even in a ...
21 views

39 views

### How can I calculate the minimum number of moves needed in a game involving stacks?

I'm currently programming a game, and I have been stuck on the following problem for a while. The above figure is a set of stacks. The end-goal is to sort all items by color in the least possible ...
80 views

### Going from abstract intuition to formal proof

This question is somewhat open-ended and there is unlikely to be a single fixed answer to this, but I would love to hear some thoughts of the people with a deeper understanding of this field than I ...
17 views

### show maximum number of arc disjoint directed $s-t$ paths is equal to max flow

Given: $D = (V,A)$ a directed graph and $s,t \in V$ Problem: Show that the maximum number of pairwise arc-disjoint directed $s-t$ paths is equal to the maximum value of the flow $f$ where $f$ is ...
19 views

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

### Help formulating an inventory problem

I need some advice on how to describe this as an optimization problem. There are a number of items stored in warehouses, that need to be reorganized in order to minimize new purchases. To illustrate ...
36 views

### Prove that if (S, V − S) is an arbitrary mincut of N, then c_f (x, y) = 0 for all x ∈ S and y ∈ V − S

Some backgroud- Let N = (G = (V, E), c, s, t) be a network, f be a maxflow in N, Nf = (Gf = (V, Ef ), cf , s, t) be the residual network of N with respect to f, S∗ be the set of vertices reachable ...
32 views

### construct graph using max flow algorithm

Given n pair of integer (di, dj), e.g. (0, 2), (1, 1), (1, 0), (1, 0)... Construct a directed graph G = ({1...n}, E) such that in-degree of vertex 1 is di and out-degree is dj. Is it possible to ...
27 views

### Ford Fulkerson MaxFlow dCut

Question is the following: Z={A,B} subset of V containing all Nodes. State dCut({Z}, G). Does the above dCut induce an upper bound to the maximum s – t flow value? If so,what is the induced upper ...
33 views

### Network Flow Optimization

Suppose we have a network with node set $N = \{1,\dots, n\}$ and arc set $E$. $(i, j) \in E$ if there is a link between node $i$ and node $j$. We need to send $L$ commodities from their respective ...
12 views

### Digraph: Flow with length constraint

I'm considering the following problem: Given a directed graph $G = (V,A)$ with unit capacities, determine if there exists a flow from $x$ to $y$ ($x = y$ is allowed) with a specific length $k$, i.e., ...
21 views

### Two disjoint minimum cuts in a flow network

I was studying flow networks and intersection/union of min cuts in such networks, Im trying to prove a theory that says if the intersection of two min cuts A, B had s in it (meaning (A)intersection(B)=...
7 views

### min-cut - max-flow: A flow that saturates every cut has a maximal flow?

I need some help understanding if this claim is correct: Given a flow network $N$ and a flow $f$ on this network. It is given that for every minimal cut $<S,T>$ , $f(e)=c(e)$ for every edge ...
43 views

### Algorithm for max flow and min cut, simultaneous

Good morning everyone. I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. One of the problems was asking for an ...
35 views

### Values of $s-t$ flows and cuts

$G = (V, A)$ is a directed graph where all arcs in $A$ have a capacity of $1$. The shortest length path in $G$ from $s$ to $t$ consists of exactly $d$ arcs. G has a total of $m$ arcs and $n$ vertices. ...
36 views

### Uniqueness of a minimum capacity $s-t$ cut

Two vertices $x$ and $y$ form an arc that is part of a minimum capacity $s-t$ cut in a directed graph $G = (V, A)$. Prove that another minimum capacity $s-t$ cut cannot exist in $G$ if it only ...
33 views

### Max flow in simple weighted graph with no specified source or sink

I am modeling a traffic network with a simple edge-weighted graph. The edge weights represent the capacity of each road. I would like to measure the maximum flow the network can accept. In order to ...
100 views

### Does the maximum bottleneck-capacity variant of Ford-Fulkerson always terminate?

We know that the generic Ford-Fulkerson Algorithm may not terminate in the presence of irrational capacities and that its maximum bottleneck-capacity variant always terminates within weakly polynomial ...
20 views

### A special condition on the Minimum Cost Flow Problem

I am working on the following exercise: Consider the minimum cost flow problem with the following additional constraint: For each vertex $i \in V$ we are given an upper bound $w_i$ for the amount ...
69 views