具有k个割点标号有向连通图计数

《具有k个割点标号有向连通图计数》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要图论是研究图的组合关系及结构的一个数学分支，其发展已有200多年的历史。图论中所研究的图是由若干给定的点及连接两点的边所构成的图形，这种图形是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统，是数学中经常采用的抽象直观思维方法的典型代表，是一种更全面，更系统的数据结构，是解决许多实际问题的一种理想的数学模型，便于计算机存储和分析计算。因此近年来图论发展迅速，已成为组合数学领域最活跃的分支，其结论和技巧已经广泛移植到计算机科学，电子学，网络理论，信息论，控制论，运筹学，管理科学，社会科学等众

2、多领域的研究中。在人们的社会实践中，现实世界中的许多事物或对象都能用图表示其拓扑结构，把实际闯题的研究转化为图的研究，利用图的相关结论对这些问题做出分析和判断。目前图论已成为解决自然科学，工程技术，社会科学，生物技术以及经济，军事等领域中许多问题的有力工具，越来越受到数学家和实际工作者的喜爱。图的计数是图论中一类重要问题，尤其是有向图的计数在网络流理论，电路网络以及计算机科学的研究中有着越来越广泛的应用。了解具有k个割点的标号有向连通图的计数，在实际计算中可以减少许多不必要的盲目性。本文首先根据图论的基本概念，图的计数中的基本性质和标号

3、计数引理，利用标号有向图的计数，讨论了标号有向图的指数型生成函数和标号有向连通图的指数型生成函数之间的关系，在理论上对所得结论进行了严格证明，算出了标号有向连通图的指数型生成函数的前9项，解决了标号有向连通图的计数问题。在此基础上，进一步研究了标号有向连通图的指数型生成函数和标号有向块的指数型生成函数之问的关系，并对所得结论进行了严格证明，算出了标号有向块的指数型生成函数的前8项，解决了标号有向块的计数问题。最后，引入了第二类Stirling数，利用第二类Stirling数的组合意义及前面所得结论，研究了标号有向块的指数型生成函数和具有

4、唯一一个割点的标号有向连通图指数型生成函数之间的关系，解决了具有唯一一个割点的标号有向连通图的计数问题。并找到了标号有向块的指数型生成函数和所有割点都在一个块上的标号有向连通图的指数型生成函数之间的关系，并对所得结论进行了严格证明。最终解决了所有割点都在一个块上的标号有向连通图的计数问题。关键词；标号有向连通图指数型生成函数第二类Stirling数割点计数ⅡAbstractGraphtheoryisabranchofmathematics,studyingtherelmionofthegraphiccombinationandstruc

5、ture，andithasahistoryofmorethan200years．Thegraphsstudiedingraphtheoryareoneswhicharecomposedbyacertainnumberofgivenpointsandedgeswhicha∞connectedbyusinganabstractformtoexpresssonl时specificobjectsandsomespecifiedrelationexistingornotexistingamongtheseobjects．Besides，thisk

6、indofgraphsarethetypicalrepresentativesofabstractanddirectmethodadoptedinmaththinking,akindofmoiecomprehensive，andsystematicdatastructure，anidealmathematicalmodelusedtoresolvemanypracticalproblems．Andthiskindofgraphsiseasytobestoredincomputersandanalyzedandcalculated．Sog

7、raphtheorydevelopsrapidlyinlf{eceutyears，andithasbeenthemostactivebranchinthefieldofcombinationmath．Inaddition,itsconclusionandtechniqueshavebeentransformedwidelyintovariousfields’study．Suchascomputerscience，electronics，networktheory,informationtheory,cybernetics,operati

8、onalresearch，，managementscienceandsocialscience．Inpeople’Ssocialplactice,lotsofthingsorobjectsinrealwor