一些有向图的生成树计数研究
摘要
图的生成树计数是图论中的一个重要分支，对图论的相关研究也有着至关重要的作
用，例如复杂网络、随机游走、图的结构分析等方面。随着生成树计数问题的应用领域
逐渐拓宽，人们发现在随机游走和网络控制系统等领域中，有向图中比无向图更具有研
究意义。诸多事实也告诉我们对各类递推构造的图或有向图的运算图生成树的研究，可
以为网络的设计提供重要的理论依据。因此，有向图的生成树计数研究是一项基础且有
意义的工作。
本文介绍了一些加权有向图的运算图的定义，将许多在无向图背景下的图运算的定
义推广到有向图当中。通过分析图运算所生成的合成图的顶点加权Laplacian矩阵和
R
Schur补矩阵给出了有向剖分图、有向图、有向Join图和有向Corona图等顶点加权有
向图的有根生成树计数公式。特别地，当有向图的顶点和有向边权值都为1时，得到了
通过图运算所生成的合成图的有根生成树计数公式。
关键词：生成树；有向图；Laplacian矩阵
一些有向图的生成树计数研究
ABSTRACT
Asanimportantbranchofgraphtheory,thespanningtreecountingofgraphsplaysa
crucialroleinrelevantresearchesofgraphtheory,suchascomplexnetworks,randomwalks,
structureanalysisofgraphs,etc.Withtheincreasingapplicationofspanningtreescounting
problem,itisfoundthatdirectedgraphismoresignificantthanundirectedgraphinrandom
walkandnetworkcontrolsystem.Manyfactsalsotellusthattheresearchonthegraphof
recursiveconstructionortheoperationgraphspanningtreeofdirectedgraphcanprovide
importanttheoreticalbasisforthedesignofnetwork.Therefore,theresearchonspanningtree
countingofdirectedgraphisabasicandmeaningfulwork.
Inthisthesis,thedefinitionsofsomeoperationalgraphsofweighteddirectedgraphsare
introduced,andthedefinitionsofmanyoperationalgraphsunderthebackgroundof
undirectedgraphsisextendedtodirectedgraphs.Byanalyzingthevertex-weightedLaplacian
matrixandSchurcomplementmatrixofthecompositegraphgeneratedbygraphoperation,
thecountingformulasoftherootedspanningtreeofthevertex-weighteddigraphsaregiven,
suchasdirecteddivisiongraph,directedR-graph,directedJoingraphanddirectedCorona
graphandsoon.Inparticularly,whentheweightsoftheverticesandarcsofthegraphareall
1,thecountingfo