18.2.3. Modeling Problems with Graphs

Try these first

1. 1.

   What is a vertex in graph theory?

   Hint

   Think of what a state or city might represent.

2. 2.

   What is graph coloring used for?

   Hint

   Consider how a map displays different regions.

3. 3.

   What must be true in a graph coloring situation?

   • Adjacent vertices can share the same color
   • Adjacent vertices cannot share the same color
   • No colors are required

   Hint

   Think about coloring a map.

4. 4.

   True or False: In a directed graph, if there is an edge from A to B, there must also be an edge from B to A.

   • True
   • False

   Hint

   Refer back to the airline situation.

5. 5.

   Given a graph with 6 vertices where each vertex is connected to all others, how many colors are necessary to color the graph without adjacent vertices sharing colors?

   Hint

   Consider the rules of graph coloring.

6. 6.

   Design a directed graph representing flight paths between 5 cities. Discuss the complexity of finding a route from one city to another.

   Hint

   Think about how you would travel from city A to city B.