共查询到20条相似文献,搜索用时 15 毫秒
1.
利用对偶图求平面图的生成树数目 总被引:1,自引:0,他引:1
图的生成树数目是图的一个重要参数,求连通图生成树数目的方法有很多.本文利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目,求这类平面图的生成树数目比直接利用收缩边和去边得到递推公式的方法要简单,该方法对于平面图可以进一步推广. 相似文献
2.
一类平面图的生成树数目 总被引:1,自引:0,他引:1
利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目,求这类平面图的生成树数目比直接利用Cayley公式要简单,且该方法对于同一类的平面图可以进一步推广. 相似文献
3.
谭秋月 《集美大学学报(自然科学版)》2014,(1):57-62
利用图G的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当G是基于圈的多重完全图时,其补图类Kn-G的生成树数目的计数问题.给出基于圈的多重完全图相关图Kn-G的一些特殊情况时生成树数目具体计数公式. 相似文献
4.
基于路的多重完全图相关图的生成树数目 总被引:1,自引:0,他引:1
谭秋月 《曲阜师范大学学报》2012,(3):47-52
利用图G的标号技巧、矩阵和行列式运算、补生成树矩阵定理等,研究了当G是基于路的多重完全图时的补图类Kn-G的生成树数目的计数问题,并求出了补图类Kn-G的一些特殊情况的生成树数目的计数公式. 相似文献
5.
基于圈或路的多重星相关图的生成树数目 总被引:1,自引:0,他引:1
谭秋月 《天津师范大学学报(自然科学版)》2013,33(1):30-34
利用图的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当图G是基于圈或路的多重星图时,补图类Kn-G的生成树数目的计数问题,得到了一些特殊情况下基于圈或路的多重星相关图的生成树数目的计数公式. 相似文献
6.
证明了一类广义双锥图的生成树数目可以转化为一个二阶行列式的计算,以此得到了特殊图类的生成树数目的显式表达式,并推广已有的结果. 相似文献
7.
在一个给定的概率空间(Ω,F,P)中,通过建立一个古典概率,人出了图论中关于完全图Kn的生成树的数目公式,即Cayley定理及Clarke定理,进而,证明了在“团”下更一般情形的图的生成树的数目公式,使Caley定理及Clarke定理成为其在完全图下的特殊情况。 相似文献
8.
令N表示满足如下条件的数对(k,l)∈(N U{∞})2全体:存在一个无穷电网络,其上的绑定生成森林几乎处处有l棵树,而其上的自由生成森林以正概率有k棵树.证明了N={(k,l)∈N2|k≤l}U{(∞,∞)}U{(k,∞)|k∈N}. 相似文献
9.
卢鹏丽 《兰州大学学报(自然科学版)》2007,43(3):114-117
生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量.利用切比雪夫多项式的性质推出了循环图中计算生成树个数的在线性时间内即可实现的方法,并讨论了渐进特性. 相似文献
10.
图生成树棵数的一种求法 总被引:1,自引:0,他引:1
吐然克孜·热合曼 《新疆师范大学学报(自然科学版)》2004,23(4):41-44
本文提出了对给定图 G来说 ,计算它的所有的生成树棵数的一种方法 ,即由 Cayley定理与 Binet-Cauchy定理来推导一个公式τ(G) =det(KKT) ,为了证明此公式的成立 ,还证明了从一个图的完全关联矩阵 M(G)中删去任意一行后 ,得到的矩阵 K和 K的转置 KT满足 Binet-Cauchy条件。公式τ(G) =det(KKT)的证明是由一个图的生成树的棵数公式τ(G) =τ(G -e) τ(G . e)与具有以上性质的矩阵 K与 KT且 det(KKT) =∑ Ki Ki=∑K2i 合起来证明。 相似文献
11.
12.
13.
连通图的生成树是指该图的极小连通生成子图.在Cayley公式的基础上,给出树扩图生成树数的上下界. 相似文献
14.
15.
计算图(有向图或无向图)中生成树的个数可以用组合的方法,也可以用代数的方法。介绍了用代数的方法求图中生成树的个数,给出了欧拉回路与生成树的关系,并将其应用于实际的问题中,解决了一类等价类问题。 相似文献
16.
如何精确求解出图的全部生成树,是图论研究的重要课题之一.引入组合数学的母函数原理,结合图论相关理论,提出了一种求图的全部生成树的新方法,该方法易于在计算机上实现,能精确求解连通图的生成树数目及其全部生成树,快速找出带权图的最小生成树,并给出了严密证明. 相似文献
17.
18.
黄鲤颖 《华侨大学学报(自然科学版)》1998,19(1):12-15
设t(m,n)和t(m,n)分别是平面m×n格图生成树和对称生成树的数目,从而给出了t(3,n)和t(3,n)的闭公式以及t(m,n)递推式阶的估计. 相似文献
19.
最小生成树问题是运筹学网络优化中一个常见的基本问题.提出了一种新的求最小生成树的矩阵算法,此算法可以不必在原图上进行操作而得到最小生成树,过程简单易懂. 相似文献
20.
树T是连通的无圈图。T的子树数是指T的所有子树的数目。L.A.Szekely和Wang Hua证明了在所有树图中,子树数最大的图是星图,最小的图是路图。本文利用树的子树计算公式,研究了直径为5的子树的数目,并探讨了直径为5的子树数目的变化规律。对于Wiener index和网络可靠性等的研究具有一定的意义。 相似文献