аспирант
graduate student
В статье рассмотрены свойства матрицы относительной лесной доступности ориентированного цикла и ориентированного пути.Во введении представлена история вопроса, дан обзор основных идей и результатов работы.Во втором разделе собраны основные понятия теории графов, и дано ”графовое“ представление матрицы относительной лесной доступности орграфа Γ: F =(((𝑓𝑖𝑗))𝑛×𝑛)/𝑓 , 𝑖, 𝑗 = 1 . . . 𝑛, где 𝑓𝑖𝑗 – количество остовных сходящихся корневых лесов орграфа Γ, в которых вершины 𝑖 и 𝑗 принадлежат одному дереву, сходящемуся к 𝑗, а 𝑓 – общее количество остовных cходящихся корневых лесов орграфа Γ.В третьем разделе рассмотрены вопросы построения и исследования матрицы относительной лесной доступности ориентированного пути 𝑃𝑛, 𝑛 ≥ 2. Рассмотрены примеры построения матрицы относительной лесной доступности ориентированного пути для малых значений 𝑛. Приведены иллюстрации ”графовой“ процедуры построения матрицы F. Доказано, что матрица относительной лесной доступности ориентированного пути 𝑃𝑛, 𝑛 ≥ 2, связана с последовательностью 1, 2, 4, 8, 16, ..., 2𝑛, ... степеней числа 2. Другими словами, элементы 𝑓𝑖𝑗 , формирующие матрицу, представляют собой элементы множества {1, 2, 22, ..., 2𝑛−1}, заполняющие столбцы матрицы: первый столбец состоит из последовательно убывающих чисел 2𝑛−1, ..., 2, 1; второй столбец, начинаясь с 0, содержит на втором месте (пересечение с главной диагональю) число 2𝑛−2, в то время как следующие элементы представляют собой последовательно убывающие числа 2𝑛−3, ..., 2, 1; третий столбец, содержащий нули на двух позициях, расположенных над главной диагональю, содержит на третьем месте (пересечение с главной диагональю) число 2𝑛−2, в то время как следующие элементы представляют собой последовательно убывающие числа 2𝑛−3, ..., 2, и т.д.Величина 𝑓 равна 2𝑛−1.В четвертом разделе аналогичные рассуждения проведены для матрицы относительной лесной доступности для ориентированного цикла 𝐶𝑛, 𝑛 ≥ 3.В заключении подведены итоги работы.
In this paper we consider the properties of the matrix of relative forest accessibility of the oriented cycle and the properties of the matrix of relative forest accessibility of the oriented path.The introduction contains the history of the problem and provides an overview of the main ideas and results presented in the article.The second section gives basic concepts of the graph theory and a ”graphical“ representation of the matrix of relative forest accessibility of the digraph Γ: F =(((𝑓𝑖𝑗))nxn)/𝑓 , 𝑖, 𝑗 = 1 . . . 𝑛, where 𝑓𝑖𝑗 is the number of spanning converging rooted forests of the digraph Γ, in which the vertices 𝑖 and 𝑗 belong to the same tree converging to 𝑗, and 𝑓 is the total number spanning converging rooted forests of the digraph Γ.The third section deals with the construction and research of the matrix of relative forest accessibility of the oriented path 𝑃𝑛, 𝑛 ≥ 2. Examples of constructing the matrix of relative forest accessibility of oriented path for small values of 𝑛 are considered. Illustrations of the ”graphical“ procedure of building the matrix F are given. It is proved that the matrix of relative forest accessibility for the directed path 𝑃𝑛, 𝑛 ≥ 2, is related to the sequence 1, 2, 4, 8, 16, ..., 2𝑛, ... of powers of 2. In other words, the elements of 𝑓𝑖𝑗 that form the matrix are elements of the set{1, 2, 22, ..., 2𝑛−1} filling the columns of the matrix: the first column consists of sequentially decreasing numbers 2𝑛−1, ..., 2, 1; the second column, starting at 0, contains in the secondplace (the intersection with the main diagonal) the number 2𝑛−2, while the following elements are consecutively decreasing numbers 2𝑛−3, ..., 2, 1; the third column, containing zeros in twopositions above the main diagonal, contains in the third place (the intersection with the main diagonal) the number 2𝑛−2, while the following elements are sequentially decreasing numbers2𝑛−3, ..., 2, etc. The value of 𝑓 is equal to 2𝑛−1.In the fourth section, similar considerations for matrix of relative forest accessibility of the oriented cycle 𝐶𝑛, 𝑛 ≥ 3, are represented.In the conclusion, the results of the work are summed up.
The authors declare that there are no conflicts of interest present.