Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [network-flow]

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

0
votes
0answers
12 views

Dinic's algorithm

Given $ N = (G = (V , E),s, t, c)$ a flow network, we run the Dinic's algorithm (https://en.wikipedia.org/wiki/Dinic%27s_algorithm) on this Network. Consider some iteration $i$ which is not the last ...
1
vote
1answer
24 views

Cut In a Flow Network

Given $ N = (G = (V , E),s, t, c)$ a flow network (assume that the capacity $c$ is always positive) and $e = (u,v) \in E$. I would like to develop an algorithm that tell if there exist a min-cut (cut ...
0
votes
1answer
16 views

How to find the vertices of one component in a min-cut problem?

I need to write a min-cut algorithm on a undirected graph, and retrieve the vertices of one of the components $S$ or $T$. I know some algorithms, like resolving the associated Max Flow problem or ...
0
votes
1answer
19 views

Not able to understand the skew symmetry property in Flow Network

From Wikipedia: $G(V,E)$ is a finite directed graph in which every edge $\ (u,v) \in E$ has a non-negative, real-valued capacity $\ c(u,v)$. A flow network is a real function $\ f:V \times V \...
2
votes
1answer
21 views

3-connectivity as a set linear constraints

It turns out connectivity of a graph can be expressed as a set of linear constraints. https://www.researchgate.net/post/How_can_I_ensure_graph_connectivity_using_LP_or_MIP_formulation Giving a vertex ...
0
votes
0answers
18 views

Minimum Cost Flow Problem Formulation

A small town draws its water supply from the local river. The flow of (untreated) water in the river fluctuates with the seasons. To meet higher demand for (treated) water in some seasons, the town ...
0
votes
0answers
13 views

Calculating utilization of BITMAP protocol

i was reading around and didn't find any solution to my problem, either here in stackexchange, nor in recaps and tutorials online, so i am trying posting it here, hoping that i might get lucky and ...
0
votes
0answers
23 views

Find a matrix that describes a modularity score of a partition.

For a partition P of a network of n nodes and m edges into two disjoint communities, $V_{1}$ and $V_{2}$. Let $s=[s_{1},s_{2},...,s_{n}]$ where each $s_{i}$, corresponding to each vertex is 1 if that ...
2
votes
0answers
27 views

Path finding in time dependent graphs and murderous hitchhikers

Last week I heard some informatic students talking about car-to-car communication via wifi-hotspots in cars and the following problem occured to me: Suppose you are making a road trip with many ...
0
votes
2answers
19 views

Max Flow with aggregated edge capacities

I would like to find a solution for a max-flow problem where there is a combined capacity constraint on edges. For example, in the image below, the capacity for edge (1,3) and edge (2,3) should be 1 ...
0
votes
2answers
403 views

Network Flow: Algorithm to find a cut of smallest capacity among all cuts

You are given a flow network $G$ with $n > 4$ vertices. Besides the source $s$ and the sink $t$, you are also given two other special vertices $u$ and $v$ belonging to $G$. Describe an algorithm ...
0
votes
0answers
26 views

Convex Optimization: objective function in minimum cost flow problem

I have a graph $G=(N,V)$ where $|N|=n$ and $|V|=m$. I want to implement a solver (based on a specific algorithm for convex optimization) for a convex quadratic separable Min-Cost Flow Problem. $$min\{...
1
vote
1answer
44 views

stuck on island (probability)

There are many islands that are connected by one-way bridges, that is, if a bridge connects islands a and b , then you can only ...
0
votes
0answers
18 views

nonnegative flow can be decomposed into a nonnegative linear combination of directed $s–t$ paths and directed cycles.

I was asked to prove the following: Let $D = (V, A)$ be a directed graph and $s, t ∈ V$ be distinct. If $f ≥ 0$ is an $s–t$ flow (that is, $f$ is an $s–t$ flow and $f$ is nonnegative) with $\text{...
0
votes
0answers
23 views

Is this a valid proof of Hall's Theorem on System of Distinct Representatives?

Hall's Theorem states that for sets $A_1,...,A_n$ if and only for all $J\subseteq \{1,...,n\}$ we find $|\bigcup_{j\in J}A_j|\geq|J|,$ then we can choose $x_i\in A_i$ for all $i$ such that $\{x_1,...,...
0
votes
0answers
49 views

Meaning of (viable) and (non viable) flow pattern?

I found all the unknown traffic flows for this network (check picture), but in the end, the question is asking to give (one viable flow pattern) and (one that is not viable) what does that mean? any ...
1
vote
1answer
69 views

Use min-cut max-flow to prove that the matching number $\alpha'(G)$ of a bipartite graph is equal to its vertex cover number $\beta(G)$

My approach is to construct a network on the bipartite graph, with the source and sink being two extra vertices, each adjacent to all vertices from one partition of G. All edges are "forward" edges, ...
0
votes
0answers
31 views

Help applying linear algebra and systems of equations to visual network flow problem

The image above shows the "flows" of some arbitrary entities along certain paths $(i = 1,2...6)$. The value of the flow over a path is equal to $x_i$. Each dot is a "node". I need to find a system of ...
0
votes
0answers
26 views

How is delta value determined in this transshipment problem?

I am trying to understand how this transshipment problem is optimized from step to step. I have the answer on the exercice, but cannot really get it. The main point is clear: We want to transport (in ...
0
votes
0answers
21 views

how to formulate and prove networking problem

Formulate and prove a theorem that gives necessary and sufficient conditions so that a network with multiple sources and sinks has a flow that simultaneously meets all prescribed demands with ...
2
votes
1answer
68 views

Proving that the Wardrop/Nash equilibirum flow on a graph is “stable”?

Let $[0, 1] \subset \mathbb{R}$ be denoted $\mathbb{R}_{[0, 1]}$. Let $[0, \infty) \subset \mathbb{R}$ be denoted $\mathbb{R}_{\geq 0}$. Let $G$ be a finite, connected graph. Associate with each edge ...
2
votes
1answer
39 views

Proof of a graph theorem

Studying graph theory I found the following theorem for s,t vertex of the graph $G=(V,E)$ and a cut defined as "subset $C$ of $E$ an s−t cut if C = $δ ^{out}(U)$ for some subset U of V satisfying s $\...
0
votes
0answers
17 views

Flow value returned by function, and flow value

If I have a flow $f:V \times V \to \mathbb{R}$, in a network $R=(G,s,t,c)$ what is the difference between the value return by the function $f$, and the value of the flow $f$?
1
vote
1answer
60 views

Split network flow function

Let a graph $G = (V,E)$ a network $N = (G, s, t, c)$ and an integral flow funtion $f$ The value of f $v(f)=v_1+v_2+...+v_p$, where $v_i$ is a flow leaving the source. I must prove that there are $p$...
0
votes
0answers
38 views

Sum of flow network functions

It might be a pretty silly question but.. What is the sum of two flow network functions? You just go and make the sum of each flow function for every edge? Let f1 and f2 two flow functions a graph ...
0
votes
0answers
33 views

Flow Decomposition theorem explanation

I have a question about Flow Decomposition Theorem. In the theorem say that a flow $f$ can be decompose in $k$ flows, $f_1, f_2 ... f_k$, and the cost of the flow $f$ is equal to the sum of the costs ...
0
votes
0answers
161 views

Reducing an integral flow to $p$ mini flows in a network

Let $x$ be an integral flow in a given network $R = (G, s, t, c)$, with $v(x) = v_1 + v_2 + \cdots + v_p$, where $v_i \in \mathbb N∗$, $\forall i = 1, p, p > 1$. Prove that there exists $p$ ...
0
votes
0answers
36 views

Transport/flow network in GAP

How to define a transport network in GAP? I can't seem to find a single function related to transport networks or flows in general in the GAP-GRAPE manual. I'd be content with just manually adding ...
1
vote
1answer
43 views

Modelling of a flow network with a positional constraint

While I do realise pasting an exercise question in here is not exactly perfect form, I am desperate and I wil try anyway. So here it goes: Consider a set of n mobile computing clients in a town with ...
1
vote
1answer
20 views

Show that there are k directed walks from a to b in gamma having no common directed edge pairwise

Let $\Gamma$ be a digraph, $k$ a natural number and $a$, $b$ vertices in $\Gamma$ such that $$ \operatorname{outdegree}(a)-\operatorname{indegree}(a)=\operatorname{indegree}(b)-\operatorname{outdegree}...
0
votes
0answers
39 views

does strong duality hold for minimum cost flow problem

I know that the strong duality holds for linear programming and the optimal values of the objective functions in the primal and dual linear programming problems are equal. I am wondering whether the ...
0
votes
0answers
19 views

Showing that simple random walks on two graphs have the same type

Question Let $G$ be a connected infinite graph of bounded degree (which means that there exists $K>0$ such that $\text{deg}(v)\leq K$ for all vertices $v$ in G). Let $G_k$ be the graph obtained ...
0
votes
0answers
56 views

Feasible Flows and Incidence Vectors

Let $f$ be a function on the arc set $A$ of an acyclic network $N(x,y)$ (here $x$ is the source and $y$ the sink). Suppose $0 \leq f(a) \leq c(a)$ for all $a \in A$ ($c$ is the capacity function). ...
0
votes
1answer
119 views

Max flow min cut in matching reduced to max flow

I can not find the max flow, min cut in this graph where all edges have capacity 1. The graph: 1 The max flow in this graph from s to t is 2? But it is impossible to separate s and t without cutting ...
1
vote
0answers
162 views

How do I find the maximum independent set of a bipartite graph via Maximum Network Flow?

Background is in computer science, but I realize I'm well and fully into graph-theory, here. I have constructed the following bipartite graph where each node represents either a vertical or ...
0
votes
1answer
39 views

True or False: Flow network with $n$ internal nodes has $2^n$ different cuts with all min capacity

Prove whether true or false: For every $n >0$, there exists a flow network with $n$ internal nodes such that there are $2^n$ different cuts that all have minimum capacity. I have no idea how to ...
0
votes
0answers
17 views

Design of “balancing” networks with loopbacks

Say that you have a network of conveyor belts with nodes, where each node is a 2-lane crossover switch (2 in, 2 out, either straight-through or crossed-over). Beneš networks work to solve the problem ...
0
votes
0answers
15 views

LP to compute all cuts between 2 vertices of a graph

Given an undirected graph $G$ (for example a symmetric adjacency matrix) without weights, I want to compute all cuts of two chosen vertices in the graph. Actually there is an R-function st_cuts of ...
0
votes
0answers
23 views

Proving Easy Lemma about Flows

Let $D=(V,E)$ be some basic flow network and $f$ some flow. I'm trying to prove the following lemma: I've been told that this is a proof that follows directly from the definitions of flow yet I can't ...
1
vote
0answers
110 views

Graph Theory/Algorithm: Do multiple max flow imply multiple min cut?

We know that Ford-Fulkerson Algorithm (FFA) will yield max flow and min cut solutions at the same time. My question is: if restricted to integer graph only, does the existence of multiple max flow ...
0
votes
0answers
12 views

Fastest way to solve a very sparse, maximum weight (unbalanced) bipartite graphs

I'm trying to do maximum weighted bipartite matching on very sparse and fairly large (dimension $n$ is ~50,000) matrix. Question is: what's the best way to achieve this? (Small approximations are fine ...
0
votes
0answers
18 views

how to understand a manufacturing process w/ uncertain delays & rerouting?

Can anyone tell me what branch of mathematics I need to study in order to better understand the factors that govern the completion times in a multi-step process, in which the thing that's traveling ...
5
votes
3answers
114 views

Why can't set cover be reduced to min-cost max-flow?

Okay, so I know obviously I'm making some kind of easy mistake here, since set cover is NP-complete and min-cost max-flow is in P, but I can't figure out what the mistake is. So, given a universe $U$ ...
0
votes
0answers
14 views

Is it possible to list solutions to a maximum flow problem in poly(or pseudo-polynomial ) time?

For a given network flow problem, can we find all flow functions $f$ that achieve the maximum flow amount using some polynomial, or pseudo-polynomial time approach? By polynomial, I mean polynomial ...
0
votes
1answer
81 views

How tough is this graph?

In graph theory, toughness is a measure of the connectivity of a graph. A graph $G$ is said to be $t$-tough for a given real number $t$ if, for every integer $k > 1, G$ cannot be split into $k$ ...
1
vote
1answer
83 views

Min cost flow change in objective function by changing flow of some arc

I solving a problem that is formulated as a min cost flow problem. After finding the optimal solution, I would like to determine how the objective function will change if I increase/decrease flow of ...
0
votes
0answers
134 views

Example of a Minimum Cost Capacitated Flow Problem

I am struggling to find an example with a solution for a Minimum Cost Capacitated Flow problem. My network is defined as a graph G = (V, E), where each edge has a capacity c(u, v) > 0, a flow f(u, v) ...
0
votes
0answers
12 views

Graph with every node a binary flow of 1 out of every node

Is there a name for this type of graph? I have a hypergraph and am wondering if there is a name for when we have a flow of exactly one out of each node, along only one edge. There can be any amount of ...
0
votes
0answers
83 views

Maximum double-matching problem in a bipartite graph using max-flow algorithm

Ive encountered the following problem studying for my test, with no answer published to it: 1)Maximum double matching problem- given a bipartite graph G=(V=(LUR),E) describe an algorithm that returns ...
1
vote
0answers
92 views

Shortest path as a max flow problem

Using a road network, we were given the task to find the shortest path using various algorithms for each team, and our team was given the Edmonds–Karp algorithm to implement it. But reading the ...