18.2.7. Finding a Route in Directed and Undirected Graphs

Try these first

1. 1.

   What are the two main components of a graph?

   Hint

   Think about what connects the points in a graph.

2. 2.

   Define what a vertex is.

   Hint

   What do we call the points on a map?

3. 3.

   What are the two main types of graphs we discussed?

   • Directed and Undirected
   • Circles and Triangles
   • Colored and Non-colored

   Hint

   Recall the types mentioned during our discussions.

4. 4.

   True or False: Every map can be colored using just two colors.

   • True
   • False

   Hint

   Think about the complexity of borders in different regions.

5. 5.

   You have a directed graph where cities A, B, and C are connected as follows: A to B, B to C, but not A to C. You want to travel from A to C. Is it possible, and why?

   Hint

   Consider the direction of each connection.

6. 6.

   In a political map with states represented as vertices, find a sequence of coloring with five colors that represents the same map, but shows that four colors are still sufficient. Which are the states that could share colors and why?

   Hint

   Visualize states and their borders on a map.