共查询到20条相似文献,搜索用时 15 毫秒
1.
给出了生成子图和生成子图的计数定理。证明了生成子图的构造定理。提出了任意完全图Kp的生成树的计数方法和构造方法。给出了生成子树的计数公式。利用生成子圈的计数方法,寻找生成子图的生成树,证明了生成树的构造定理和计数定理。同时介绍了完全图K5的含圈生成子图及不含圈的生成树的计数和构造。生成树的计算公式过于庞大,且仅适用于完全图的Kp。平图例子验证了构造定理和计数定理的实用性和有效性,是构造一个完全图的生成树的简单易行的方法。 相似文献
2.
偶阶完全图Kp的生成树的计数 总被引:6,自引:5,他引:1
给出了生成子图的定义.证明了生成子图的计数定理和构造定理.提出了生成树的计数方法和构造方法.介绍了完全图K6的含圈的生成子图和不含圈的生成树的计数与构造. 相似文献
3.
给出了生成子图的定义。证明了生成子图的计数定理和构造定理。提出了生成树的计数方法和构造方法。介绍了奇阶完全图K_5、K_7的含圈生成子图和不合圈生成树的计数与构造。 相似文献
4.
完全二分图的生成树的个数 总被引:3,自引:0,他引:3
给出了生成子图的定义.证明了生成子图的构造定理和计数定理.提出了任意G(p,q)的生成树的计数方法和构造方法.介绍了完全二分图K3,3的生成树的计数和构造. 相似文献
5.
经典理论矩阵树定理用于图中生成树的计数并不实用,但利用Chebyshev多项式的性质作为工具,结合Kel,malls和Chelnokov的结果,可以给出较简单的方法对很多图中的生成树进行精确计数.通过给出一些组合图中生成树的计数进一步体现了该技术在其中所起的作用. 相似文献
6.
7.
从组合数学的角度研究生成树的计数.先利用容斥原理,得到3个组合恒等式,再从组合数学的角度出发,并利用数学归纳法给出了Cayley's公式的又一简便证明.该计数方法将图的计数问题与组合数学中的经典问题联系起来,更好地揭示了生成树计数的本质. 相似文献
8.
基于路的多重完全图相关图的生成树数目 总被引:1,自引:0,他引:1
谭秋月 《曲阜师范大学学报》2012,(3):47-52
利用图G的标号技巧、矩阵和行列式运算、补生成树矩阵定理等,研究了当G是基于路的多重完全图时的补图类Kn-G的生成树数目的计数问题,并求出了补图类Kn-G的一些特殊情况的生成树数目的计数公式. 相似文献
9.
《太原科技大学学报》2015,(4)
主要研究了无圈竞赛图中的外向生成树和指定点对的路问题,得到了图中全部外向生成树的计数公式τ+(Tn)=(n-1)!,在此基础上,得出图中全部内向生成树的计数公式τ-(Tn)=(n-1)!;两点之间全部路的计数公式σ(Tn)=2n-2,在此基础上,得出n阶无圈图全部路数为2j-i-1. 相似文献
10.
五面体平图中的生成树的构造与计数 总被引:1,自引:1,他引:0
首先给出了生成子图的定义,生成子图与生成树、含圈的生成子图的关系S(G)=C(G)+T(G);其次对于任意连通图,以p=4,q=6的完全图K4为例给出了生成子图个数的计算公式,同样以p=4,q=6完全图K4为例给出了生成树的构造定理和计数定理,提出了图S(G)生成树的计数方法和构造方法;最后,介绍了五面体平图生成子图个数的计算和各生成子图的构造,并验证了所给公式的正确性,从而解决了任意平图G(p,q)生成树的构造问题。 相似文献
11.
基于圈或路的多重星相关图的生成树数目 总被引:1,自引:0,他引:1
谭秋月 《天津师范大学学报(自然科学版)》2013,33(1):30-34
利用图的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当图G是基于圈或路的多重星图时,补图类Kn-G的生成树数目的计数问题,得到了一些特殊情况下基于圈或路的多重星相关图的生成树数目的计数公式. 相似文献
12.
W.T.Tntte在中提出了这样的猜想:在具有2m条边的所有3-连通平面图中,其生成树的总数以轮W_(m 1)为最小.笔者利用连通图的生成树数的Cayley定理,给出了若干3-连通平面图的生成树的显式计数公式,获得了这个猜想的若干反例,明了对任何m≥27的整数,轮W_(m 1)都不是生成树数最小的3-连通平面图的结论.文中还给出了另外一些连通平面图的生成树的计数公式. 相似文献
13.
谭秋月 《集美大学学报(自然科学版)》2014,(1):57-62
利用图G的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当G是基于圈的多重完全图时,其补图类Kn-G的生成树数目的计数问题.给出基于圈的多重完全图相关图Kn-G的一些特殊情况时生成树数目具体计数公式. 相似文献
14.
许进 《西北大学学报(自然科学版)》1989,19(4):23-31
本文主要给出了两类图的支撑树的计数公式,这两类图的支撑树的计数公式,几乎把目前所获得的特殊图的计数公式都作为它们的特例。另外附带地给出了几类图的支撑树的简便计数方法。 相似文献
15.
蒋强荣 《郑州大学学报(理学版)》2010,42(3)
针对图的相似性问题,提出了基于生成树的回路核,其中包括基于最小生成树的回路核、基于最大生成树的回路核、基于最小生成树或最大生成树的回路核、基于最小生成树与最大生成树的回路核、基于混合生成树的回路核、基于赋权混合生成树的回路核.结果表明,所定义的基于生成树的回路核是可计算的、正定的;在实验中,回路核的识别率高于通路核的识别率,最高可达100%. 相似文献
16.
17.
18.
完美匹配树的计数公式 总被引:3,自引:0,他引:3
魏均斌 《华南师范大学学报(自然科学版)》2002,(1):61-63
证明完美匹配树的一些相关性质与定理,并利用Polya计数定理得到了完美匹配树的计数公式。 相似文献
19.
20.
最小生成树的寻求一直受到人们的关注,而EXCEL的规划求解有着较强的计算功能。借助EXCEL规划求解得以方便快捷地找寻最小生成树,并对多个最小生成树、指定边的最小生成树的找寻进行了讨论。 相似文献