共查询到20条相似文献,搜索用时 289 毫秒
1.
王忠义 《西安科技大学学报》2003,23(1):107-110
连通图必存在支撑树,且支撑树一般不唯一。如何得到连通图的所有支撑树,是图论中讨论的一个重要问题。利用基本割集对应的子图多项式生成所有支撑树是一个简单可行的方法[1],现有的对这种方法的理论证明较繁琐。本文给出一种较直观的证明,说明该方法可生成全体互异的支撑树。 相似文献
3.
《信阳师范学院学报(自然科学版)》2015,(4):597-600
针对当赋权连通图中存在权值相同的多条边时,传统的Kruskal算法不能计算出全部的最小生成树,提出了求解最小生成树的改进算法.实验结果表明,改进算法可以得到一个赋权连通图的所有最小生成树,进而为决策者提供更全面的最优决策方案. 相似文献
4.
利用对偶图求平面图的生成树数目 总被引:1,自引:0,他引:1
图的生成树数目是图的一个重要参数,求连通图生成树数目的方法有很多.本文利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目,求这类平面图的生成树数目比直接利用收缩边和去边得到递推公式的方法要简单,该方法对于平面图可以进一步推广. 相似文献
5.
研究局部连通图中支撑树的变换. 给出L.Nebesk定理的一个新证明, 并将其推广得到一类新的上可嵌入图. 相似文献
6.
连通图的生成树是指该图的极小连通生成子图.在Cayley公式的基础上,给出树扩图生成树数的上下界. 相似文献
7.
提出一种求连通图的全部树的方法,该方法采用撕裂大图分为两个连通片,然后添加撕裂边,便生成全部生成树,该方法可用于计算机并行运算,适用于大网络的计算机辅助分析。 相似文献
8.
周理 《曲阜师范大学学报》1995,21(4):39-42
给出了无向边集是支撑树的混合图为欧拉图的充要条件,在此基础上,结合Guan和Pulleyblank算法,给出了另外一种求解最小欧拉定向的算法。 相似文献
9.
简单有向连通图关联矩阵右逆的图特征及应用 总被引:1,自引:0,他引:1
李斌 《重庆大学学报(自然科学版)》2000,23(2):34-38,55
研究n阶简单有向连通图的n-1传导矩阵,引入了图真值向量及运算,得出n阶简单有向连通图关联矩阵右逆的图特征;提出了一种寻找简单有向连通图全部生成树的方法。 相似文献
10.
陈东灵 《山东科技大学学报(自然科学版)》1986,(2)
本文基于“最优树算法”,在赋权连通图关于最优树的基本圈中,通过边权的比较,得到了次优树的算法,並给出了证明,从而解决了如何把一个赋权连通图的所有生成树按权的大小进行排序的一种方法。由此对工程设计中经常迂到的“连线问题”,可以给出各种不同的设计方案,供决策部门选择。 相似文献
11.
图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况,得到了最小度至少为5或围长至少为4的4连通图中在其生成树上存在至少两条可去边;同时也得到了最小度至少为5的4连通图中在其生成树外存在至少两条可去边. 相似文献
12.
13.
以G的生成树为点,两点相邻的充要条件是两颗生成树只相差一条边,这个图称为G的生成树图。连通图的生成树图是连通的,本文对此进行推广,证明了赋权连通图的最优树图也是连通的。 相似文献
14.
以G的生成树为点,两点相邻的充要条件是两颗生成树只相差一条边,这个图称为G的生成树图。连通图的生成树图是连通的,本文对此进行推广,证明了赋权连通图的最优树图也是连通的。 相似文献
15.
简单图类的生成树数(I) 总被引:3,自引:3,他引:0
王维凡 《辽宁大学学报(自然科学版)》1995,22(3):32-36
连通图的生成树是该图的极小连通生成图。本文通过Cayley公式及求解递推关系方程,分别求出了三类简单外平面图An,Bn和Zn的生成树的棵数,给出了它们的递推关系式及通项表达式。 相似文献
16.
柳柏濂 《华南师范大学学报(自然科学版)》1985,(1):1
本文证明了关于连通图划分的一个定理.运用这个定理,简化了标号连通图和标号树的递归计数关系的证明,并导出了给定价数和根点块数的有根标号连通图和二色标号连通图的递归计数式. 相似文献
17.
连通图的生成树是指该图的极小连通生成子图.通过Cayley公式、递推关系式及伪类环图与伪类环图生成树数之间的关系式给出伪类环图-Sn,-An的生成树数. 相似文献
18.
谢力同 《山东大学学报(理学版)》1986,(3)
本文讨论连通图的支撑树系列基边向量总表的有关性质,并用来研究边重构问题,得出一个边3连通图是边可重构的一个充要条件和一族连通图是合法的主子图族的一个充要条件(见§6.5和§6.6) 相似文献
19.
20.
全部树的一种生成方法 总被引:1,自引:0,他引:1
本文介绍一种找出连通图全部生成树的方法.通过视察一个给定连通图,利用两类 K—树,直接列出全部树的表达式,相乘展开此式,恰好得到该图的全部生成树. 相似文献