|
Section
|
Mathematics
|
|
Title
|
The graph of acyclic digraphs
|
|
Author(-s)
|
Al' Dzhabri Kh.Sh.ab,
Rodionov V.I.b
|
|
Affiliations
|
University of Al-Qadisiyaha,
Udmurt State Universityb
|
|
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
|
|
UDC
|
519.175, 519.115
|
|
MSC
|
05C30
|
|
DOI
|
10.20537/vm150401
|
|
Received
|
23 October 2015
|
|
Language
|
Russian
|
|
Citation
|
Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of acyclic digraphs, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, vol. 25, issue 4, pp. 441-452.
|
|
References
|
- Al' Dzhabri Kh.Sh., Rodionov V.I. The graph of partial orders, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 4, pp. 3-12 (in Russian).
- Al' Dzhabri Kh.Sh. The graph of reflexive-transitive relations and the graph of finite topologies, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2015, vol. 25, no. 1, pp. 3-11 (in Russian).
- Liskovets V.A. On the number of maximal vertices of a random acyclic digraph, Theory Probab. Appl., 1976, vol. 20, no. 2, pp. 401-409.
- Rodionov V.I. On the number of labeled acyclic digraphs, Discrete Mathematics, 1992, vol. 105, pp. 319-321.
|
|
Full text
|
|
+7 (3412) 91 60 92
Russian