Skip to content

What is Closures of Relations? ​

  • A relation R on a set A, it may or may not have some property P (e.g. relfexive, symmetric, antisymmetric, etc.)

Definition

A relation S, if exists, satisfies the following conditions:

  • R ⊆ S
  • S has property P
  • S is the smallest relation containing R with property P

We call S is closure of R

Reflexive closure ​

TIP

We have a diagonal relation Δ on a set A,

Δ={(a,a) | a∈A}

A reflexive relation S of relation R on a set A,

S=R∪Δ

Example ​

Set A={1,2,3}

The relation R={(1,1),(1,2),(2,1),(3,2)} on the set A is not reflexive

We have a diagonal relation Δ on set A,

Δ={(2,2),(3,3)}

The reflexive closure of R is,

S=R∪Δ={(1,1),(1,2),(2,1),(3,2),(2,2),(3,3)}

Symmetric closure ​

TIP

A symmetric relation S of relation R on a set A,

S=R∪R−1

Example ​

Set A={1,2,3}

The relation R={(1,1),(1,2),(2,2),(2,3),(3,1),(3,2)} on the set A is not symmetric

We have an inverse relation R−1 on set A,

R−1={(2,1),(1,3)}

The symmetric closure of R is,

S=R∪R−1={(1,1),(1,2),(2,2),(2,3),(3,1),(3,2),(2,1),(1,3)}

Transitive closure ​

Theorem Path và Relation Power ​

INFO

Given a relation R on set A

There is a path of length n from a to b, iff

(a,b)∈Rn
  • Intuition
    • R: đi được trong 1 bước
    • R2: đi được trong 2 bước
    • R3: đi được trong 3 bước
    • ...
    • Rn: đi được trong đúng n bước

Connectivity relation R∗ ​

INFO

  • Let R be a relation on a set A.
  • The connectivity relation R∗ consists of the pairs (a, b) such that there is a path of length at least one from a to b in R
  • In other words,
R∗=R1∪R2⋯∪R∞=⋃n=1∞Rn
  • R∗ tells us there exists a path from a to b. (Reachable)

TIP

A Transitive relation S of relation R on a set A,

S=R∗

Efficient ways to find transitive closure ​

WARNING

  • The n in the previous section is the length of the path and leads to infinity (∞).

Lemma 1 ​

INFO

If there is a path from (a) to (b), then there exists a path whose length is at most n.

Moreover, if a≠b, then there exists a path of length is at most n - 1

  • From Lemma 1, we see that the transitive closure of R is the union of R, R2, R3, ⋯Rn

TIP

n is the number of elements in the set A

Transitive closure for the zero–one matrix ​

Theorem 3

  • Let MR be the zero–one matrix of the relation R on a set with n elements. Then the zero–one matrix of the transitive closure R∗ is
MR∗=MR∪MR2⋯MRn
  • Note that this is a Boolean multiplication

Warshall’s Algorithm ​

Details

Warshall does NOT build paths by length.

Instead, it builds reachability by:

gradually allowing more intermediate vertices.

Interior Vertices ​

For a path:

a,x1,x2,…,xm−1,b

the interior vertices are:

x1,x2,…,xm−1

TIP

That is: all vertices except the first and last

Definition of Wk ​

Warshall constructs matrices:

W0,W1,…,Wn

where:

Wk=[wij[k]]

and when:

wij[k]=1

iff there exists a path from:

vi→vj

such that all interior vertices belong to:

{v1,v2,…,vk}

Important Interpretation

At step (k):

we are allowed to use only

v1,…,vk

as intermediate vertices.

Lemma 2 — The Core Recurrence ​

wij[k]=wij[k−1]∨(wik[k−1]∧wkj[k−1])
  • Meaning that, a path from vi→vj, exists at step k if:
Case 1 — Existing Path ​

The path already existed before:

wij[k−1]=1
Case 2 — Path Through vk ​

There exists:

vi→vk

and:

vk→vj

using only:

v1,…,vk−1

as intermediate vertices.

Practical Implementation O(n3) ​
text
for k = 1 to n
    for i = 1 to n
        for j = 1 to n
            W[i][j] =
            W[i][j] OR
            (W[i][k] AND W[k][j])

Built with ❤️ and curiosity