Enumeration of connected components of acyclic digraph

Abstract

We established the concept of a binary reflexive relation of adjacency and determined the algebraic system consisting of all binary relations of set X and all unordered pairs of binary relations in terms of characteristic functions on the set of all binary relations of the set X. We investigated some properties of algebraic system of the structure of acyclic digraph. Also, we prove that if σ and τ are adjacent relations, then σ is acyclic relation (finite acyclic digraph) if and only if τ is an acyclic relation. Finally, the number of connected components of an acyclic relations graph is given an exact formula.

Subject Classification: (2010):

• 05C30

Keywords:

• Graph
• Binary relation
• Acyclic digraphs