Processing math: 100%

Об опорных множествах ациклических и транзитивных ориентированных графов

 pdf (245K)

В предыдущих работах авторов на множестве всех бинарных отношений множества X введено понятие бинарного рефлексивного отношения смежности и определена алгебраическая система, состоящая из всех бинарных отношений множества X и из всех неупорядоченных пар смежных бинарных отношений. Если X - конечное множество, то эта алгебраическая система - граф (граф бинарных отношений G). В настоящей работе для ациклических и транзитивных орграфов вводится понятие опорного множества: это совокупности S(σ) и S(σ), состоящие из вершин орграфа σG, имеющих нулевую полустепень захода и исхода соответственно. Доказано, что если Gσ - связная компонента графа G, содержащая ациклический или транзитивный орграф σG, то {S(τ):τGσ}={S(τ):τGσ}. Получена формула для числа транзитивных орграфов, имеющих фиксированное опорное множество. Аналогичная формула для числа ациклических орграфов, имеющих фиксированное опорное множество, получена авторами ранее.

Ключевые слова: перечисление графов, ациклический орграф, транзитивный орграф
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2017, т. 27, вып. 2, с. 153-161
DOI: 10.20537/vm170201

On support sets of acyclic and transitive digraphs

In previous works of the authors, the concept of a binary reflexive adjacency relation was introduced on the set of all binary relations of the set X, and an algebraic system consisting of all binary relations of the set X and of all unordered pairs of adjacent binary relations was defined. If X is a finite set, then this algebraic system is a graph (graph of binary relations G). The current paper introduces the notion of a support set for acyclic and transitive digraphs. This is the collections S(σ) and S(σ) consisting of the vertices of the digraph σG that have zero indegree and zero outdegree, respectively. It is proved that if Gσ is a connected component of the graph G containing the acyclic or transitive digraph σG, then {S(τ):τGσ}={S(τ):τGσ}. A formula for the number of transitive digraphs having a fixed support set is obtained. An analogous formula for the number of acyclic digraphs having a fixed support set was obtained by the authors earlier.

Keywords: enumeration of graphs, acyclic digraph, transitive digraph
Citation in English: Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2017, vol. 27, issue 2, pp. 153-161

Журнал индексируется в Web of Science (Emerging Sources Citation Index)

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref