Chapter_22_Elementary_Graph_Algorithms/exercises_22.5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 22.5 Strongly connected components"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.5-1\n",
    "\n",
    "> How can the number of strongly connected components of a graph change if a new edge is added?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$-(K - 1) \\sim +1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.5-2\n",
    "\n",
    "> Show how the procedure STRONGLY-CONNECTED-COMPONENTS works on the graph of Figure 22.6. Specifically, show the finishing times computed in line 1 and the forest produced in line 3. Assume that the loop of lines 5–7 of DFS considers vertices in alphabetical order and that the adjacency lists are in alphabetical order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./img/22.3-2_1.png)\n",
    "\n",
    "{r}, {u}, {q, y, t}, {x, z}, {s, w, v}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.5-3\n",
    "\n",
    "> Professor Bacon claims that the algorithm for strongly connected components would be simpler if it used the original (instead of the transpose) graph in the second depth-first search and scanned the vertices in order of _increasing_ finishing times. Does this simpler algorithm always produce correct results?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.5-4\n",
    "\n",
    "> Prove that for any directed graph $G$, we have $((G^T)^{SCC})^T = G^{SCC}$. That is, the transpose of the component graph of $G^T$ is the same as the component graph of $G$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$u \\leadsto v \\overset{T}{\\rightarrow} v \\leadsto u$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.5-5\n",
    "\n",
    "> Give an $O(V + E)$-time algorithm to compute the component graph of a directed graph $G = (V, E)$. Make sure that there is at most one edge between two vertices in the component graph your algorithm produces."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add edge $(u', v')$ if $u \\in C_{u'}$, $v \\in C_{v'}$ and there is an edge $(u, v) \\in E$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.5-6\n",
    "\n",
    "> Given a directed graph $G = (V, E)$, explain how to create another graph $G' = (V, E')$ such that (a) $G'$ has the same strongly connected components as $G$, (b) $G'$ has the same component graph as $G$, and (c) $E'$ is as small as possible. Describe a fast algorithm to compute $G'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate SCCs, create a loop in each SCC, connect SCCs with one edge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 22.5-7 \n",
    "\n",
    "> A directed graph $G = (V, E)$ is __*semiconnected*__ if, for all pairs of vertices $u, v \\in V$, we have $u \\leadsto v$ or $v \\leadsto u$. Give an efficient algorithm to determine whether or not $G$ is semiconnected. Prove that your algorithm is correct, and analyze its running time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $\\forall i \\in [1, K)$, there is an edge $(u,v) \\in E$, $u \\in C_i$, $v \\in C_{i+1}$, then the graph is semiconnected, $O(V + E)$."
   ]
  }
 ],
 "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
}