# Questions tagged [network-flow]

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

303 questions
Filter by
Sorted by
Tagged with
45 views

### How to formulate a condition for a flow graph to have valid output/input over any possible set of activations/deactivations of sources/sinks

I have a Graph G with some set of sources and sinks. Each edge, source and sink has a maximum capacity of 1. A node divides its inputs evenly among the output edges. (Might not be relevant to the ...
57 views

### Write down linear system describing the flow in the network

Network question I currently have the following answer: X1 - X2 - X3 - X4 = 0 X2 = 1 X3 = -1 X4 = 5 But the answer sheet says this is correct: ...
149 views

5k views

### Definition of capacity of cut in a flow network

In the flow network below, an S-T cut is made. The net flow across the cut is $12-4+11=19$. The capacity of the cut is $12+14=26$. The "backwards" edge $(v_3,v_2)$ is not counted when calculating ...
918 views

### Find the minimum amount of edges in a graph to improve flow

Given a flow network with maximum flow $f$, I want to find the minimum amount of edges, that if their capacity will increase, the maximum flow will increase. I have tried using BFS to find the amount ...
787 views

### A game: When can you merge two directed graphs?

I am trying to consider the conditions under which you can win the following directed graph game: Graph merging game. Fix an acyclic directed graph $G$; its vertex set is $V$, and its edge set is $E$....
272 views

### Maximum and Sets of vertex-disjoint paths in a not-directed graph

Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices. Let's consider one vertex $V$ of this graph (which is a source). The problem ...
22k views

### Belt Balancer problem (Factorio)

So this question is inspired by the following thread: https://forums.factorio.com/viewtopic.php?f=5&t=25008 In it, the poster is examining an $8$-belt balancer (more on that to come) which he ...
169 views

### Finding a minimum cut for an (s-t) flow: why not just cut the start/end edges?

Most examples I've seen involve cuts snaking through graphs picking off various edges. My question is why not simply do a cut either involved the edges leaving the source or the edges entering the ...
131 views

### Max-Flow Min-Cut

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image? (Something like this - image)
642 views

### Maximum flow on a directed, acyclic graph

What would be the best algorithm to use for finding max-flow/min-cut on a directed, acyclic graph with integer flows, capacities, and vertex demands? I've been thinking Dinic's Algorithm would be ...
242 views

### Weighted Katz Centrality

Given a graph G with n nodes and adjacency matrix A, the Katz Centrality measure, K(G), is given by $K(G)[i] = \sum_{k=1}^{\infty}\sum_{j=1}^{n}\alpha^k(A^k)_{ji}$ s.t. $\alpha$ is an attenuating ...
1k views

### Network flows - formulating the max flow problem as a min cost flow problem

I have been trying to look this up, and I could only find a min cost flow to max flow transformation on the internet. Apparently, this transformation can be done by setting the costs to 0. Another ...
35 views

### What are those weighed graphs called?

Let $G = (V, E)$ be a directed graph, and define the weight function $f : V \sqcup E \to \mathbb{R}^+$ as follows: sum of weights of vertices is 1, if a vertex has edges coming out of it, their ...
339 views

### Max-flow/min-cut to determine densest subgraph

I have been trying to understand how a maximum average degree problem can be solved as a maximum flow problem for my optimization class from this article: https://hal.archives-ouvertes.fr/inria-...
46 views

### Why it is not trivial that $Z_k$-flow gives $k$-flow

In Diestel graph theory book, theorem 6.3.3 (Tutte 1950) states: A multigraph admits a $k$-flow iff it admits a $\mathbb{Z}_k$-flow. I don't understand why do we need a proof, because, by definition,...
392 views

### Is there any algorithm to find all the solutions of the following special linear Diophantine system?

Consider the following system. 1) $a_{11}x_1 + a_{21}x_2 + \cdots + a_{m1}x_m=d_1$ 2) $a_{12}x_1 + a_{22}x_2 + \cdots + a_{m2}x_m=d_2$ $\vdots$ n) $a_{1n}x_1 + a_{2n}x_2 + \cdots + a_{mn}x_m=d_n$ ...
50 views

### It would be nice if someone has some idea! (A Diophantine system associated with a network flow)

Assume that we are given a connected network flow with n nodes, $\{1, ..., n\}$, and m arcs. For each arc, say $x_{ij}$ from node i to node j, there is a maximum capacity level given as $M_{ij}$. ...
2k views

### Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
202 views

### What measures of centrality exist for fully connected networks with weighted directed edges?

I have a network of cities with transport links between them. The transport links are not symmetric in both directions, therefore asymmetric edges between nodes. There is a variable number quantifying ...
3k views

### Group Theory vs Graph Theory [closed]

I would like to know that, For a given graph can we find an associated finite group? If there are more than one such group, what are the differences and similarities between them? Here by a graph I ...
77 views

### Is it possible to turn a weighted adjacency matrix into an ODE compartment model?

I have an idea for a project that hinges on this idea. Lets say we have an adjacency matrix of a DiGraph where the i,j entry represents an out-going edge from node i to node j and at this position ...
456 views

### Max/Min flow of a network

I have a network: How do I figure out the maximum and minimum possible flow through each undefined branch?
2k views

### Airline scheduling using minimum network flow

Consider the following table for an airline company:                          &...
512 views

### Max Flow - Changing the capacity of an edge

Let $G=(V,E)$ be a flow network from $s$ to $t$. I have a maximum flow $f\colon E\to Z$ that was calculated using Ford-Fulkerson. How can I efficiently update $f$ when I need to subtract the ...
1k views

### Reduction to a max flow problem from a sudoku like puzzle

Given an $n$ by $n$ grid of which some of the squares are black and some are white. I'm allowed to mark some of these squares and the question is to prove whether a given grid with given black squares ...
83 views

### Decompose a flow network into several trivial flows

Let $f$ be a flow in (a directed) network $G$. Show that it is possible to express $f$ as a sum of another flow $f_0$ which value is 0, and at most $|E|$ flows, each of which is trivial - i.e. flows ...
88 views

### Multi-commodity flow problem. What if only one commodity? (Context: column generation)

What problem can arise when the number of commodities is only one when looking at a multi-commodity flow problem? This question was asked by my professor in the context of column generation and ...
1k views

### Linear programming and shortest path

Given the linear programming formulation of the shortest path problem:  \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in V^{-}(...
103 views

### Books on Multi-Commodity Minimum Cost Flow Problems

I'm searching for books on Multi-Commodity Minimum Cost Flow Problems (MCMCF) with theoretical aspects (solvability, optimality conditions, similar statements like in the case of Min Cost Flow,...). ...
496 views

### Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
938 views

### Proving the congestion of a butterfly network.

In MIT's 6.042j course assignment 6. In problem 5, it is required to prove that a butterfly network has congestion of \sqrt{N}. If we have an 8-input butterfly network and let's assume that all of the ...
85 views

### Explain how to find a max $(s-t)$ flow in a network

Explain how to find a max $(s-t)$ flow in a network, where some vertices are assigned capacities giving the maximum flow that can pass through those vertices. and Illustrate this method on the ...
84 views

### verifying minimum capacity of cut

So I have a cut $(P,P')$ on some network and its capacity is $13$. Now I'm told to assume that the current flow on the network is the max flow, is the cut of minimum capacity? So far all we've ...
917 views

### How many “cuts” does a flow network have?

Assuming a single source, single sink digraph with |V| vertices, including source s and sink t. How many “cuts” does a flow network have?
346 views

### A equivalent condtion for existence of feasible circulation

A circulation in a directed graph $D$ is a function $g:E(D)\rightarrow\mathbb{R}$ satisfying the conservation condition at every vertex. Let $l,u:E(D)\rightarrow \mathbb{R}^{+}_{0}$ be a lower and ...
162 views

### All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent along ...
133 views

### What are dynamic networks.

From my understanding, dynamic networks are similar to traditional models except that they function in continuous time and have edges and nodes that evolve over time? Is this a correct understanding? ...
26 views

### Why are dynamic networks probabilistic? [duplicate]

I have a only survey level background in network science but am interested in it. I was browsing wikipedia and read this page, (https://en.wikipedia.org/wiki/Dynamic_network_analysis.) In that ...