Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PartialOrderGraphQ

Source Notebook

Test whether a graph is a partial order, that is, reflexive, antisymmetric and transitive

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

ResourceFunction["PartialOrderGraphQ"][g]

yields True if the binary relation defined by edges of the graph g is a partial order and False otherwise.

Details and Options

The binary relation defined by edges of the graph is a partial order if it is transitive, reflexive and antisymmetric.

Examples

Basic Examples (2) 

The graph representing the divisibility relation between integers is partial order since the relation is reflexive (each integer divides itself), antisymmetric (n cannot divide m if n>m) and transitive (as n|m implies m=kn for some integer k, so m|l implies n|l):

In[1]:=
RelationGraph[(Mod[#1, #2] == 0) &, Range[8], VertexLabels -> "Name"]
Out[1]=
In[2]:=
ResourceFunction["PartialOrderGraphQ"][%]
Out[2]=

A graph formed by selecting ordered tuples is a partial order:

In[3]:=
tuples = Tuples[CharacterRange["a", "e"], 2]
Out[3]=
In[4]:=
Graph[DirectedEdge @@@ Select[tuples, OrderedQ]]
Out[4]=
In[5]:=
ResourceFunction["PartialOrderGraphQ"][%]
Out[5]=

On the other hand, a similar graph constructed from the symmetric set of the tuples is not:

In[6]:=
Graph[DirectedEdge @@@ tuples]
Out[6]=
In[7]:=
ResourceFunction["PartialOrderGraphQ"][%]
Out[7]=

Version History

  • 1.0.0 – 01 July 2020

Related Resources

License Information