|
Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, Volume 25, Issue 1, Pages 3–11
(Mi vuu459)
|
|
|
|
This article is cited in 6 scientific papers (total in 6 papers)
MATHEMATICS
The graph of reflexive-transitive relations and the graph of finite topologies
Kh. Sh. Al' Dzhabriab a Udmurt State University, ul. Universitetskaya, 1, Izhevsk, 426034, Russia
b University of Al-Qadisiyah, ul. Babilon, 29, Al Diwaniyah, Iraq
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.
Received: 12.11.2014
Citation:
Kh. Sh. Al' Dzhabri, “The graph of reflexive-transitive relations and the graph of finite topologies”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 25:1 (2015), 3–11
Linking options:
https://www.mathnet.ru/eng/vuu459 https://www.mathnet.ru/eng/vuu/v25/i1/p3
|
Statistics & downloads: |
Abstract page: | 460 | Full-text PDF : | 205 | References: | 70 |
|