Graph Algorithms

Individual Homework: Graph AlgorithmsIn class we discussed finding a minimum spanning tree in anetwork of nodes and link. A network of nodes and links iscalled a “graph” in computer science. I know you arethinking “graph” means something like � = �$, but this issomething completely different, with the same name. Agraph is literally a set of nodes and a set of links.Walking a graphA “walk” in a graph is moving from node to node along links.For example, BCABD is a walk in the graph to the right.However, AEB is not a walk, because you can’t go directlyfrom A to E.1. Give an example of a walk in this graph that visits four different nodes.2. Give an example of a walk that starts and ends at the same place.A walk that starts and ends at the same place is called a “circuit.” If the circuitdoes not have any repeated nodes (other than the fact that the start and end arethe same), it is called a “cycle.” For example, BDFB is a cycle containing 3 nodes.3. Give an example of a circuit that goes through all the nodes in this graph.4. Find a cycle containing 4 nodes.5. Find a cycle containing 5 nodes.6. Try to find a cycle containing 6 nodes. (Remember a cycle can’t touch a node more than once.)7. Try to find a cycle containing all 7 nodes.Euler and the Bridges of KönigsbergLeonhard Euler (pronounced “oiler”—it’s German, actually Swiss) came up with the concept of graphswhen he was intrigued by a classical puzzle called the Bridges of Königsberg. You can read more about iton the Base CS blog. Because of this puzzle and Euler’s solution, we call certain kinds of walks on graphs“Eulerian walks.” An Eulerian walk hits all the links in the graph exactly once. Likewise, an “Euleriancircuit” is a walk through the graph that hits all the links exactly once and you end up where you started.For example, in the small graph to the left, IHKJIK is anEulerian walk. (You can trace the nodes in that order withoutlifting your pencil.) On the other hand, in the small graph tothe right, there is no Eulerian walk or Eulerian circuit.8. Find an Eulerian walk in the graph at the top of the page.9. You can tell if a graph has an Eulerian walk or Eulerian circuit by trying to find one. But if youcan’t find one, how do you know if the graph really doesn’t have one, or if you just haven’t lookedhard enough yet? There is actually a way to know for sure. Figure this out yourself, or read it inthe blog cited above. Then explain the method here in your own words.ABCDEFG-4 -3 -2 -1 0 1 2 3 4 5-112345HIKJLPNMMinimum Spanning Tree and Kruskal’s AlgorithmRecall Kruskal’s algorithm for finding the minimum spanning tree in a graph with link costs. (Get thenotes from someone if you missed class.)10. Use Kruskal’s algorithm to find a minimum spanning tree for each of these graphs.a.b.