Individual Homework: Graph Algorithms In class we discussed finding a minimum spanning tree in a network of nodes and link. A network of nodes and links is called a “graph” in computer science. I know you are thinking “graph” means something like � = �$, but this is something completely different, with the same name. A graph is literally a set of nodes and a set of links. Walking a graph A “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 directly from 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 circuit does not have any repeated nodes (other than the fact that the start and end are the 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önigsberg Leonhard Euler (pronounced “oiler”—it’s German, actually Swiss) came up with the concept of graphs when he was intrigued by a classical puzzle called the Bridges of Königsberg. You can read more about it on 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 “Eulerian circuit” 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 an Eulerian walk. (You can trace the nodes in that order without lifting your pencil.) On the other hand, in the small graph to the 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 you can’t find one, how do you know if the graph really doesn’t have one, or if you just haven’t looked hard enough yet? There is actually a way to know for sure. Figure this out yourself, or read it in the blog cited above. Then explain the method here in your own words. A B C D E F G -4 -3 -2 -1 0 1 2 3 4 5 -1 1 2 3 4 5 H I K J L P N M Minimum Spanning Tree and Kruskal’s Algorithm Recall Kruskal’s algorithm for finding the minimum spanning tree in a graph with link costs. (Get the notes from someone if you missed class.) 10. Use Kruskal’s algorithm to find a minimum spanning tree for each of these graphs. a. b.
Looking for solution of this Assignment?
WHY CHOOSE US?
We deliver quality original papers |
Our experts write quality original papers using academic databases.We dont use AI in our work. We refund your money if AI is detected |
Free revisions |
We offer our clients multiple free revisions just to ensure you get what you want. |
Discounted prices |
All our prices are discounted which makes it affordable to you. Use code FIRST15 to get your discount |
100% originality |
We deliver papers that are written from scratch to deliver 100% originality. Our papers are free from plagiarism and NO similarity.We have ZERO TOLERANCE TO USE OF AI |
On-time delivery |
We will deliver your paper on time even on short notice or short deadline, overnight essay or even an urgent essay |