19.5. Naive Algorithm for Computing Connectivity Relation

Try these first

1. 1.

   What is a connectivity relation?

   Hint

   Consider a directed graph.

2. 2.

   How do you calculate R^n?

   Hint

   Think about the definition of matrix multiplication.

3. 3.

   What is the main purpose of the connectivity relation?

   • To show direct relationships only
   • To indicate possible paths between elements
   • To count elements in a set

   Hint

   Think about what 'connectivity' means.

4. 4.

   The naive algorithm has a computational complexity of ...

   • True
   • False

   Hint

   Recall the steps of the algorithm.

5. 5.

   Given a directed graph representing friendships among students, construct the connectivity relation of the graph. Show how many levels of friendship exist between every two nodes.

   Hint

   Visualize paths in the directed graph.

6. 6.

   Discuss how an optimized algorithm could improve the computation of connectivity relations. What changes would you propose?

   Hint

   Research alternatives that directly improve the performance.