19.5. Naive Algorithm for Computing Connectivity Relation

Imagine you are given a relation R over a set which may or may not be finite. So, your R is a subset of A x A. And I define this relation R*, which I call as the connectivity relation and this is basically defined to be the union of different powers of your relation R.

The connectivity relation R* is a way to understand how elements in a set are related through paths. If you have a relation R, which can connect elements directly, the connectivity relation includes connections through multiple steps. Specifically, R* consists of all pairs of elements that can be reached by traversing from one element to another in the set, regardless of the number of steps or the length of the path.

Think of a city map where roads connect various locations. If there is a direct road (relation) from location A to B (R), R* would include all locations you can reach from A, even if it requires going through other locations C and D. Essentially, R* captures all possible routes you can take to get from A to other locations.

It turns out that, as per my definition of R*, an element, a_i will be related to a in this relation R* provided there exists some path of any length from a_i to a, in the directed graph of your relation R.

In the context of the connectivity relation R*, the length of the path taken to connect two elements does not matter. So long as there is a way (a series of connections) to get from one element to the other in the directed graph representation of the relation R, those two elements will be considered related in R*. The crucial part is establishing that a path exists; the specifics of how long or convoluted that path is are irrelevant.

Imagine trying to get from one friend to another through a series of mutual friends. If you can find a sequence of friends who can introduce you to the target friend, you will reach them, regardless of how many intermediaries exist. As long as the connection exists, the actual number of introductions or the complexity of getting there doesn’t change the end result.

My claim here is that R* is nothing but the union of R, R² and up to Rⁿ because you do not need to take the union of higher powers of R. Any higher powers of R will be subsumed in the union of the first n powers of R.

When considering a finite set with n elements, we only need to look at paths made up of these n elements. The maximum unique path we can have (where no element is used more than once) can only be of length n, since there are only n distinct nodes. Therefore, any higher path combinations will essentially loop back and can already be represented by paths of length n or less. This means when calculating the connectivity relation, we can limit our focus to these first n powers of the relation R.

Consider you have a group of friends (n friends) and you can only introduce two friends to each other directly. After a certain number of introductions (paths), introducing a friend already known to another friend will only retrace steps already made. Therefore, focusing on unique introductions becomes unnecessary once every possible pair has been introduced.

Now we will see a relationship between the transitive closure and the connectivity relationship. ... The transitive closure of your relation R is nothing but the connectivity relation.

The transitive closure and the connectivity relation effectively describe the same concept: they both determine whether a direct or indirect relationship exists between elements. To prove this, it's shown that adding edges (direct relationships) in a way that maintains transitivity results in a graph that encompasses the same connections defined by the connectivity relation R*. Thus, both approaches yield the same outcome regarding connectedness.

Think about a network of friendships where knowing someone means you can reach out to their friends. The transitive closure would mean if you know a friend of a friend, you might be introduced to them, effectively making you all connected. Therefore, both connection methods (via direct and indirect relationships) lead to the same understanding of who is connected to whom.

So, we will be focusing on the case when the relation is over a finite set. ... Here is the naive algorithm for computing the matrix for connectivity relation.

For computing the connectivity relation, we can create a Boolean matrix that represents connections in a finite set. Starting with the matrix of the original relation, we will multiply it to get the next powers of R and keep track of these. Then, we find connections in any of these powers similar to previous points. This allows construction of the final connectivity matrix that gives us complete visibility into how elements relate to each other across the entire series of potential paths.

This process is like building a web of connections at a networking event. Initially, you might connect with a few people. As the event progresses and you introduce multiple connections, you're building out the network. By following how these connections evolve among attendees, you'd eventually develop an understanding of who knows whom, just like constructing your connectivity relation.

--