Tag Info

3

There is an errata in this printing, the corrected proof is found in the link below. Indeed, the correction requires you to consider subsets $V_1=\{v:(u,v)\in E\}$ and $V_2=\{v:(v,u)\in E\}$. https://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf

2

Create an undirected weighted graph $G=(V,E)$ where $V=\{C_1,C_2,M_1, \dots, M_n\}$. For each $i=1,\dots,n$ add the edge $(C_1, M_i)$ of weight $a_i$ and the edge $(C_2, M_i)$ of weight $b_i$. For each pair of distinct indices $i,j=1,\dots,n$ add the edge $(M_i, M_j)$ of weight $d_{i,j}$. You are looking for a $C_1$-$C_2$-cut of minimum weight, namely a ...

2

You want each node to have the same number of incoming and outgoing edges. Let $\alpha(v)$ be the number of edges in $A$ outgoing in $v$ minus the number of edges in $A$ outgoing from $v$. Consider the graph $H=(V,E)$ and let $\delta(v)$ be the degree of $v$ in $H$. We need to find an orientation of the edges in $H$ such that each vertex $v$ has an out-...

2

When all edges have weight 2 and $n = |V|$ the problem is equivalent to longest path which is NP-complete. So unless P = NP, there is no efficient algorithm for solving the problem.

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 ...

2

Suppose there is a max-flow $f'\neq f$. Then, The function $\Delta f= f'-f$ is a nontrivial flow of flow value $0$ in $R_f$. (Nontrivial just means $\Delta f$ is not zero on some edge. There is a cycle in a $0$-valued nontrivial flow. How do we prove point 2? Start with any edge with non-zero flow. Visit vertexes by following an outgoing edge with non-...

1

Here is a formal proof, thanks to your hint of the max-flow min-cut theorem. Let us treat $G$ directly as a network with capacity function $w$. Suppose we are given three arbitrary nodes $a, b, c$ in $V$. Select a minimum $a$-$c$ cut of $G$, $(S, T)$. Let $w(S,T)$ be the capacity of $(S,T)$ as a cut of $G$, i.e. $$w(S,T)=\sum_{u\in S, v\in T} w(u,v).$$ ...

1

The shortest path and the path with the largest bottleneck are not the same in general. It is easy to construct a counterexample: pick $G=(V,E)$ with $V=\{a,b,c\}$, and $E=\{ (a,b), (a,c), (c,b) \}$ where $(a,b)$ has capacity $1$ while $(a,c)$ and $(c,b)$ have capacity $2$. The shortest path between $a$ and $b$ consists of the single edge $(a,b)$. The path ...

1

the answer to "is definitelly NOT is A." routing routing is done by network layer before i go in the next ones here is disabmiguity warning. B. and C. are performed by TCP which is transport layer. if the application is using a custom transport protocol on top of UDP, i.e., RTP for transmitting multimedia, then, depending on the definition, it ...

1

You are on the right track. Connect the starting node $s$ to each node in the first layer with an edge of capacity one. Since the balls $b_{i1}$ and $b_{i2}$ cannot stored in the same bin, for each bin $X$ in $\hat B_{i1}\cap\hat B_{i2}$, instead of connecting $b_{i1}$ and $b_{i2}$ directly to the node $X$ in the second layer, construct a node $c_{i,X}$ ...

1

Here are two papers giving examples that show that the analysis of the Edmonds–Karp algorithm is tight: Norman Zadeh, Theoretical efficiency of the Edmonds–Karp algorithm for computing maximal flows. Zvi Galil, On the theoretical efficiency of various network flow algorithms.

1

There are different (equivalent) definitions of residual networks (depending on whether you keep edges with capacity $0$ or not). Anyway, the claim is false since we can select the original network as a graph with no edges (meaning that the only feasible flow is the empty flow, as long as the source and the sink vertices are distinct). Then, the residual ...

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'(... 1 That would actually work as well, but it is more cumbersome than just adding a new source and sink. 1 What you describe can happen in a feasible flow. However the net flow across the (undirected) edge$\{u,v\}$would be$0$. Also, you say that the original graph has flow$2c$, this is false since the amount of flow from a vertex$s$to a vertex$t$in a graph is not the sum of the flows across all the edges, but rather the amount of flow leaving$s$or, ... 1 The easy solution is to add an edge between$s$and$u$with infinite weight and$t$and$v$with infinite weight. Note though that this doesn't mean that$s$and$u$will be connected in$G[A]\$.

1

These lecture notes also mention the reduction from the circulation problem to the max-flow problem (Theorem 2), and reduction from network flows with lower bounds to the max-flow problem (Theorem 5). The proofs are of a few lines.

Only top voted, non community-wiki answers of a minimum length are eligible