19.4. Significance of Connectivity Relationship

So, let me start by introducing the connectivity relation. So, 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. It turns out that, as per my definition of R*, an element, a_i will be related to a_j in this relation R* provided there exists some path of any length from a_i to a_j in the directed graph of your relation R.

The Connectivity Relation, R*, is defined based on a given relation R which connects elements from a set. It is the union of all possible powers of R, meaning R* captures all pairs of elements that are indirectly connected through any path in the graph representation of R, regardless of how many steps that path takes. In simpler terms, if you can get from one element to another by following the connections provided in R, then those two elements are considered related in R*.

Imagine you are in a city represented as a graph where intersections are nodes and roads are edges. The relation R describes direct roads between intersections. If there exists a path through several intersections leading from Intersection A to Intersection B, then A and B are considered connected via the connectivity relation R*. This is much like finding a route on a map, showing that even if there’s no direct road, you can travel between A and B.

It might be possible that (a, a) is also present in say some other power of R. That means, as per the same statement there exists a path of length k from the node a to a.

In the context of the connectivity relation R*, if element a is related to itself via R*, it indicates that there is a path from a to a (essentially a loop) in the graph derived from relation R. This path can be of various lengths (could be 1 for a direct relationship or longer through indirect connections), but what is crucial is that at least one path exists connecting a back to itself.

Consider the example of a social network. If person A can reach out to person A through several mutual friends, it shows that even through twists and turns in the network, there is still a way to connect back to oneself. This could be through one mutual connection or several, demonstrating that connectivity is unaffected by how long the route is, as long as it exists.

My claim here is that R* is nothing but the union of R, R^2 and up to R^n because you do not need to take the union of higher powers of R.

This claim posits that in a graph with n distinct nodes, there can't be a path longer than n that utilizes distinct edges, because passing through the same node or edge implies returning to an already traversed route, which does not create a 'new' connection. Hence, analyzing powers of R from 1 to n suffices to determine all possible connections represented in R* without needing higher powers.

Imagine a party where 10 people can each introduce themselves to others. If everyone has introduced themselves to everyone else, after 10 introduction steps, you can't form any new recent acquaintances without revisiting previous introductions. Therefore, knowing the connections established from 1 to 10 effectively covers all possibilities of introductions without needing to extend further.

So, now what we are going to prove here is now we are going to see a relationship between the transitive closure and the connectivity relationship.

The transitive closure of a relation R is defined as the smallest transitive relation that contains R. The connectivity relation R* essentially provides this closure; it encapsulates all connections directly derived from R including all possible indirect relations through various paths. Thus, R* satisfies all conditions required for being the transitive closure of R.

Think of a family tree where a parent is related to their child, and each subsequent generation can also be connected. The connectivity relation here shows that if person A is the parent of person B, then A is related to B. If B has children, A is still connected to those children through B, demonstrating that knowing R (parental relationships) allows you to deduce all possible familial connections through indirect relationships.

So, this connectivity relationship has got a huge amount of significance. Now the question is how we algorithmically compute this connectivity relationship.

Having established the importance of the connectivity relationship, the next natural question is how to efficiently compute it. We can represent the relations using a Boolean matrix where entries indicate whether two elements are directly related. By performing Boolean matrix multiplication, we can derive higher powers and subsequently determine the connectivity relationship encompassing all possible paths between elements.

Envision a city transit map illustrated as a matrix where intersections are rows and columns. Each entry indicates direct transit routes between intersections. If you can compute transit times between routes, you can then derive the quickest paths effectively using matrix operations, similar to how territory is interconnected in networked systems.

--