Chapter 6 - Weighted Graph Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 6: Weighted Graph Algorithms (Completed 10/25: 40%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulating Graph Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1 [3]\n",
    "\n",
    "For the graphs in Problem 5-1:\n",
    "\n",
    "(a): Draw the spanning forest after every iteration of the main loop in Kruskal’s algorithm.  \n",
    "(b): Draw the spanning forest after every iteration of the main loop in Prim’s algorithm.  \n",
    "(c): Find the shortest path spanning tree rooted in $A$.  \n",
    "(d): Compute the maximum flow from $A$ to $H$.  \n",
    "\n",
    "![Skiena Fig 5-1](Figures/Skiena_Fig_5-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**Graph 1**:\n",
    "\n",
    "First we put the edges in sorted order:\n",
    "\n",
    "$\\text{(B,E): 1}$  \n",
    "$\\text{(I,J): 1}$  \n",
    "$\\text{(C,E): 2}$  \n",
    "$\\text{(C,F): 2}$  \n",
    "$\\text{(G,I): 2}$  \n",
    "$\\text{(G,J): 2}$  \n",
    "$\\text{(B,C): 3}$  \n",
    "$\\text{(B,D): 3}$  \n",
    "$\\text{(G,H): 3}$  \n",
    "$\\text{(A,D): 4}$  \n",
    "$\\text{(D,E): 4}$  \n",
    "$\\text{(H,J): 4}$  \n",
    "$\\text{(A,B): 6}$  \n",
    "$\\text{(D,G): 6}$  \n",
    "$\\text{(E,G): 6}$  \n",
    "$\\text{(E,H): 7}$  \n",
    "$\\text{(E,F): 8}$  \n",
    "$\\text{(A,I): 9}$  \n",
    "$\\text{(F,H): 11}$  \n",
    "\n",
    "**(a):** Kruskal's\n",
    "\n",
    "In Kruskal's algorithm, we sequentially add the next least-weight edge, unless there is already a path between the two vertices in the current tree/forest.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-1.jpg)\n",
    "\n",
    "**(b):** Prim's\n",
    "\n",
    "In Prim's algorithm, we add the next least-weight edge that connects a non-tree node with the tree. Unlike in Kruskal's algorithm, there is only a single tree at all times.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-2.jpg)\n",
    "\n",
    "**(c):** Shortest Path from $A$\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-3.jpg)\n",
    "\n",
    "**(d):** Maximum Flow from $A$ to $H$\n",
    "\n",
    "In the graphs below I successively found the shortest path from $A$ to $H$, then computed the Residual Flow Graph by subtracting the lowest edge-weight along that path from all the edges in the path. The maximum flow was 13. Note that this is equal to the weight of the minimum $A-H$ cut. Specifically the minimum $A-H$ cut consists of deleting edges $(A,B), (A,D), (G,I),$ and $(G,J)$, which have a total weight of 13 and which are exactly the edges with weight zero (missing) in the final Residual Flow Graph.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-4.jpg)\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-5.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Graph 2**:\n",
    "\n",
    "Again, first we put the edges in sorted order:\n",
    "\n",
    "$\\text{(A,B): 1}$  \n",
    "$\\text{(C,G): 1}$  \n",
    "$\\text{(M,N): 1}$  \n",
    "$\\text{(A,E): 2}$  \n",
    "$\\text{(I,M): 3}$  \n",
    "$\\text{(B,F): 4}$  \n",
    "$\\text{(D,H): 4}$  \n",
    "$\\text{(J,K): 4}$  \n",
    "$\\text{(E,I): 5}$  \n",
    "$\\text{(H,L): 5}$  \n",
    "$\\text{(F,J): 6}$  \n",
    "$\\text{(O,P): 8}$  \n",
    "$\\text{(J,N): 9}$  \n",
    "$\\text{(L,P): 9}$  \n",
    "$\\text{(N,O): 9}$  \n",
    "$\\text{(E,F): 10}$  \n",
    "$\\text{(G,K): 11}$  \n",
    "$\\text{(I,J): 11}$  \n",
    "$\\text{(K,O): 12}$  \n",
    "$\\text{(F,G): 13}$  \n",
    "$\\text{(B,C): 18}$  \n",
    "$\\text{(C,D): 20}$  \n",
    "$\\text{(G,H): 22}$  \n",
    "$\\text{(K,L): 23}$  \n",
    "\n",
    "**(a):** Kruskal's\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-6.jpg)\n",
    "\n",
    "**(b):** Prim's\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-7.jpg)\n",
    "\n",
    "**(c):** Shortest Path from $A$\n",
    "\n",
    "Here the edges represent the *cumulative* cost of reaching the vertex.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-8.jpg)\n",
    "\n",
    "**(d):** Maximum Flow from $A$ to $H$\n",
    "\n",
    "The maximum flow in this case was only 3. Note once again that this is equal to the weight of the minimum $A-H$ cut. Specifically the minimum $A-H$ cut consists of deleting edges $(A,B)$ and $(A,E)$, which have a toal weight of 3 and which are exactly the edges with weight zero (missing) in the final Residual Flow Graph.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-9.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimum Spanning Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2 [3]\n",
    "\n",
    "Is the path between two vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Definitely not. Otherwise, what was the point of Dijkstra's algorithm, if we could just use Prim's or Kruskal's to find the minimum spanning tree?\n",
    "\n",
    "As a counterexample, think of a triangle with 3 edges, each with weight 1. Any minimum spanning tree will only have 2 of these edges. Pick the 2 vertices with degree 1 in the tree. In the tree, the shortest path between them passes through the 3rd vertex and has weight 2, while in the full graph there is a direct edge of weight 1 connecting them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.3 [3]\n",
    "\n",
    "Assume that all edges in the graph have distinct edge weights (i.e. , no pair of edges have the same weight). Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "No.\n",
    "\n",
    "As a counterexample, think of a triangle with 3 edges with weights 2, 3, and 4. The minimum spanning tree will only have the edges of weight 2 and 3. The path between the two leaves must travel through the root, and therefore has weight $2 + 3 = 5$. However, in the full graph, there is a direct edge between them with weight $4$. Therefore the MST-path was not the shortest path on the full graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.4 [3]\n",
    "\n",
    "Can Prim’s and Kruskal’s algorithms yield different minimum spanning trees? Explain why or why not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "They both yield correct results, so this could only occur if there is more than one correct minimmum spanning tree.\n",
    "\n",
    "I can see 3 potential ways that 2 minimum spanning trees can differ, without changing the total weight of the tree. I'll briefly discuss each one and why I think each can or cannot occur between MST's produces by Prim's and Kruskal's algorithms. They are ordered by decreasing trivialness.\n",
    " \n",
    "**1) Different root, but otherwise same nodes and edges.** This difference can occur because Prim's algorithm allows you to select the starting point, which becomes the root of the MST.\n",
    "\n",
    "**2) Equal-weight edges are swapped.** Here it depends on the implementation. For example, a triangle with 3 weight-1 edges will engender an MST with one of the edges missing. Prim's algorithm seems to be deterministic once a starting point is selected, but Kruskal's algorithm, as given in the textbook, uses quicksort to sort the edges based on weight. The random nature of quicksort can give rise to different orderings among the 3 edges since they are of equal weight. Therefore the 2 edges selected to be in the MST may differ on repeated runs of Kruskal's algorithm, only one of which can match Prim's. If a stable sort like merge sort was used instead, so that equal-weight edges were placed in order based on their array index, this may lead to a deterministic result that may always match Prim's.\n",
    "\n",
    "**3) Different edges with different weights, but the sum is still the same.** For example, one algorithm might include edges of weights 2 and 4, while the other might include edges of weights 3 and 3. Both add to 6, but clearly they are different edges with different weights. I do not believe this situation can occur because 1) both algorithms are greedy, and so would choose to include the edge of weight 2 as soon as possible. 2) I have not been able to construct an example where the selection of an edge meaningfully forces the algorithms to make different decisions later. And 3) choosing the edge with weight 3 doesn't pay off until after the other edge of weight 3 is included; therefore at this moment, the two algorithms may have included the same nodes but have different total weights. If we were to delete the non-tree nodes at this point, only one of the algorithms could be correct. You may object that the incorrect algorithm was making its decision based on the presence of the rest of the nodes, and that deleting them \"tricked\" the algorithm. But this isn't true because both algorithms are greedy, and are not capable of that sort of planning ahead."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.5 [3]\n",
    "\n",
    "Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights? Explain why or why not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "They both work. Both algorithms check if the 2 vertices in a candidate edge are already connected. This ensures that both algorithms will add only $n-1$ edges to span a graph with $n$ vertices, even if adding additional edges would lower the weight. At each stage, both algorithms seek to add the algorithm with the lowest weight; it doesn't matter if the number happens to be negative. Note that when dealing with negative weights, non-edges should have weight infinity, not zero.\n",
    "\n",
    "Problems where you care about cumulative weights across paths are likely to have more difficulty with negative weights. Intuitively, this might have to do with the fact that the number of vertices in different paths can vary; for example, a 3-edge path might be of lower weight than a 2-edge path between the same pair of vertices. In the MST problem, spanning trees must have $n-1$ edges, so this is not an issue here.\n",
    "\n",
    "This problem will likely be related to question 6.7, since in this question you could simply add a large constant value to every edge weight to ensure they are all positive, find the minimum spanning tree, and then subtract off the value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.7 [5]\n",
    "\n",
    "**(a):** Let $T$ be a minimum spanning tree of a weighted graph $G$. Construct a new graph $G'$ by adding a weight of $k$ to every edge of $G$. Do the edges of $T$ form a minimum spanning tree of $G'$? Prove the statement or give a counterexample.\n",
    "\n",
    "**(b):** Let $P = \\{s, . . . , t\\}$ describe a shortest weighted path between vertices $s$ and $t$\n",
    "of a weighted graph $G$. Construct a new graph $G'$ by adding a weight of $k$ to every edge of $G$. Does $P$ describe a shortest path from $s$ to $t$ in $G'$? Prove the statement or give a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):**\n",
    "\n",
    "Yes. We'll prove this by contradiction.\n",
    "\n",
    "Let $G'$ be a new graph constructed by adding a weight of $k$ to every edge of $G$. Let $T_1$ be a minimum spanning tree of $G$ and $T_2$ be a MST of $G'$, and suppose that $T_1$ and $T_2$ do not contain all the same edges. Let $w(T)$ and $w'(T)$ be the weight of tree $T$ on graphs $G$ and $G'$, respectively.\n",
    "\n",
    "We know that $w(T_1) < w(T_2)$, since $T_1$ is a MST of $G$ while $T_2$ is not. Similarly, we know that $w'(T_2) < w'(T_1)$.\n",
    "\n",
    "To show that these two expressions contradict one another, we need to relate $w$ to $w'$.\n",
    "\n",
    "Constructing $G'$ involved adding $k$ to every edge in $G$. Therefore the weight of a tree will incease by $k$ for each edge it contains. Since MST's must contain $n-1$ edges, we have $w'(T_1) = w(T_1) + k(n-1)$ and $w'(T_2) = w(T_2) + k(n-1)$. Importantly, both increase by the same amount.\n",
    "\n",
    "We can then rewrite our second inequality $w'(T_2) < w'(T_1)$ as $w(T_2) + k(n-1) < w(T_1) + k(n-1)$. Removing the common term on both sides yields $w(T_2) < w(T_1)$. But this directly contradicts our first inequality $w(T_1) < w(T_2)$.\n",
    "\n",
    "In other words, if the weight of $T_2$ were less than that of $T_1$ on $G'$, then this would also be true on $G$, since moving between graphs changes their weights by the same amount, because they contain the same number of edges. But this contradicts the assumption that $T_1$ was a MST of $G$.\n",
    "\n",
    "Therefore the weight of $T_2$ cannot be less than that of $T_1$ on $G'$, and so $T_1$ must be a minimum spanning tree of $G'$ as well as of $G$.\n",
    "\n",
    "**(b):**\n",
    "\n",
    "No. This is because different paths between $s$ and $t$ can contain different amounts of edges, and therefore their total weights will change by different amounts when converting between $G$ and $G'$.\n",
    "\n",
    "As a simple counterexample, imagine a triangle with edges of weights 1, 1, and 3. The shortest path between the two vertices contained in the weight-3 edge is to go around through the other vertex. This path will have weight 2, less than the direct path of weight 3. However, if all edge weights were increased by 2, and therefore became 3, 3, and 5, in this case the fastest route between the same two vertices is the direct edge of weight 5, rather than going around for a total weight of 6. The shortest weighted path between these two vertices is different on graphs $G$ and $G'$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Union-Find"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.14 [3]\n",
    "\n",
    "The *single-destination shortest path* problem for a directed graph seeks the shortest path *from* every vertex to a specified vertex $v$. Give an efficient algorithm to solve the single-destination shortest paths problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Dijkstra's algorithm gives the shortest path **from** a vertex $v$ **to** every other vertex. If we flipped the direction of every edge and then used Dijkstra's algorith, the resulting shortest paths **from** $v$ would correspond to shortest paths **to** $v$ in the orignal graph.\n",
    "\n",
    "Since Dijkstra's algorithm is efficient ($O(m + n \\log n)$ with a priority queue implementation), we just need an efficient way to flip the direction of every edge. It was implied that this could be done in linear time on unweighted graphs on page 181, in the context of determining if a directed graph was strongly connected. We need to iterate over every edge $(x,y)$, adding the reverse edge $(y,x)$ each time to the new graph. Using adjacency lists, iterating over all edges would be $O(m)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.15 [3]\n",
    "\n",
    "Let $G = (V,E)$ be an undirected weighted graph, and let $T$ be the shortest-path spanning tree rooted at a vertex $v$. Suppose now that all the edge weights in $G$ are increased by a constant number $k$. Is $T$ still the shortest-path spanning tree from $v$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "No. The reason is that the amount by which the weight of a path increases is proportional to the number of edges it contains. Therefore with weight of different paths can increase by different amounts.\n",
    "\n",
    "As a counterexample, imagine a triangle with two edges of weight 1 and one edge of weight 3. Let $u$ and $v$ be the two vertices incident on this weightier edge. The shortest-path spanning tree rooted at $v$ will be composed of a single branch going around the perimeter, containing the two edges of weight 1. The path to vertex $u$ will have weight 2, since 2 weight-1 edges were traversed.\n",
    "\n",
    "Now add a weight of 2 to every edge, making 2 edges with weight 3 and 1 edge with weight 5. The path from $v$ to $u$ on the original shortest-path tree now has weight 6, since 2 weight-3 edges were traversed. However, the direct edge between $u$ and $v$ now has weight 5, and therefore now is the shorter path. On this new graph, the shortest-path spanning tree rooted at $v$ will have 2 branches, each of length 1, of weights 3 and 5.\n",
    "\n",
    "Therefore the adding a constant weight to every edge can alter the shortest-path spanning tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.16 [3]\n",
    "\n",
    "Answer all of the following:\n",
    "\n",
    "**(a):** Give an example of a weighted connected graph $G = (V,E)$ and a vertex $v$, such that the minimum spanning tree of $G$ is the same as the shortest-path spanning tree rooted at $v$.\n",
    "\n",
    "**(b):** Give an example of a weighted connected directed graph $G = (V,E)$ and a vertex $v$, such that the minimum-cost spanning tree of $G$ is very different from the shortest-path spanning tree rooted at $v$.\n",
    "\n",
    "**(c):** Can the two trees be completely disjointed?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):**\n",
    "\n",
    "A triangle with edge weights 1, 1, and 10. For any vertex chosen as the root, and Minimum Spanning Tree (MST) and Shortest-Path Tree (SPT) will be the same. Specifically, they both will contain the two weight-1 edges and will not contain the weight-10 edge.\n",
    "\n",
    "\n",
    "**(b):**\n",
    "\n",
    "In the example given below, the MST and SPT rooted at $A$ are very different, only having one edge in common.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-10.jpg)\n",
    "\n",
    "**(c):**\n",
    "\n",
    "No. Prim's algorithm for finding the MST and Dijkstra's algorithm for finding the SPT differ in how they rate the desirability of potential new tree nodes and edges. Specifically, Dijkstra's includes the cost of the path from the root to the connecting tree node, while Prim's only cares about the cost of the new edge.\n",
    "\n",
    "On the first iteration of these algorithms, these conditions are identical, because Dijkstra's cannot include the cost of the adjoining tree-path because there isn't one: the tree has only one node. Therefore they both will select the same edge, specifically, the one with the lowest weight.\n",
    "\n",
    "This can be seen in the example from part (b): the single edge that the MST and SPT have in common is the lowest-weight edge adjacent to $A$, specifically edge $(A,B)$ of weight 2.\n",
    "\n",
    "What if there are multiple edges leaving the root that tie for the smallest weight? The SPT will contain all of them, and the MST must contain at least one of them. Therefore they still will have at least one edge in common.\n",
    "\n",
    "Using Kruskal's algorithm instead of Prim's to find the MST doesn't change the result: the lowest-weight edge leaving the root will still be selected to be included in the tree (or one of them, if there are multiple). And this edge will also be in the SPT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.17 [3]\n",
    "\n",
    "Either prove the following or give a counterexample:\n",
    "\n",
    "**(a):** Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?\n",
    "\n",
    "**(b):** Suppose that the minimum spanning tree of the graph is unique. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):**\n",
    "\n",
    "This is identical to problem 6.2, and so I quote my solution to that problem:\n",
    "\n",
    "\"Definitely not. Otherwise, what was the point of Dijkstra's algorithm, if we could just use Prim's or Kruskal's to find the minimum spanning tree?\"\n",
    "\n",
    "\"As a counterexample, think of a triangle with 3 edges, each with weight 1. Any minimum spanning tree will only have 2 of these edges. Pick the 2 vertices with degree 1 in the tree. In the tree, the shortest path between them passes through the 3rd vertex and has weight 2, while in the full graph there is a direct edge of weight 1 connecting them.\"\n",
    "\n",
    "**(b):**\n",
    "\n",
    "No. Suppose we have a triangle with edge weights 2, 3, and 4. The unique MST will consist of the edges of weights 2 and 3, leaving out the edge of weight 4. On the MST, traveling between the two vertices included in the weight-4 edge would require passing through the root, and the path would have weight $2 + 3 = 5$. But on the original graph the shortest path is the edge between them, which has weight $4$. Therefore even in the case where the MST is unique, finding the MST still does not mean you have found the shortest path between any two vertices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Network Flow and Matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.24 [3] Unfinished\n",
    "\n",
    "A matching in a graph is a set of disjoint edges—i.e., edges that do not share any vertices in common. Give a linear-time algorithm to find a maximum matching in a tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Some thoughts.\n",
    "\n",
    "First note that all trees are bipartite: just make each layer a different color.\n",
    "\n",
    "In the book, this problem is only described in terms of unweighted graphs as an application of the network flow problem, which does use weighted graphs. The problem is solved by connecting a source to all L vertices and a sink to all R vertices. All edges have weight 1, both original and added. Then find the maximum flow from source to sink.\n",
    "\n",
    "One idea I had was to use breadth-first search to compute the tree. Then count the number of clusters in each row. One edge can be included from each cluster since they all connect to the same parent, so the number of edges you can include from each level is equal to the number of clusters. But you can only include edges from every other level. So just add up the number of clusters on the even numbered levels and the odd numbered levels, and the greater one is the one you choose to include in the matching.\n",
    "\n",
    "This idea doesn't work though in general, maybe only if the tree is fully dense. If a level includes a dead-end edge, then you can include both the dead end edge and edges in the next lower level.\n",
    "\n",
    "Below is an example of a graph, with the BFS tree computed starting from vertex 1. The vertices are numbered in the order that they were added to the tree. The brackets indicate the number of clusters in each level, and the circled edges are the ones that perhaps form a maximum matching. Note that the number of clusters are $1-1-1-1-2-2-2$, and summing up alternating levels equals $6$ and $4$, but the circled matching contains $8$ edges, showing that the maximum matching can exceed these values.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Hallock_Fig_6-11.jpg)\n",
    "\n",
    "Perhaps an idea is to include as many leaf edges as you can at each level, starting at the bottom. In the example above, 6 out of the 8 edges are leaves.\n",
    "\n",
    "How about a recursive algorithm that when in finds a leaf, it deletes the leaf and it's parent, and any other children of the parent.\n",
    "\n",
    "Iterate over the adjacency list, looking for vertices with degree 1?\n",
    "\n",
    "Is there a way to do this conceptually on the original graph? Perhaps targetting dead-ends first? The original graph is still a tree, but isn't organized into a top down shape with a root."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}