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
1
vote
1answer
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 ...
1
vote
0answers
202 views

Jackson network, steady state

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 ...
0
votes
1answer
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 ...
1
vote
1answer
234 views

Spanning Tree - Equivalent Properties

I am working on the following problem: Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') \geq ...
1
vote
1answer
88 views

Finding maximum flow of directed network with two inputs

I am given a directed network graph with three fixed verticess where two of these are "inputs" and and one is the "sink". I'm asked to find the maximal flow through the network. How should go about ...
1
vote
1answer
3k views

Proof of König's theorem

Let $G=(V,E)$ be a graph. $H\subseteq V$ is called a vertex cover of $G$ iff $(u,v)\in E\Rightarrow u\in H\vee v\in H$. Now let's assume $G$ is bipartite, i.e. $V=V_1 \cup V_2$ and $E\subseteq V_1\...
3
votes
1answer
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 ...
2
votes
0answers
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$ ...
1
vote
0answers
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, ...
0
votes
1answer
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, ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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$ ...
0
votes
1answer
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 ...
3
votes
2answers
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)$. ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
4
votes
1answer
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$. ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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?
2
votes
1answer
2k views

Flow network - minimum capacity cuts proof

Let's start out by reviewing max-flow min-cut, as well as the flow networks they operate on. http://en.wikipedia.org/wiki/Flow_network http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Let $G = (...
0
votes
1answer
70 views

Individual components of flow along edges in a graph

I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an "in-...
4
votes
1answer
2k views

Unimodular matrix definition?

I'm a bit confused. Based on Wikipedia: In mathematics, a unimodular matrix M is a square integer matrix having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
0
votes
1answer
213 views

Network Simplex Method: How to relabel the vertices and arcs such that the truncated matrix is upper triangular and non-singular.

Suppose $G = (V, A)$ is the acyclic weakly connected digraph with$ V $consisting of vertices $v_{i}$ $(i = 1, 2, ..., 8)$ in which the seven arcs are $(v 1 , v 2 ), (v 3 , v 2 ), (v 4 , v 3 ),(v 7 , v ...
0
votes
1answer
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 ...
0
votes
2answers
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$...
2
votes
1answer
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 ...
5
votes
2answers
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?
3
votes
2answers
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) ...
2
votes
1answer
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 ...
4
votes
1answer
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 ...
11
votes
4answers
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 ...
5
votes
1answer
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 ...
2
votes
0answers
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 ...
0
votes
1answer
926 views

Multicommodity flow in polynomial size

The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size? Linear program of multicommodity flow $maximize \...
0
votes
2answers
2k views

How to calculate the maximum flow in this graph by the Edmonds-Karp algorithm?

How do I use the Edmonds-Karp algorithm to calculate the maximum flow? I don't understand this algorithm $100\%$. What I need to know is about flow with minus arrow. Here is my graph: . Our $1-6-...
0
votes
1answer
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 ...
0
votes
2answers
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-...
2
votes
1answer
248 views

Sparsest cut is solvable on trees

The problem is to prove that Sparsest cut is solvable on trees in polynomial time. A short review, a sparsest cut is linear program $$\min \frac{c(S,\overline{S})}{D(S,\overline{S})}$$ where $c(S,\...
4
votes
1answer
579 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
4
votes
1answer
8k views

Linear Algebra: Network Flow problem

So I have the following problem: And I have obtained the following system of equations: $$\begin{align*} -x_1+x_2&=400\\ x_1+x_3-x_4&=600\\ x_2+x_3+x_5&=300\\ x_4+x_5&=100 \end{align*}...
3
votes
1answer
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. ...
3
votes
1answer
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'...
2
votes
1answer
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......
2
votes
2answers
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 ...
7
votes
3answers
362 views

What sort of mathematical methods and models are used to model the brain

What sorts of mathematical tools, models and methods and theoretical frameworks do people use to simulate the function of the brain's neural networks? What mathematical properties do different brains ...
2
votes
2answers
1k views

Queueing Theory: How to estimate steady-state queue length for single queue, N servers?

I have a real-life situation that can be solved using Queueing Theory. This should be easy for someone in the field. Any pointers would be appreciated. Scenario: There is a single Queue and N ...

1
3 4 5
6
7