|
Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, Volume 25, Issue 4, Pages 441–452
(Mi vuu498)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
MATHEMATICS
The graph of acyclic digraphs
Kh. Sh. Al' Dzhabriab, V. I. Rodionovb a University of Al-Qadisiyah, ul. Babilon, 29, Al Diwaniyah, Iraq
b Udmurt State University, ul. Universitetskaya, 1, Izhevsk, 426034, Russia
Abstract:
The paper introduces the concept of a binary reflexive relation of adjacency on the set of all binary relations of a set $X$ (in terms of characteristic functions) and determines an algebraic system consisting of all binary relations of the set and of all unordered pairs of adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs”). It is proved that the diameter of a graph of binary relations is 2. It is shown that if $\sigma$ and $\tau$ are adjacent relations, then $\sigma$ is an acyclic relation (finite acyclic digraph) if and only if $\tau$ is an acyclic relation. An explicit formula for the number of connected components of a graph of acyclic relations is received.
Keywords:
binary relation, acyclic digraph.
Received: 23.10.2015
Citation:
Kh. Sh. Al' Dzhabri, V. I. Rodionov, “The graph of acyclic digraphs”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 25:4 (2015), 441–452
Linking options:
https://www.mathnet.ru/eng/vuu498 https://www.mathnet.ru/eng/vuu/v25/i4/p441
|
Statistics & downloads: |
Abstract page: | 461 | Full-text PDF : | 164 | References: | 66 |
|