22.3.1. Acyclic Graphs and Trees

Try these first

1. 1.

   Define a graph in your own words.

   Hint

   Think about how you’d represent connections visually.

2. 2.

   What does BFS stand for?

   Hint

   Remember how BFS explores levels in a graph.

3. 3.

   What does a tree always have in relation to its vertices?

   • n+1 edges
   • n-1 edges
   • n edges

   Hint

   Think about the definition of a tree.

4. 4.

   A graph is disconnected if...

   • True
   • False

   Hint

   Visualize paths in a city.

5. 5.

   Given a directed graph with vertices 1-7 and edges denoting connections between them, list the edges that could represent forward, backward, or cross edges if shown in a DFS traversal.

   Hint

   Remember the definitions of each edge type when visualizing.

6. 6.

   Construct a scenario where a directed graph represents course prerequisites for a major. Discuss how you would ensure that the graph remains acyclic.

   Hint

   Think about the logical flow of courses required for degree completion.