Chapter_22_Elementary_Graph_Algorithms/exercises_22.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 22.2 Breadth-first search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-1\n",
    "\n",
    "> Show the $d$ and $\\pi$ values that result from running breadth-first search on the directed graph of Figure 22.2(a), using vertex 3 as the source."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| \\ | 1 | 2 | 3 | 4 | 5 | 6 |\n",
    "|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n",
    "| $d$ | $\\infty$ | 3 | 0 | 2 | 1 | 1 |\n",
    "| $\\pi$ | NIL | 4 | NIL | 5 | 3 | 3 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-2\n",
    "\n",
    "> Show the $d$ and $\\pi$ values that result from running breadth-first search on the undirected graph of Figure 22.3, using vertex $u$ as the source."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| \\ | $r$ | $s$ | $t$ | $u$ | $v$ | $w$ | $x$ | $y$ |\n",
    "|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n",
    "| $d$ | 4 | 3 | 1 | 0 | 5 | 2 | 1 | 1 |\n",
    "| $\\pi$ | $s$ | $w$ | $u$ | NIL | $r$ | $x$ | $u$ | $u$ |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-3\n",
    "\n",
    "> Show that using a single bit to store each vertex color suffices by arguing that the BFS procedure would produce the same result if lines 5 and 14 were removed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Duplicate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-4\n",
    "\n",
    "> What is the running time of BFS if we represent its input graph by an adjacency matrix and modify the algorithm to handle this form of input?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Theta(V^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-5\n",
    "\n",
    "> Argue that in a breadth-first search, the value $u.d$ assigned to a vertex $u$ is independent of the order in which the vertices appear in each adjacency list. Using Figure 22.3 as an example, show that the breadth-first tree computed by BFS can depend on the ordering within adjacency lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\delta$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-6\n",
    "\n",
    "> Give an example of a directed graph $G = (V, E)$, a source vertex $s \\in V$, and a set of tree edges $E_\\pi \\subseteq E$ such that for each vertex $v \\in V$, the unique simple path in the graph $(V, E_\\pi)$ from $s$ to $v$ is a shortest path in $G$, yet the set of edges $E_\\pi$ cannot be produced by running BFS on $G$, no matter how the vertices are ordered in each adjacency list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./img/22.2-6_1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-7\n",
    "\n",
    "> There are two types of professional wrestlers: \"babyfaces\" (\"good guys\") and \"heels\" (\"bad guys\"). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have $n$ professional wrestlers and we have a list of $r$ pairs of wrestlers for which there are rivalries. Give an $O(n+r)$-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BFS, the new reachable node should have a different type. If the new node already have the same type with the current node, then it is impossible to perform such a designation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-8 $\\star$\n",
    "\n",
    "> The __*diameter*__ of a tree $T = (V, E)$ is defined as $\\max_{u,v \\in V}\\delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BFS with a random node as the source, then BFS from the node with the largest $\\delta$, the largest $\\delta$ in the second BFS is the diameter of the tree, $O(V + E)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.2-9\n",
    "\n",
    "> Let $G = (V, E)$ be a connected, undirected graph. Give an $O(V + E)$-time algorithm to compute a path in $G$ that traverses each edge in $E$ exactly once in each direction. Describe how you can find your way out of a maze if you are given a large supply of pennies."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eulerian path."
   ]
  }
 ],
 "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
}