New answers tagged

0

An edge $uv$ is in some MST if and only if it is a minimum-weight edge of some cut. So we need to find a $uv$-cut with a minimum number of edges whose weight is strictly less than $w(uv)$. Once those edges are removed, $uv$ will be in some MST. Algorithmically, any min $st$-cut algorithm, applied on the subgraph of edges of weight less than $w(uv)$, will ...


0

Create vertices $s$, $t$ $f_1, f_2, ..., f_n$ for each of the $n$ families. $t_1, t_2, ..., t_m$ for each of the $m$ tables. Create edges from $s$ to $f_i$ with capacity the size of the $i$th family. from $f_i$ to $t_j$ with unit capacity from $t_j$ to $t$ with the capacity the size of the table. This ensures that each family sends at most one person to ...


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


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


0

First of all, since each square consists of $4$ cells and an $n \times m$ matrix contains $nm$ cells, you can clearly fit at most $\lfloor nm/4 \rfloor$ many different cells. If $n,m$ are both even, then you can fit $nm/4$ different square-shaped squares. In all other cases, you have to be more cunning. I won't ruin the joy of the puzzle by explaining how to ...


0

Copied from StackOverflow: Each arc u-->v belongs to some s--t min cut if and only if there is no residual path from u to t, there is no residual path from s to v, and there is no residual path from u to v. To prove the if direction, consider the cut consisting of vertices reachable from s or u by a residual path, which is an s--t cut by (1), has zero ...


Top 50 recent answers are included