Function Repository Resource:

TransitiveGraphQ

Test whether the binary relation defined by edges of a graph is transitive

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["TransitiveGraphQ"][g]

yields True if the graph g is transitive and False otherwise.

Details and Options

ResourceFunction["TransitiveGraphQ"][g] returns True if the binary relation defined by edges of the graph g is transitive.

A directed graph formed by tuples is transitive:

In[1]:=

Out[1]=

In[2]:=

Out[2]=

In[3]:=

Out[3]=

But the undirected graph formed by the same tuples is not:

In[4]:=

Out[4]=

In[5]:=

Out[5]=

The divisibility relation between integers is transitive since n|m implies m=kn for some integer k, so m|l implies n|l:

In[6]:=

Out[6]=

In[7]:=

Out[7]=