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

来源 :南开大学 | 被引量 : 0次 | 上传用户:mydearsun
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论是研究图的组合关系及结构的一个数学分支,其发展已有200多年的历史。图论中所研究的图是由若干给定的点及连接两点的边所构成的图形,这种图形是以一种抽象的形式来表达一些确定的对象,以及这些对象之间具有或不具有某种特定关系的一个数学系统,是数学中经常采用的抽象直观思维方法的典型代表,是一种更全面,更系统的数据结构,是解决许多实际问题的一种理想的数学模型,便于计算机存储和分析计算。因此近年来图论发展迅速,已成为组合数学领域最活跃的分支,其结论和技巧已经广泛移植到计算机科学,电子学,网络理论,信息论,控制论,运筹学,管理科学,社会科学等众多领域的研究中。在人们的社会实践中,现实世界中的许多事物或对象都能用图表示其拓扑结构,把实际问题的研究转化为图的研究,利用图的相关结论对这些问题做出分析和判断。目前图论已成为解决自然科学,工程技术,社会科学,生物技术以及经济,军事等领域中许多问题的有力工具,越来越受到数学家和实际工作者的喜爱。图的计数是图论中一类重要问题,尤其是有向图的计数在网络流理论,电路网络以及计算机科学的研究中有着越来越广泛的应用。了解具有七个割点的标号有向连通图的计数,在实际计算中可以减少许多不必要的盲目性。 本文首先根据图论的基本概念,图的计数中的基本性质和标号计数引理,利用标号有向图的计数,讨论了标号有向图的指数型生成函数和标号有向连通图的指数型生成函数之间的关系,在理论上对所得结论进行了严格证明,算出了标号有向连通图的指数型生成函数的前9项,解决了标号有向连通图的计数问题。在此基础上,进一步研究了标号有向连通图的指数型生成函数和标号有向块的指数型生成函数之间的关系,并对所得结论进行了严格证明,算出了标号有向块的指数型生成函数的前8项,解决了标号有向块的计数问题。最后,引入了第二类Stirling数,利用第二类Stirling数的组合意义及前面所得结论,研究了标号有向块的指数型生成函数和具有唯一一个割点的标号有向连通图指数型生成函数之间的关系,解决了具有唯一一个割点的标号有向连通图的计数问题。并找到了标号有向块的指数型生成函数和所有割点都在一个块上的标号有向连通图的指数型生成函数之间的关系,并对所得结论进行了严格证明。最终解决了所有割点都在一个块上的标号有向连通图的计数问题。
其他文献
近年来,纳米材料在表面工程中的研究取得了很大的进步,优异独特的性质使之在微/纳米电子机械系统中得以广泛应用。为了考虑表/界面效应对纳米材料力学行为产生的影响,Gurtin和Mu
本文对古典风险模型的破产概率计算问题的Laplace变换方法进行了一些讨论,用一些重要的结论和Laplace变换的方法导出了古典风险模型的破产概率ψ(λ),给出了当索赔量是混合指数
胡锦涛总书记 2 0 0 3年 7月 1日在“三个代表”重要思想理论研讨会上发表了重要讲话 ,号召在全党兴起学习贯彻“三个代表”重要思想的新高潮。此前 ,中共中央发出了《关于在
布尔函数作为研究密码学的重要工具得到了广泛的关注.旋转对称布尔函数是一类多输入单输出布尔函数,具有良好的密码学性质,已经被应用在了各种密码学系统中,并且关于其轨道计数
近年来,静宁县委、县政府坚持以“三个代表”重要思想为指导,按照“紧贴中心谋发展,建强龙头抓班子,着眼先进筑堡垒,创新载体增活力”的思路,深入开展“三级联创”活动,组织
本文主要利用Level Set函数隐式地追踪图像的边界来实现图像分割。论文对Level Set方法的数值实现进行了研究,讨论了该方法的全局算法;给出了图像分割的变分问题以及相应的Eu
为了在并行计算机上求解抛物方程的Dirichlet定解问题,本文考虑交替型并行差分格式。构造了具有三阶截断误差的交替分组显格式(AGE),证明了格式的绝对稳定性,并给出了格式的截断
树是图论中最简单而又最重要并且应用最广泛的一类图,它在计算机科学中是一种重要的数据结构,它应用于很多领域,例如,在商业中等级层次的分析,运输网络最小代价的确定等等。图的计
本文根据河北医科大学运用中药青风藤提取物——青藤碱治疗患系膜增生性肾小球肾炎的SD大鼠所得最新实验数据,采用多元统计分析的Fisher判别法和基础统计分析方法的均值比较法
最优化问题及其理论和算法来源于经济,管理,工程等许多重要领域,同时和计算数学中的微分方程数值解法,非线性方程组数值解法等分支有着密切的联系和应用.传统的Broyden族拟牛顿算