Chapter_23_Minimum_Spanning_Trees/exercises_23.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 23.1 Growing a minimum spanning tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-1\n",
    "\n",
    "> Let $(u, v)$ be a minimum-weight edge in a connected graph $G$. Show that $(u, v)$ belongs to some minimum spanning tree of $G$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$S = {u}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-2\n",
    "\n",
    "> Professor Sabatier conjectures the following converse of Theorem 23.1. Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V - S)$ be any cut of $G$ that respects $A$, and let $(u, v)$ be a safe edge for $A$ crossing $(S, V - S)$. Then, $(u, v)$ is a light edge for the cut. Show that the professor's conjecture is incorrect by giving a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not light."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-3\n",
    "\n",
    "> Show that if an edge $(u, v)$ is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$(u, v)$ is a bridge in the minimum spanning tree, thus $V$ can be divided into two components."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-4\n",
    "\n",
    "> Give a simple example of a connected graph such that the set of edges $\\{(u, v):$ there exists a cut $(S, V - S)$ such that $(u, v)$ is a light edge crossing $(S, V - S)\\}$ does not form a minimum spanning tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$E = \\{(u, v), (v, w), (w, u)\\}$ with the same weight."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-5\n",
    "\n",
    "> Let $e$ be a maximum-weight edge on some cycle of connected graph $G = (V, E)$. Prove that there is a minimum spanning tree of $G' = (V, E - \\{e\\})$ that is also a minimum spanning tree of $G$. That is, there is a minimum spanning tree of $G$ that does not include $e$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The edges in the cycle are lighter than the maximum-weight edge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-6\n",
    "\n",
    "> Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Counterexample: $E = \\{(u, v), (u, w)\\}$ with the same weight."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-7\n",
    "\n",
    "> Argue that if all edge weights of a graph are positive, then any subset of edges that connects all vertices and has minimum total weight must be a tree. Give an example to show that the same conclusion does not follow if we allow some weights to be nonpositive."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not a tree: remove one edge from the cycle.\n",
    "\n",
    "Nonpositive: $E = \\{(u, v), (v, w), (w, u)\\}$ with the same weight -1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-8\n",
    "\n",
    "> Let $T$ be a minimum spanning tree of a graph $G$, and let $L$ be the sorted list of the edge weights of $T$. Show that for any other minimum spanning tree $T'$ of $G$, the list $L$ is also the sorted list of edge weights of $T'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-9\n",
    "\n",
    "> Let $T$ be a minimum spanning tree of a graph $G = (V, E)$, and let $V'$ be a subset of $V$. Let $T'$ be the subgraph of $T$ induced by $V'$, and let $G'$ be the subgraph of $G$ induced by $V'$. Show that if $T'$ is connected, then $T'$ is a minimum spanning tree of $G'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cut $V'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-10\n",
    "\n",
    "> Given a graph $G$ and a minimum spanning tree $T$, suppose that we decrease the weight of one of the edges in $T$. Show that $T$ is still a minimum spanning tree for $G$. More formally, let $T$ be a minimum spanning tree for $G$ with edge weights given by weight function $w$. Choose one edge $(x, y) \\in T$ and a positive number $k$, and define the weight function $w'$ by\n",
    "\n",
    "> $$\n",
    "w'(u, v) = \\left \\{\n",
    "\\begin{array}{ll}\n",
    "w(u, v) & \\text{if}~(u, v) \\ne (x, y), \\\\\n",
    "w(x, y) - k & \\text{if}~(u, v) = (x, y).\n",
    "\\end{array}\n",
    "\\right .\n",
    "$$\n",
    "\n",
    "> Show that $T$ is a minimum spanning tree for $G$ with edge weights given by $w'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lighter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.1-11 $\\star$\n",
    "\n",
    "> Given a graph $G$ and a minimum spanning tree $T$, suppose that we decrease the weight of one of the edges not in $T$. Give an algorithm for finding the minimum spanning tree in the modified graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the edge $(u, v)$ is not in $T$ and its weight is less than some edge in the path from $u$ to $v$, then replace the edge with maximum weight in the path with $(u, v)$."
   ]
  }
 ],
 "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
}