19.1. Introduction to Connectivity Relation

Try these first

1. 1.

   Define the term 'connectivity relation'.

   Hint

   Consider the concept of paths between nodes in a graph.

2. 2.

   What does the notation R* represent?

   Hint

   Think about how we represent unions of relations.

3. 3.

   What does the connectivity relation R* represent?

   • It's a direct relationship
   • It's the union of powers of R
   • It only includes pairs in R

   Hint

   Consider the definition of union in set theory.

4. 4.

   True or False: The transitive closure is a type of connectivity relation.

   • True
   • False

   Hint

   Think about how transitive properties influence connectivity.

5. 5.

   Consider a directed graph with five vertices where paths exist in such a way that a connects to b, b connects to c, and c connects back to a. Define the connectivity relation and explain your reasoning.

   Hint

   Try drawing the graph to visualize the connections.

6. 6.

   Using a Boolean matrix, how would you represent the following relation R: {(1,2),(2,3),(3,1)}? Demonstrate computing R*.

   Hint

   Include all paths when performing Boolean products for each power.