检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

生成树计数若干问题研究

生成树计数若干问题研究

作者：龚瑜绍兴文理学院

学位级别：硕士

一个图G的一颗生成树是指包含G所有顶点的连通无圈子图,它是图的一个重要且被广泛研究的同构不变量。若G是完全图Kn的子图,则G的Kn-补图定义为从Kn中删除G中所有边得到的图,记为Kn-G。本文研究了二部图G的Kn 补图(即Kn-G)生成树计数问题... 详细信息

一个图G的一颗生成树是指包含G所有顶点的连通无圈子图,它是图的一个重要且被广泛研究的同构不变量。若G是完全图Kn的子图,则G的Kn-补图定义为从Kn中删除G中所有边得到的图,记为Kn-G。本文研究了二部图G的Kn 补图(即Kn-G)生成树计数问题,并以一种直接计算的方式给出了任意二部图Kn-补图生成树计数的一般公式,进一步,获得了一些特殊二部图的Kn-补图的生成树计数公式,如G为顶点不交边,顶点不交路,顶点不交圈,顶点不交星图和顶点不交完全二部图,推广了Kn-G这类图簇的生成树计数公式,这些公式的证明基于矩阵-树定理以及一个对角矩阵与另一个矩阵和的行列式展开。特别地,当G邻接矩阵的秩小于等于6时,该生成树计数的方法通过对G的一些诱导子图(边K2、匹配2K2、路P3、圈C6等等)计数可以获得Kn-G的生成树数目的显式表达式。此外,将Kn任意两点之间的边增加到m条时,得到的图称为完全m重图,记为Knm。Knm+G(Knm-G)表示在Knm基础上再添加(或删除)子图G的所有边得到的图。Nikolopoulos和Papadopoulos利用Kirchhoff矩阵-树定理和复杂行列式计算给出了Knm± G 生成树计数公式τ(Knm±G)=m(mn)n-p-2 det(mnIp±L(G)),其中,|V(G)|=p,L(G)为G的拉普拉斯矩阵。本文利用线性代数技巧(一个有关矩阵和行列式计算公式),给出了τ(Knm±G)公式的一种简洁证法。此外,当G是完全图、圈、路、完全二部图时,给出了τ(Knm±G)的一些结果。

关键词：生成树拉普拉斯矩阵二部图 Kn-补图完全多重图

基于电网络技巧计数一类平面自相似图的生成树数目

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

运筹学学报 2022年第4期26卷 119-126页

作者：赵伟良齐林明浙江工业职业技术学院浙江绍兴312000

Sierpiński多面体是Sierpiński三角形的三维近似,Sierpiński金字塔自相似图是Sierpiński四面体的1-骨架。本文受Sierpiński金字塔图的构造启发,研究一类构造上极为相似的平面自相似图。基于图的自相似性特点和电网络理论技巧,得到... 详细信息

Sierpiński多面体是Sierpiński三角形的三维近似,Sierpiński金字塔自相似图是Sierpiński四面体的1-骨架。本文受Sierpiński金字塔图的构造启发,研究一类构造上极为相似的平面自相似图。基于图的自相似性特点和电网络理论技巧,得到这类自相似图的生成树的计数公式及生成树增长的熵值。

关键词： Sierpiński三角形生成树自相似电网络等价熵值

维普期刊数据库

在线全文

学校读者我要写书评

暂无评论

一类广义双锥图的生成树数目

厦门大学学报（自然科学版） 2022年第4期61卷 689-693页

作者：李晓琳陈海燕集美大学理学院福建厦门361021

证明了一类广义双锥图的生成树数目可以转化为一个二阶行列式的计算,以此得到了特殊图类的生成树数目的显式表达式,并推广已有的结果.

关键词：生成树拉普拉斯矩阵广义双锥图

维普期刊数据库博看期刊

在线全文

学校读者我要写书评

暂无评论

一些有向图的生成树计数研究

一些有向图的生成树计数研究

作者：王红岩哈尔滨工程大学

学位级别：硕士

图的生成树计数是图论中的一个重要分支,对图论的相关研究也有着至关重要的作用,例如复杂网络、随机游走、图的结构分析等方面。随着生成树计数问题的应用领域逐渐拓宽,人们发现在随机游走和网络控制系统等领域中,有向图中比无向图更具... 详细信息

图的生成树计数是图论中的一个重要分支,对图论的相关研究也有着至关重要的作用,例如复杂网络、随机游走、图的结构分析等方面。随着生成树计数问题的应用领域逐渐拓宽,人们发现在随机游走和网络控制系统等领域中,有向图中比无向图更具有研究意义。诸多事实也告诉我们对各类递推构造的图或有向图的运算图生成树的研究,可以为网络的设计提供重要的理论依据。因此,有向图的生成树计数研究是一项基础且有意义的工作。本文介绍了一些加权有向图的运算图的定义,将许多在无向图背景下的图运算的定义推广到有向图当中。通过分析图运算所生成的合成图的顶点加权Laplacian矩阵和Schur补矩阵给出了有向剖分图、有向R图、有向Join图和有向Corona图等顶点加权有向图的有根生成树计数公式。特别地,当有向图的顶点和有向边权值都为1时,得到了通过图运算所生成的合成图的有根生成树计数公式。

关键词：生成树有向图 Laplacian矩阵

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

几类图的电阻距离和生成树计数

几类图的电阻距离和生成树计数

作者：王艺霏四川师范大学

学位级别：硕士

电阻距离是定义在图上的一个重要不变量,是电路理论与图论的一个经典问题.它来源于电网络中的等效电阻,在组合数学、概率论中也有若干应用.生成树计数问题,具有悠久的历史,同时也是一个至今活跃的课题.生成树的数目在探究网络可靠性方... 详细信息

电阻距离是定义在图上的一个重要不变量,是电路理论与图论的一个经典问题.它来源于电网络中的等效电阻,在组合数学、概率论中也有若干应用.生成树计数问题,具有悠久的历史,同时也是一个至今活跃的课题.生成树的数目在探究网络可靠性方面是一个重要的指标,有广泛的应用空间.图的电阻距离和生成树计数也有密切联系.本文将研究一些图类的电阻距离和生成树计数.完全图、完全二部图的结构较为特殊、对称性极强.在完全图、完全二部图中计算电阻距离和生成树数目相对容易.我们对这些图的结构进行合理改动,删掉其中若干子结构(如圈、路等).这将会削弱完全图、完全二部图的一些局部对称性,会大大提升计算电阻距离和生成树数的难度.本文探讨计算电阻距离和生成树数的各类方法,得出哪些方法在此类图中更为有效,且对一些特殊图能完全确定其电阻距离和生成树数.本文具体安排如下:在第一章中,介绍研究背景、现状及简要说明本文研究内容.在第二章中,给出研究中的一些常用符号和基础知识.在第三章中,研究电阻距离相关知识,着重对完全图及完全二部图去掉路和圈的图进行探究.在第四章中,考虑完全图和完全二部图去掉路和圈的生成树计数.在第五章中,总结全文并提出一些今后有待研究的问题.

关键词：电阻距离生成树完全图完全二部图拉普拉斯矩阵

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的生成树边密度和Kirchhoff指标

图的生成树边密度和Kirchhoff指标

作者：徐灿烟台大学

学位级别：硕士

图的生成树和电阻距离是图论和网络理论中的重要研究课题.本文主要考虑分别基于图的生成树和电阻距离定义的两个重要参数,一个是图的生成树边依赖,另一个是图的Kirchhoff指标.设图G是连通图,包含G中所有顶点的无圈的连通子图称为G的生成... 详细信息

图的生成树和电阻距离是图论和网络理论中的重要研究课题.本文主要考虑分别基于图的生成树和电阻距离定义的两个重要参数,一个是图的生成树边依赖,另一个是图的Kirchhoff指标.设图G是连通图,包含G中所有顶点的无圈的连通子图称为G的生成树.假设G中生成树的数目为τ（G）,并设G中包含给定一条边e的生成树的数目为τG（e）,则称dG（e）=τG（e）/τ（G）为边e的生成树边密度（简称密度）,并称G中所有边的密度的最大值为G的生成树边依赖,记作dep（G）=maxeeE（G）dG（e）.图G中两个顶点i和j之间的电阻距离定义为,将G中的每条边用单位电阻代替后所得到的电网络N中节点i和j之间的等效电阻,并称G中所有顶点对之间的电阻距离之和为G的Kirchhoff指标.本文主要研究关于图的生成树边依赖的两个猜想以及六角化图的电阻距离和Kirchhoff指标.全文共分四章,具体内容如下.第一章主要介绍了本文所用到的概念和记号,并综述了图的生成树以及图的电阻距离和Kirchhoff指标的研究进展.第二章研究了关于生成树边依赖的两个猜想.设p,q为正整数且p＜q,若对任意有理数p/q都存在图G和G中的一条边e,使得dG（e）=p/q,则称有理数p/q是生成树边密度可构造的;如果图G满足dep（G）=p/q,那么我们就称p/q是生成树边依赖可构造的.2002年,Ferrara,Gould和Suffel提出了如下问题:哪些有理数是生成树边密度可构造的?哪些是生成树边依赖可构造的?2016年,Kahl通过构造的技巧证明了（0,1）之间所有的有理数都是生成树边密度和边依赖可构造的.Kahl还进一步证明了限制在二部图或平面图的范围内,（0,1）内的任意有理数也是生成树边密度可构造的.基于此,Kahl猜想限制在二部图（猜想1）或平面图（猜想2）的范围内,（0,1）内的任意有理数都是生成树边依赖可构造的.通过组合和电网络的方法,我们证明了猜想1.对于猜想2,我们证明了该结果对于平面多重图是成立的.但是,对于（简单）平面图,我们证明了猜想2对于大于1/2的有理数都是成立的,但是对于所有不大于1/3的有理数都是不成立的.在第三章中,我们研究了图G的六角化图H（G）的电阻距离和Kirchhoff指标.将G中的每条边都用以边的端点作为起点和终点的两条长度为3的独立路替换后所得到的图称为G的六角化图,记作H（G）.我们用Hk（G）表示对G作k次六角化迭代后所得到的图.利用代数和组合的方法,我们得到了H（G）和Hk（G）的电阻距离和Kirchhoff指标的解析计算公式.所得结果证明,这两类图运算均可以通过原图G的电阻距离和结构参数表示.最后,在第四章中,我们总结了前面两部分的主要内容,并提出了后续的研究问题.

关键词：生成树边密度边依赖电阻距离 Kirchhoff指标

改进蚁群算法和生成树相结合的中压配电网架规划

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

农业工程学报 2013年第A01期29卷 143-148页

作者：梁英关洪浩中国电力科学研究院北京100192 中国农业大学信息与电气工程学院北京100083

由于涉及许多变量和约束,中压配电网规划是一个非常复杂的大规模组合优化问题。蚁群算法是一种具有正反馈特性的贪婪性、分布式的现代启发式搜索方法,适合于路径的寻优,但是易陷入局部最优。该文将蚁群算法和生成树算法结合起来,用于带... 详细信息

由于涉及许多变量和约束,中压配电网规划是一个非常复杂的大规模组合优化问题。蚁群算法是一种具有正反馈特性的贪婪性、分布式的现代启发式搜索方法,适合于路径的寻优,但是易陷入局部最优。该文将蚁群算法和生成树算法结合起来,用于带有交叉点的中压配电网网架规划。针对基本蚁群算法易于陷入局部最优的问题,提出了动态设定待选路径信息素阀值和动态调整路径选择策略的方法,以便提高蚁群算法的全局搜索能力。在考虑中压配电网辐射状和连通性约束时,提出了带有交叉点的生成树方法,大大减少了在规划中不可行解的产生。算例仿真结果表明采用该方法求解中压配电网架规划方案是有效的。

关键词：配电网规划蚁群算法生成树交叉点辐射型网络

维普期刊数据库

在线全文

学校读者我要写书评

暂无评论

几乎完全多部图的生成树及电阻距离

几乎完全多部图的生成树及电阻距离

作者：程素静集美大学

学位级别：硕士

设G是一个边权连通图,顶点集为V(G),边集为E(G),边权函数为ω:E(G)→R.若把G的每条边的权看作该边的电导(即电阻的倒数),则G和一个电网络N(G)等价.图G中的任意两点u和v之间的电阻距离(Resistance distance)定义为电网络中节点u和v之间... 详细信息

设G是一个边权连通图,顶点集为V(G),边集为E(G),边权函数为ω:E(G)→R.若把G的每条边的权看作该边的电导(即电阻的倒数),则G和一个电网络N(G)等价.图G中的任意两点u和v之间的电阻距离(Resistance distance)定义为电网络中节点u和v之间的等效电阻,记为RG(u,v).利用电阻等价替换原理,物理学家早就发现的串并联法则、(广义)三角形-星变换等局部变换方法求电网络中两点间的电阻与对应的图的生成树的数目.本文给出了完全多部图-繁星变换的电阻版本和生成树版本.作为应用,首先给出了完全多部图加一个匹配得到的图中任意两点之间的电阻距离的计算公式以及生成树的计数表达式.其次,我们给出了一个统一的方法来计算几乎完全s部图的生成树的数目,特别当s=2,3,4时的几乎完全s部图的生成树的数目的计算公式.最后,我们研究了一类带权的几乎完全二部图的生成树的权和计算问题.

关键词：电阻距离生成树 Kn1,n2,...,ns-繁星变换三角形-星变换几乎完全多部图

基于无向生成树的并行遗传算法在配电网重构中的应用

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

电力系统自动化 2015年第14期39卷 89-96页

作者：黄红程顾洁方陈电力传输与功率变换控制教育部重点实验室上海交通大学上海市200240 国网上海市电力公司电力科学研究院上海市200437

随着以风电、光伏为代表的不可控型分布式电源在配电网中的渗透率日益提高,分布式电源出力的不确定性成为配电网重构中必须考量的重要因素。因此建立了以系统网损最小为目标,计及潮流方程、节点电压、支路潮流和配电网开环运行约束的配... 详细信息

随着以风电、光伏为代表的不可控型分布式电源在配电网中的渗透率日益提高,分布式电源出力的不确定性成为配电网重构中必须考量的重要因素。因此建立了以系统网损最小为目标,计及潮流方程、节点电压、支路潮流和配电网开环运行约束的配电网重构随机优化模型。模型以机会约束描述节点电压和支路潮流约束,采用基于拉丁超立方采样的蒙特卡洛法随机潮流进行检验。提出了基于无向生成树的并行遗传算法以实现配电网重构模型的并行求解。IEEE 33节点系统的测试结果验证了模型的合理性,并将所提出的算法与基于无向生成树的遗传算法、粒子群优化算法、蚁群搜索算法和改进和声搜索算法进行比较,验证了其高效性。

关键词：配电网重构生成树遗传算法并行算法随机模型概率潮流拉丁超立方采样机会约束

维普期刊数据库