Chapter_26_Maximum_Flow/exercises_26.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 26.2 The Ford-Fulkerson method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-1\n",
    "\n",
    "> Prove that the summations in equation (26.6) equal the summations in equation (26.7)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\sum_{v \\in V_2} f(s, v) = 0$, $\\sum_{v \\in V_1} f(v, s)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-2\n",
    "\n",
    "> In Figure 26.1(b), what is the flow across the cut $(\\{s, v_2, v_4\\}, \\{v_1, v_3, t\\})$? What is the capacity of this cut?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$f(S, T) = f(s, v_1) + f(v_2, v_1) + f(v_4, v_3) + f(v_4, t) - f(v_3, v_2) = 11 + 1 + 7 + 4 - 4 = 19$.\n",
    "\n",
    "$c(S, T) = c(s, v_1) + c(v_2, v_1) + c(v_4, v_3) + c(v_4, t) = 16 + 4 + 7 + 4 = 31$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-3\n",
    "\n",
    "> Show the execution of the Edmonds-Karp algorithm on the flow network of Figure 26.1(a)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-4\n",
    "\n",
    "> In the example of Figure 26.6, what is the minimum cut corresponding to the maximum flow shown? Of the augmenting paths appearing in the example, which one cancels flow?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-5\n",
    "\n",
    "> Recall that the construction in Section 26.1 that converts a flow network with multiple sources and sinks into a single-source, single-sink network adds edges with infinite capacity. Prove that any flow in the resulting network has a finite value if the edges of the original network with multiple sources and sinks have finite capacity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Flow in equals flow out."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-6\n",
    "\n",
    "> Suppose that each source $s_i$ in a flow network with multiple sources and sinks produces exactly $p_i$ units of flow, so that $\\sum_{v \\in V} f(s_i, v) = p_i$. Suppose also that each sink $t_j$ consumes exactly $q_j$ units, so that $\\sum_{v \\in V} f(v, t_j) = q_j$, where $\\sum_i p_i = \\sum_j q_j$. Show how to convert the problem of finding a flow $f$ that obeys these additional constraints into the problem of finding a maximum flow in a single-source, single-sink flow network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$c(s, s_i) = p_i$, $c(t_j, t) = q_j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-7\n",
    "\n",
    "> Prove Lemma 26.2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-8\n",
    "\n",
    "> Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-9\n",
    "\n",
    "> Suppose that both $f$ and $f'$ are flows in a network $G$ and we compute flow $f \\uparrow f'$. Does the augmented flow satisfy the flow conservation property? Does it satisfy the capacity constraint?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It satisfies the flow conservation property and doesn't satisfy the capacity constraint."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-10\n",
    "\n",
    "> Show how to find a maximum flow in a network $G = (V, E)$ by a sequence of at most $|E|$ augmenting paths. (Hint: Determine the paths after finding the maximum flow.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the minimum cut."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-11\n",
    "\n",
    "> The __*edge connectivity*__ of an undirected graph is the minimum number $k$ of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge connectivity of a cyclic chain of vertices is 2. Show how to determine the edge connectivity of an undirected graph $G = (V, E)$ by running a maximum-flow algorithm on at most $|V|$ flow networks, each having $O(V)$ vertices and $O(E)$ edges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use each $v$ as the source, find the minimum minimum cut."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-12\n",
    "\n",
    "> Suppose that you are given a flow network $G$, and $G$ has edges entering the source $s$. Let $f$ be a flow in $G$ in which one of the edges $(v, s)$ entering the source has $f(v, s) = 1$. Prove that there must exist another flow $f'$ with $f'(v, s) = 0$ such that $|f|=|f'|$. Give an $O(E)$-time algorithm to compute $f'$, given $f$, and assuming that all edge capacities are integers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26.2-13\n",
    "\n",
    "> Suppose that you wish to find, among all minimum cuts in a flow network $G$ with integral capacities, one that contains the smallest number of edges. Show how to modify the capacities of $G$ to create a new flow network $G'$ in which any minimum cut in $G'$ is a minimum cut with the smallest number of edges in $G$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}