Hamiltonian Circuits, Complete Graphs
Read the book chapters first, then make sure you can answer the questions in the notes. Following that, work on some skills-check problems and exercises. Then take the online quizzes.
- Reading
- 2.1
- Skills Check
- 1, 2, 5, 6, 7, 9, 13
- Exercises
- 1, 2, 3, 4, 7, 8, 14, 21, 26, 27, 28
- Quiz
- Take the quiz
2.1
- What circuit do we call a Hamiltonian Circuit?
- How do Hamiltonian Circuits differ from Euler Circuits?
- Do all graphs have Hamiltonian Circuits?
- Draw examples of graphs that have a HC but not a EC, as well as graphs that have a EC but not a HC.
- How many edges can we have in a Hamiltonian Circuit, in relation to the number of vertices in the graph?
- Examine the examples in Figure 2.2. How do we know for sure that these examples cannot have a Hamiltonian Circuit?
- The graph on Figure 2.2b shows an example of a graph with a “valid-2-coloring”: Each vertex is colored by one of two colors, in such a way that for every edge the two vertices corresponding to it have different colors.
- Show how the graph on figure 2.1a can also be valid-2-colored.
- When we can valid-2-color a graph, what condition would preclude such a graph from having a Hamiltonian Circuit?
- Can you provide examples of graphs that cannot possibly be valid-2-colored?
- Can you provide examples of graphs that cannot possibly be valid-3-colored?
- What graphs do we call complete graphs?
- Do complete graphs always have Hamiltonian Circuits?
- Do complete graphs always have Euler Circuits?
- If we add weights to each edge, what would be a minimum-cost Hamiltonian Circuit, and what would be a straightforward algorithm for finding such a circuit?
- What does the fundamental principle of counting say? What are some examples where we can apply it?
- In a complete graph on 5 vertices, how many different paths would the “method of trees” end up with?
- When applying the method of trees to find the minimum-cost Hamiltonian Circuit, we get multiple paths in the tree with the same cost. Why is that?