New answers tagged

0

Just adding to the answer of D.W.. Following is a simple example of a graph network that contains an exponential number of $(s,t)$ min cuts. Let the vertex set be $V = \{s\} \cup \{u_{1},\dotsc,u_{n}\} \cup \{v_1,\dotsc,v_n\} \cup \{t\}$. Let the edges set contains the directed edges $(s,u_{i})$, $(u_{i},v_{i})$, and $(v_{i},t)$ for each $i \in \{1,\dotsc,n\}...


2

Build a grid graph, with one node per entry in the matrix, and edges between each pair of adjacent nodes. Also add a source node $s$ with an edge from $s$ to each blue node, and a sink node $t$ with an edge from each white node to $t$. Set the capacity of each edge to 1, except the $s$-to-blue edges have capacity $\infty$, and the white-to-$t$ edges have ...


1

Case 1, increase the weight. Consider a path on at least three vertices with capacity 1 for every edge. Max-flow is 1, min-cut is 1. Increase one of the edges' weight, and the max-flow will still be 1, hence the claim is false. Case 2, let $C$ be a minimum cut with cost $w(C)$. Decrease the weight of one of the edges in $C$ to get a new minimum cost $w'(...


Top 50 recent answers are included