|
Section
|
Mathematics
|
|
Title
|
The graph of reflexive-transitive relations and the graph of finite topologies
|
|
Author(-s)
|
Al' Dzhabri Kh.Sh.ab
|
|
Affiliations
|
Udmurt State Universitya,
University of Al-Qadisiyahb
|
|
Abstract
|
Any binary relation $\sigma\subseteq X^2$ (where $X$ is an arbitrary set) generates on the set $X^2$ a characteristic function: if $(x,y)\in\sigma,$ then $\sigma(x,y)=1,$ otherwise $\sigma(x,y)=0.$ In terms of characteristic functions we introduce on the set of all binary relations of the set $X$ the concept of a binary reflexive relation of adjacency and determine an algebraic system consisting of all binary relations of the set and of all unordered pairs of various adjacent binary relations. If $X$ is a finite set then this algebraic system is a graph (“the graph of graphs’’).
It is shown that if $\sigma$ and $\tau$ are adjacent relations then $\sigma$ is a reflexive-transitive relation if and only if $\tau$ is a reflexive-transitive relation. Several structure features of the graph $G(X)$ of reflexive-transitive relations are investigated. In particular, if $X$ consists of $n$ elements, and $T_0(n)$ is the number of labeled $T_0$-topologies defined on the set $X,$ then the number of connected components is equal to $\sum_{m=1}^nS(n,m) T_0(m-1),$ where $S(n,m)$ are Stirling numbers of second kind. $($It is well known that the number of vertices in a graph $G(X)$ is equal to $\sum_{m=1}^nS(n,m) T_0(m).)$
|
|
Keywords
|
graph, reflexive-transitive relation, finite topology
|
|
UDC
|
519.175, 519.115.5
|
|
MSC
|
05C30
|
|
DOI
|
10.20537/vm150101
|
|
Received
|
12 November 2014
|
|
Language
|
Russian
|
|
Citation
|
Al' Dzhabri Kh.Sh. The graph of reflexive-transitive relations and the graph of finite topologies, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, vol. 25, issue 1, pp. 3-11.
|
|
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).
- Kolmogorov A.N., Fomin S.V. Elementy teorii funktsii i funktsional'nogo analiza (Elements of theory of functions and functional analysis), Moscow: Nauka, 1981, 544 p.
- Aigner M. Combinatorial theory, Berlin-Heidelberg-New York: Springer-Verlag, 1979, 492 p. Translated under the title Kombinatornaya teoriya, Moscow: Mir, 1982, 558 p.
- Ore O. Theory of graphs, Providence: Amer. Math. Soc. Colloq. Publ., 1962, vol. 18, 270 p. Translated under the title Teoriya grafov, Moscow: Nauka, 1980, 336 p.
- Harary F., Palmer E. Graphical enumeration, New York-London: Academic Press, 1973, 272 p. Translated under the title Perechislenie grafov, Moscow: Mir, 1977, 324 p.
- Comtet L. Recouvrements, bases de filtre et topologies d’un ensemble fini, C. R. Acad. Sci., 1966, vol. AB262, pp. A1091-A1094 (in French).
- Evans J.W., Harary F., Lynn M.S. On the computer enumeration of finite topologies, Comm. ACM, 1967, vol. 10, pp. 295-297.
- Gupta H. Number of topologies on a finite set, Res. Bull. Panjab. Univ. (N.S.), 1968, vol. 19, pp. 231-241.
|
|
Full text
|
|
+7 (3412) 91 60 92
Russian