доктор педагогических наук, кандидат физико-математическихнаук, доцент
doctor of pedagogical sciences, candidate of physical and mathematical sciences, associate professor
аспирант
graduate student
В статье рассмотрены вопросы перечисления некоторых графов специального вида.Именно, доказан ряд новых результатов о числе остовных деревьев и остовных лесов графов, играющих важную роль в прикладных задачах теории информации. Во-первых, рассмотрены свойства остовных сходящихся лесов ориентированных графов, участвующих в построении квазиметрики среднего времени первого прохода – обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова. Во-вторых,изучены характеристики остовных корневых лесов и остовных сходящихся лесов неориентированных и ориентированных графов, необходимых для построения матрицы относительной лесной доступности – одной из мер близости вершин графовых структур, играющей важную роль при решении прикладных задач. Рассуждения проведены на основе нескольких простейших графовых моделей, в том числе на базе простого цикла, простого пути и их ориентированных аналогов.В первом разделе (введении) представлена история вопроса, дан обзор основных идей и результатов работы. Рассмотрена роль графовых моделей в представлении и исследовании эргодических однородных цепей Маркова – последовательностей случайных событий с конечным или счетным числом исходов, характеризующихся тем, что распределение вероятностей параметров процесса в следующий момент времени зависит только от параметровпроцесса в предыдущий момент. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги – переходам между ними. С другой стороны, любой связный граф (ориентированный граф) может служить базой для построения модели простейшей цепи Маркова: если вершина 𝑖 имеет степень (полустепень исхода) 𝑘, то все выходящие из нее ребра превращаются в дуги с весами 1/𝑘 . Дано определение и раскрыта роль матрицы относительной лесной доступности неориентированных и ориентированных графов для решенияприкладных задач теории информации.Во втором разделе собраны базовые определения теории графов, необходимые для формулировки и доказательства основных результатов работы. Дано определение графа иориентированного графа, остовного подграфа, остовного корневого леса (для неориентированных графов) и остовного сходящегося леса (для ориентированных графов). Приведеныпримеры.В третьем разделе дано определение чисел Фибоначчи, сформулирован и доказан ряд свойств чисел Фибоначчи, необходимых для получения основных результатов статьи вслучае неориентированных пути и цикла.В четвертом разделе доказаны две теоремы о перечислении графов, связанных с построением матрицы среднего времени первого прохода для однородной эргодической цепи Маркова. Именно, найдено количество остовных сходящихся деревьев для ориентированного пути и цикла и остовных корневых деревьев для неориентированного пути и цикла;произведен подсчет остовных лесов, состоящих из двух деревьев, для тех же графовых структур. Результаты, связанные с ориентированным случаем, сформулированы в терминах величин 2/𝑘, 𝑘 ≥ 0; результаты для неориентированного случая сформулированы втерминах чисел Фибоначчи 𝑢𝑘, 𝑘 ≥ 1. Доказательства проведены на базе элементарных методов перечислительной комбинаторики.В пятом разделе представлены результаты, связанные с перечислением остовных лесов, необходимых для построения матрицы относительной лесной доступности неориентированного пути и цикла и их ориентированных аналогов. Найдено общее количество остовных сходящихся лесов для ориентированного пути и цикла и остовных корневых лесов для неориентированного пути и цикла; произведен подсчет остовных сходящихся лесов, в которых вершина 𝑖 принадлежит дереву, сходящемуся к 𝑗 в ориентированном пути и цикле, и остовных корневых лесов, в которых вершина 𝑖 принадлежит дереву с корнем 𝑗 в неориентированном пути и цикле. Как и ранее, результаты, связанные с ориентированным случаем, сформулированы в терминах величин 2𝑘, 𝑘 ≥ 0; результаты для неориентированного случая сформулированы в терминах чисел Фибоначчи 𝑢𝑘, 𝑘 ≥ 1.В шестом разделе (заключении) приведены основные выводы работы, намечены результаты дальнейших исследований.
In this article we consider questions of graph enumeration for some graphs of a special form.In fact, a number of new results have been proved on the number of spanning trees and spanning forests of graphs that play an important role in the applied problems of Information Theory.On the one hand, the properties of the spanning converging forests of oriented graphs involved in the construction of the mean first passage time quasi-metric, a generalized metric structure closely related to ergodic homogeneous Markov chains, are considered. On the other hand, the characteristics of spanning rooted forests and spanning converging forests of non-oriented and oriented graphs needed for the construction of a matrix of relative connectivity via forests, one of the measures of proximity of the vertices of graph structures, which plays an important role in solving of applied problems, have been studied. The consideration is based on several simple graph models, including a simple cycle, a simple path and their oriented analogues.The first section (introduction) presents the history of the problem and provides an overview of the main ideas and results presented in the article. The role of graph models in thepresentation and study of ergodic homogeneous Markov chains is considered. In fact, a Markov chain is a mathematical model of some random process describing a sequence of possible eventsin which the probability of each event depends only on the state attained in the previous event.The Markov chain can be depicted as an oriented weighted graph of transitions whose vertices correspond to the states of the chain and the arcs correspond to the transitions between them.On the other hand, any connected graph can be used as a basis for building a model of the simplest Markov chain: if a vertex 𝑖 has degree 𝑘, all incident edges are converted into arcswith the weights 1/𝑘 . The matrix of relative connectivity via forests for non-oriented and oriented graphs is defined; its role for solving important applied problems of Information Theory isdisclosed.The second section contains the basic definitions of Graph Theory necessary to formulate and prove the main results of the article. The definitions of a graph and an oriented graph, aspanning subgraph, a spanning rooted forest (for non-orentied graphs) and a spanning converging forest (for oriented graphs) are given. Some examples are represented.In the third section, the definition of Fibonacci numbers is given, a number of properties of Fibonacci numbers necessary to obtain the main results of the article for undirected paths andcycles are formulated and proved.In the fourth section, two theorems on the enumeration of graphs related to the construction of the mean first passage time matrix for a homogeneous ergodic Markov chain are proved. Infact, the number of spanning converging trees for the oriented path and the oriented cycle and the number of spanning rooted trees for the non-oriented path and the non-oriented cycle aregiven; the spanning forests consisting of two trees for the same graph structures are counted.Results for the oriented case are formulated in terms of values 2𝑘, 𝑘 ≥ 0; results for the nonoriented case are formulated in terms of Fibonacci numbers 𝑢𝑘, 𝑘 ≥ 1. The proofs are based onelementary methods of enumerating Combinatorics.The fifth section presents the results related to enumeration of spanning forests needed for construction of the matrix of relative connectivity via forests for the non-oriented paths andcycles and their oriented analogues. Total number of spanning converging forests (for oriented paths and cycles) and total number of spanning rooted forests (for non-oriented paths andcycles) are found; enumeration of the spanning converging forests, in which a vertex 𝑖 belongs to a tree converging to a vertex 𝑗 (for the oriented paths and cycles), and enumeration of the spanning rooted forests, in which a vertex 𝑖 belongs to a tree with a root 𝑗 (for the non-oriented paths and cycles) are represented. As before, results for the oriented case are formulated in terms of values 2𝑘, 𝑘 ≥ 0; results for the non-oriented case are formulated in terms of Fibonaccinumbers 𝑢𝑘, 𝑘 ≥ 1. The sixth section (conclusion) presents the main conclusions of the article, outlines the ideas of further studies.
The authors declare that there are no conflicts of interest present.