Rossen: How to perform Composition on Directed Graph.

Question

Given the directed graphs representing two relations, how can the directed graph of the union, intersection, symmetric difference, difference, and composition of these relations be found?

As, we can easily find, union, intersection, difference and symmetric difference. But how we can find composition of directed graph.

There is a ref:- https://math.stackexchange.com/questions/239897/draw-the-composition-of-directed-graphs

But not explained clearly.

Answer 1

Given R and S relations , the composition R o S is defined as :

R o S  =   { (x,z)  |  (x,y)  ∈  S  and  (y,z)  ∈  R }

 So for the two directed graphs , we can write equivalent R and S relations whose pairs are the edges in R and S respectively..Having written the R and S relations , we can do the composition R o S as mentioned above and obtain the resultant graph.

This way composition of graphs is done.

Comments

Composition may be performed for the same graph as well.

U might have come across R² , R³ in Floyd Warshall's algo .

Here R² is nothing but :   R o R  (composition of R with R)

---

thanks @Habibkhan Sir!!

---

@Shubhanshu is there any way to directly find the directed graph for union/intersection/set-diff of two relations by seeing the graphs of individual relations, without making the ordered pairs?