1
vote
1answer
30 views

Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
1
vote
1answer
21 views

Maximum Flow - Ford Fulkerson

I tried using the Ford Fulkerson algorithm with the following question: The result I got was 25: I've been told that my solution is not correct. I was not told what the solution was however. ...
0
votes
1answer
37 views

Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
0
votes
0answers
22 views

Prove a problem about Networks(in graph theory)

$S$ and $T$ are two subsets of $V(N)$, which is the set of vertices in network N. Let $S^c$ denotes the complement of $S$ and $[S,S^c]$ be the set of arcs starting in $S$ and finishing in $S^c$. If ...
0
votes
1answer
19 views

How to find a max flow in a flow network

I'm trying too many days to find an answer for this question with no success, so I hope you can help me. Let's say I have the following flow network: ...
0
votes
2answers
59 views

What is the difference between maximal flow and maximum flow?

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really ...
0
votes
1answer
46 views

Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...
0
votes
2answers
89 views

Real world application of dominating set?

can anyone tell me about the application of vertex coloring problem and algorithm for vertex color problem in graph or networks.
0
votes
1answer
37 views

the source and the sink have a maximum capacity

Consider a variant of max-flow networks in which all vertices different from the source and the sink have a maximum capacity. As we know, Such a network can be transformed into a usual max-flow ...
1
vote
1answer
50 views

Given a max flow on a graph, how do you determine the actual edges that belong to the minimal cut?

After applying an algorithm (like Ford-Fulkerson) that gives you the max flow over a graph $G(V,E)$, how do you determine the actual edges that belong to the minimal cut (recall the Max Flow/ Min Cut ...
1
vote
1answer
297 views

Finding the max flow of an undirected graph with Ford-Fulkerson

Given the following undirected graph, how would I find the max-flow/min-cut? Now, I know that in order to solve this, I need to redraw the graph so that it is directed as shown below. However, ...
0
votes
0answers
25 views

Proof of strong connectednes in digraphs by using maximum flow

G= (V,E) is strongly connected digraph if it has a directed path from i to j for every i,j in V. I want to prove that: G is strongly connected <=> every (S,T) cut in G has at least one arc in each ...
0
votes
0answers
40 views

Potential values of minimum cost maximum flow algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
0
votes
1answer
36 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 ...
0
votes
0answers
42 views

Minimum u-v cuts

I am working on the following problem: Consider the $G=(V,E)$ and let $w:E \rightarrow \mathbb{R^+}$ be an assignment of nonnegative weights to its edges. Given $u,v \in V$, let f(u,v) be the weight ...
0
votes
1answer
81 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
36 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 ...
0
votes
0answers
26 views

Network component detection

Suppose I have a (directed) graph with nonnegative edge weights. I would like to separate the graph into what you might call "$\epsilon$-components", that is, a partition $\{ V_i \}$ of the set $V$ of ...
1
vote
1answer
427 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 ...
0
votes
1answer
46 views

The Dons Problem: Minimizing the time for complete diffusion of information [duplicate]

A friend of mine asked me this question recently. He might have heard from somewhere else, but that's the extent of my background on this problem. It might have a completely different name, and I ...
2
votes
1answer
68 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 ...
0
votes
0answers
49 views

max flow/ min cut

Im trying to work out a flow of size 10 for the commodity network below (using Ford and Fulkerson algorithm). When working out the flow, would this be an acceptable solution: Where 2 + 2 + 2 + 2 ...
1
vote
0answers
146 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
1answer
45 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 ...
0
votes
0answers
59 views

Prime-Dual Algorithm Proof for Transshipment Problem

Consider an example of Transshipment Problem (TP) with a directed graphy $D=(N,A)$ such that $b(N)=0$ ($b$ are node demands). Suppose that one of the iteration from Dijkstra's algorithm finds that a ...
1
vote
1answer
223 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
71 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
66 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 ...
0
votes
1answer
66 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 ...
2
votes
2answers
69 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
84 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
132 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 ...
0
votes
1answer
888 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 ...
0
votes
0answers
176 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 ...
1
vote
0answers
141 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 ...
0
votes
1answer
48 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 ...
0
votes
1answer
128 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
325 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 ...
1
vote
1answer
128 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 ...
3
votes
2answers
1k 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
504 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
405 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 ...
10
votes
4answers
515 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 ...
2
votes
0answers
98 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
2answers
1k 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 ...
0
votes
2answers
208 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 ...
3
votes
1answer
354 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
320 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. ...
7
votes
3answers
282 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 ...
1
vote
1answer
195 views

calculating walks in an undirected graph using linear algebra identity

I am reading a text on maths applied to naturally occurring networks, eg. social networks. The section I am on is "Walks" networks. The text says: Walks: which allow both nodes and edges to be ...