Questions tagged [network-flow]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
22 views

Is a network flow equivalent to a walk?

Consider a directed graph where each edge has infinite capacity. Now consider a directed walk on this graph from arbirtary node s to arbitrary node t with $s \neq t$. Definition (Directed walk): A ...
  • 21
0 votes
0 answers
17 views

Network Flows - a cut

A really simple question that I cannot find a direct answer to. I guess it's considered so obvious but when finding a cut on a network flow graph (not necessarily min) can it cut an arc twice? TY
  • 21
0 votes
1 answer
16 views

Transforming LPP into transportation matrix

I need to transform an LPP into a transportation matrix, however, where I would expect greater than' for constraints on demand, the LPP only has 'less-than' constraints. Any hints on transforming this ...
  • 55
1 vote
1 answer
31 views

Comparing network graphs

I started out with a grid graph, performed some operations on it, and ended up with a set of networks; for example, , , , I need to compare these graphs. A thought that I had was to compare them with ...
  • 338
0 votes
0 answers
30 views

Comparing networks using graph theory

I'm new to graph theory so forgive if I use unconventional terminology. Please ask if there's any confusion regarding the statements I make. I have a bunch of undirected, unweighted, simple graphs ...
  • 338
1 vote
1 answer
44 views

Best possible way to withdraw amount from different accounts

I need to withdraw the maximum amount from different accounts under the following conditions: The following are the conditions: 1.) Minimum withdrawal is $\$1$. 2.) Amount can be transferred from one ...
1 vote
0 answers
41 views

A flow $f$ is maximum $\Leftrightarrow$ $\exists$ an empty $s$-$t$ cut

Given a flow network $(G,\mu,s,t)$. I am thinking about the following statement. A flow $f$ is maximum $\Leftrightarrow$ $\exists$ an empty $s$-$t$ cut I know "$\Rightarrow$ is correct, but also &...
  • 323
2 votes
0 answers
30 views

Non $0,\pm 1$ integer coefficient polytopes with integral extreme points

Suppose we have a linear system $$Ax\leq b\quad \text{where}\quad A\in \mathbb{Z}^{m\times n},b\in \mathbb{Z}^m.$$ In integer programming literature, we usually have that $A$ has only $\{0,\pm 1\}$ ...
  • 1,171
1 vote
1 answer
36 views

flow+flow is a flow [closed]

I have the following question: If $f$ is an $s$-$t$ flow in $(G,\mu, s, t)$ and $f'$ is an $s$-$t$ flow in $(G,\mu', s, t)$ then there exists an $s$-$t$ flow in $(G, \mu +\mu', s, t)$ of value $|f|+|f'...
  • 404
0 votes
1 answer
72 views

What is the meaning of this math formulation? [closed]

I have been wondering what is the meaning of this sigma with delta negative or plus in there (if my read is correct). $$ \sum_{i \in \Delta^{-}(j)} x_{i j k}-\sum_{i \in \Delta^{+}(j)} x_{j i k}=0 \...
0 votes
0 answers
38 views

maximum matching using Edmonds-Karp

Let $G=(A\cup B,E)$ be a undirected connected bipartite graph. Prove that one can determine a maximum cardinality matching in $G$ by using the Edmonds-Karp Algorithm with running time $\mathcal O(|E|\...
  • 284
0 votes
1 answer
16 views

Max-Flow: Modelling edge dependencies

For a toy problem I'm working on, I'd like to know if its possible to (easily) add the following type of constraints to a max-flow problem: if edge $x_{ij}$ is active (flow > 0), then also $x_{jk}$ ...
  • 145
2 votes
0 answers
34 views

Why can matrix rounding be seen as a max flow problem?

For a general max flow problem, we know that each intermediatte node must give away the same amount of flow it receives. Besides this, we also know that the amount of flow that leaves the origin node (...
  • 668
1 vote
0 answers
12 views

Estimate flux integral of $\frac{1}{|x|}$ in $\Bbb{R}^3$ through a quadratic surface.

My question occured reading this paper in the first example of section 6. Let $f:\Bbb{R}^3 \rightarrow \Bbb{R}^3$, $f(x)=|x|$ a vector field. Now divide $\Bbb{R}^3$ up into disjoint unit cubes ...
1 vote
0 answers
64 views

Finding Paths In Tripartite Graphs From Network Flow

Definition (Minimum T-Transversal): Let $T$ be the set of all triangles in a simple graph $G=(V,E)$. A T-transversal is a subset $S\subseteq E(G)$ such that every triangle in $T$ contains at least one ...
  • 77
0 votes
0 answers
8 views

Is there any special condition on finding the inital spanning tree for a minimum cost flow problem?

I was wondering... When we are working with a standard minimun cost flow problem, is there any additional condition on the initial basis besides defining a spanning tree? Take the graph below as an ...
  • 668
0 votes
1 answer
18 views

Given a max flow s-t in a network R, provide an algorithm to find the cut of max capacity.

By applying an algorithm we can find the max flow in a network. Is there a way to find the max capacity cut in O(m) from the residual graph of the max flow?
  • 61
0 votes
1 answer
29 views

Bad choice of path in maximum-flow algorithm

I'm currently studying the maximum-flow algorithm and encountered the following problem: The number on each edge is the capacity. I wonder what kind of bad choice can cause so many iterations. Thanks....
0 votes
0 answers
11 views

if any valid path has flow value <= gamma, then the maximum flow <= \gamma |E|

Prove this: In a network $(G = (V,E), u, s, t)$ with capacity set $u$, source $s$, and sink $t$, if any path from $s$ to $t$ has its value less than or equal to $\gamma$, then the maximum flow is less ...
1 vote
0 answers
33 views

Net flow out of $x$ equals net flow into $y$

Let $D=(V, A)$ be a digraph and $f$ a real-valued function on $A$. I am trying to show: $\sum\left\{f^{+}(v): v \in V\right\}=\sum\left\{f^{-}(v): v \in V\right\}$, if $f$ is an $(x, y)$-flow, then ...
's user avatar
0 votes
1 answer
35 views

Value of max flow and min cut in a graph with no directed paths

Let $N(x, y)$ be a network which contains no directed $(x, y)$-path. How do I show that the value of a maximum flow and the capacity of a minimum cut in $N$ are both zero?
's user avatar
0 votes
1 answer
21 views

Average of maximal flows and each arc's level of saturation

I am going through the proof of the max-flow min-cut theorem presented in the following paper: Ford, L., & Fulkerson, D. (1956). Maximal Flow Through a Network. Canadian Journal of Mathematics, 8, ...
2 votes
1 answer
30 views

Maximum flow with minimal number of vertices used

In many of the research problems I encountered recently, the following version of the minimum cost maximum flow problem came up. We are given a directed graph $D$, a source vertex $s$ and a terminal ...
  • 43
0 votes
0 answers
14 views

Max/min flow for scheduling slots

So imagine there is a bus schedule: These are return routes. NYE<->LND 2 buses needed NYE<->STN 3 buses needed STN<->LND 2 buses needed Single arrow signifies one-way journey. Note ...
  • 79
0 votes
0 answers
30 views

Polynomial time "fairness" algorithm that assigns leaders for $m$ tasks amongst $n$ workers.

Suppose we have $n$ workers and $m$ tasks. Suppose each task has a workforce $S_i \subseteq \{1, 2, .., n\}$. Note that $S_i \cap S_j \neq \emptyset$ is possible (and expected). Given this ...
0 votes
2 answers
88 views

Sum of weight of edges of each vertex of a $4$ regular graph can be made $0$.

Suppose we have $4$ regular graph $G$. We have to show that each edge can be labelled with $-1$ or $1$ such that the total flow in a vertex is $0$. There is also a question related to it: To find an ...
  • 12.1k
0 votes
0 answers
13 views

Algorithmically find the maximal flow of a capacitated network using the max-flow min cut theorem.

I've worked through a proof of the max-flow, min cut theorem. Visually it is easy to find a minimum cut of a network. Is there an algorithmic way for a computer to find one? I have seen some mentions ...
0 votes
1 answer
58 views

Maximum "k-to-k" matching in bipartite graph

I was "inspired" to extend the concept of Maximum "$2$-to-$1$" matching in a bipartite graph 2-to-1 matching by extending it to "k-to-k" matching for some natural number ...
  • 33
1 vote
1 answer
136 views

Maximal flow with multiple sources and sinks

How do I find a maximal flow in a network with multiple sources and sinks using the Ford-Fulkerson algorithm 'without adding anything to the network'. I know that we could add a supersource node and a ...
0 votes
0 answers
36 views

Finding flow decomposition

In Daniel Marcus's Graph Theory - A Problem Oriented Approach: According to the integral flow decomposition theorem, a flow with value n can be written as the sum of n unit path flows and possibly ...
0 votes
0 answers
27 views

Convert Dual LP to a Network Flow Problem

Consider the Dual LP: $$ \min\sum_{e\in E}c_ey_e$$ s.t.: $$\sum_{e:e\in p}y_e\ge 1\ \ \text{for each}\ \ p\in \mathcal P\\ y_e\ge 0$$ $e$: Represents an edge in $E$ $c_e$: Max flow capacity of an ...
  • 477
0 votes
0 answers
15 views

Prove that the size of a max-flow problem on a given network is equal to the maximal value of the objective function in it's linear program version

So there are lots of material on converting a max-flow problem to a linear program, but I'm not really as familiar with the proof side of things. How do we prove that the converted LP maximal value of ...
  • 477
0 votes
1 answer
26 views

prove that the subset formed by all the nodes reachable from $s$ in $Rf$ is included in every subset $S′$ from any min-cut $(S′,T′)$

Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$. For each edge $e \in E$, we have $c(e) \in \Bbb N$. also, we are given a max flow function $f$ on that network. Let $...
  • 15
0 votes
1 answer
119 views

Simple transportation problem becoming more complicated with additional information

The scenario is that we own a chemical company with 2 warehouses. We have had the following quantities of chemical A sent to 4 different ports ready for transportation to our warehouses: We require ...
0 votes
1 answer
146 views

Given a flow network and a max flow f on it, Determine whether there are at least 4 different max flows.

I'm having trouble solving this one and would really appreciate any help. thank you in advance! so, the problem is: given a flow network with integer capacities on the edges and a max flow f on that ...
  • 15
0 votes
1 answer
61 views

Finding a cycle in a graph under constraints

You are given a directed graph $G=(V,E)$ with capacities $c(e) \in R^+$ and a set of edges $E_1 \subset E$. You want to find a cycle $C = (v_1, v_2), (v_2, v_3) ... (v_n, v_1)$ in the graph under the ...
  • 55
0 votes
0 answers
25 views

How to solve min cost flow for indivisible items?

I have a transshipment problem of assigning supply to demand. Supply comes from multiple suppliers with different capacities. Demand also comes from multiple demands of different sizes. Assigning a ...
-1 votes
1 answer
71 views

Network flow optimization, additional symmetry condition

Let $N=(V,E,s,t,c)$ be a network (defined as usual). The "Max-flow min-cut" theorem states that the max flow passing from the source $s$ to the sink $t$ is given by the minimal cut. https://...
  • 1,187
0 votes
1 answer
44 views

Showing that the flow value is well defined.

Let $G$ be a directed graph with edge set $E$ and $u:E \to \mathbb{R}_{\geq 0}$ a capacity function, as well as $x: E \to \mathbb{R}_{\geq 0}$ be a function. Then $x$ is called an $s-t$ flow if the ...
2 votes
1 answer
308 views

Max-flow problem for networks with weighted vertices [closed]

Let us define a network to be a weighted and directed graph $G = (V,E)$ such that $w(e) \geq 0 \ \forall e \in E$ and $\exists u,v \in V $ such that $s$ is a source (no edges going into $s$), and $t$ ...
  • 425
0 votes
2 answers
75 views

Minimum sub-graph which preserves max-flow min-cut

Consider an undirected, weighted graph $G = (P,E)$ where $P$ is the node set and $E$ is the edge set. Say that for a single source and target pair, $s$ and $t$ there is a min-cut $C_{\min}$ which ...
  • 95
0 votes
0 answers
26 views

How to turn a maximum preflow into a maximum flow in $\mathcal{O}(nm)$?

If the preflow were acyclic I could use the topological order to eliminate excess and guarantee a maximum flow. Without that property I do not know how to proceed. Is it possible to make any maximum ...
  • 197
0 votes
2 answers
65 views

What does the 'maximum flow' in a network graph mean?

The maximum flow in a capacity-constrained network can be found by methods like Folk-Fulkerson. For example, in the graph below: Here, the maximum flow from S to T has been calculated to be 19. I ...
  • 243
0 votes
0 answers
20 views

Network Flows and transforming into basic networks

Is it possible to transform a flow network into a basic network when the following two conditions are stated: All edges are directed (it is not a mixed/undirected network) There are no capacity ...
  • 31
-2 votes
1 answer
49 views

Is this a max-flow min-cut problem? [Reference needed!]

I've been searching for a while now, but did not succeed in finding whether the problem I have is actually a max-flow min-cut problem or it can be deduced to it, i.e. the algorithms that are used to ...
  • 2,195
1 vote
0 answers
22 views

Model or algorithm for a balanced graph

I have a graph which each nodes has the following features: A node can produce some "energy" (or something like that); A node has to satisfy the need energy and so use the energy produced ...
  • 101
1 vote
0 answers
64 views

Defining a Minimum cost-flow problem with piecewise costs

I need to formulate an Integer Linear Programming model for a Minimum cost-flow problem over a graph without constraints on edges. The cost over edges isn't linear but piecewise, given by: $c(x_{ij})=\...
1 vote
1 answer
38 views

Minimum Cut formulation for binary linear program

I am trying to formulate the following program into a minimum cut formulation: $$\text{minimize}_{y\in \left\{0,1\right\}^V} \sum_{i\in V}\sum_{j\in V} d_{i,j}y_i(1-y_j) + \sum_{i\in V}f_iy_i.$$ Where ...
  • 6,068
2 votes
0 answers
84 views

prove the flow $f(χ) $ across any cut is equal to the flow value of the network $|f|$

I have one question please about proving that the flow $f(χ) $ across any cut is equal to the flow value of the network $|f|$. Now, the flow of the cut is the difference between flow of forward edges (...
  • 1,103
1 vote
1 answer
26 views

Formulation of cost minimization problem of graph

I'm having trouble solving following integer programming using python. Let $G$ be a graph with nodes set $V=\{0,1,...,|V|-1\}$ and edges set $E$. Define cost of each edge $(m,n)$ as $c_{m,n}$ set ...
  • 55

1
2 3 4 5
8