18.1. Design and Analysis of Algorithms

Try these first

1. 1.

   Define a graph.

   Hint

   Think about basic definitions we discussed.

2. 2.

   What do you call the connections between vertices?

   Hint

   Remember the term starts with 'e'.

3. 3.

   What are the points called in a graph?

   • Edges
   • Colors
   • Vertices

   Hint

   Remember what we call the individual components of a graph.

4. 4.

   True or False: A graph can only be directed.

   • True
   • False

   Hint

   Recall our discussion on directed versus undirected graphs.

5. 5.

   Given a graph with 6 vertices and edges represented as pairs, devise a coloring strategy that minimizes colors while ensuring no two adjacent vertices are colored the same. How many colors are necessary?

   Hint

   Test smaller combinations first or visualize different setups.

6. 6.

   Design a directed graph representing a transport system among five cities. Identify potential bottlenecks based on graph analysis and suggest optimizations.

   Hint

   Think about which cities might be busy and require more connections.