共查询到20条相似文献,搜索用时 296 毫秒
1.
将W.T.Tultte提出的计算有向图中以某点为根的支撑出树数目的公式推广到了更一般的情况,并给出了有向图中具有不同特点的支撑树数目的计算公式。 相似文献
2.
李帮义 《高等学校计算数学学报》2002,24(3):283-288
支撑树问题已经有很长的研究历史了,见[1].在许多工程问题中,需要产生一个网络G的所有支撑树,见[2,3,4].当G为赋权图时,每棵支撑树T有长度L(T).在产生G的所有支撑树时,许多工程问题希望按照L(T)的非降顺序产生,见[5,6].在按照L(T)的非降顺序产生的支撑树中,有许多支撑树长度是相同的,而支撑树的数目又非常大(可以高达nn-2个),因此算法的计算量非常大.本文希望能够按照L(T)的严格上升顺序产生所有的支撑树,从而避免大量的重复计算. 相似文献
3.
主要研究了树指标非齐次马氏链的广义熵遍历定理.首先证明了树指标非齐次马氏链上的二元函数延迟平均的强极限定理.然后得到了树指标非齐次马氏链上状态出现延迟频率的强大数定律,以及树指标非齐次马氏链的广义熵遍历定理.作为推论,推广了一些已有结果.同时,证明了局部有限无穷树树指标有限状态随机过程广义熵密度的一致可积性. 相似文献
4.
5.
6.
旋转壳的边界条件,传统的表达方式是在中面位移μ,μ,ω,ψ或相应的四个力共八个量当中给定四个.而以节圆广义位移作为基本未知数,一个节圆上未知数的数目超过四个.在这种情况下关于边界条件的处理问题尚无令人满意的解决办法.本文利用虚功原理,导出一组壳边广义量与非广义量关系公式.研究了七种类型常见边界,给出用广义力与广义位移表示的边界条件公式.每一种边界条件公式的数目可以和一个节圆上所采用的未知数数目相一致.有了这些公式,即可直接将边界条件代入广义位移法运动方程以求解广义位移.这样做,避免了文献[2]关于未知数的变换与逆变换过程,不仅道理上简明而且也简化了计算.有了边界条件广义表达式,使得旋转壳广义位移法在理论上也更为完善. 相似文献
7.
本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小. 把瓶颈型Hamming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法. 相似文献
8.
该文引进广义Bethe树和广义Cayley树的概念,并研究其上马氏链场关于状态和状态序偶出现频率的强极限定理,作为主要结果的推论,得到Bethe树和Cayley树上马氏链场的ShannonMcMillan定理.证明中采用了研究概率论强极限定理的一种新的方法. 相似文献
9.
本在无向网络中,建立了带有边集限制的最均匀支撑树问题的网络模型.中首先解决最均匀支撑树问题,并给出求无向网络中最均匀支撑树的多项式时间算法;然后,给出了求无向网络中带有边集限制的最小树多项式时间算法;最后,在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题. 相似文献
10.
11.
广义de Bruijn和Kautz有向图的距离控制数 总被引:1,自引:0,他引:1
对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?).图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者.本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件.从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= .在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= . 相似文献
12.
Guillaume Ducoffe 《Discrete Applied Mathematics》2013,161(13-14):2200-2204
In this article, we determine when the large generalized de Bruijn cycles are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized cycles. They are Kronecker products of generalized de Bruijn digraphs and dicycles. 相似文献
13.
设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界. 相似文献
14.
In this paper, we completely determine the connectivity of every infinite circulant digraphs and prove that almost all infinite
circulant digraphs are infinitely strongly connected and therefore have both one- and two-way infinite Hamiltonian paths.
Received February 4, 1998, Accepted May 16, 2002 相似文献
15.
16.
In this paper,we study the bases and base sets of primitive symmetric loop-free (generalized)signed digraphs on n vertices.We obtain sharp upper bounds of the bases,and show that the base sets of the classes of such digraphs are{2,3,...,2n-1}.We also give a new proof of an important result obtained by Cheng and Liu. 相似文献
17.
18.
We call a Cayley digraph Γ = Cay(G, S) normal for G if G
R
, the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs
of valency 2 on nonabelian groups of order 2p
2 (p odd prime). As a result, a family of nonnormal Cayley digraphs is found.
Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998 相似文献
19.
20.
一个本原不可幂带号有向图s的基指数l(s)是这样的最小正整数l,使得在s中,从任意一点u到任意一点v都有一对长为l的sssD途径.本文研究了n阶最小奇圈长为r的本原不可幂对称带号有向图的基指数,给出了这类有向图的基指数的最大值. 相似文献