度限制最小树的蚂蚁算法

Based on the ant system methodology,this paper offers an algorithm for the degree constrained minimum spanning tree problem.Compared with some other algorithms, numerical examples are tested which give promising results and useful conclusions.

基于二维调制的级联型整流器负载平衡度限制范围

级联型整流器运行时可能会出现负载不平衡的情况,负载平衡度超出一定范围时直流母线电压将无法保持平衡,此时由其合成的交流侧电压谐波分量增加,导致系统电流的谐波分量也相应增加。在对基于二维调制的平衡控制方式研究的基础上,对单相两级级联整流器的调制波形作深入分析,根据调制波形推导出使两桥直流母线电压能够保持平衡的负载平衡度限制范围。搭建基于Matlab/Simulink的仿真模型和基于RT-lab的半实物实时仿真实验平台,通过仿真和实验验证所作分析与结论的正确性,为无工频变压器级联式功率变换器的设计提供了理论依据。

蚂蚁算法建立度限制树在聚类中的应用

针对聚类算法解决大规模数据时间复杂度和空间复杂度都很大的问题,给出了应用蚂蚁算法建立度限制树,同时结合密度思想来解决这一问题的算法.经过数据的测试和验证,得到了较好的结果和一系列有意义的结论.

求解度限制最小生成树问题的启发式遗传搜索算法

提出了求解度限制最小生成树问题的启发式遗传搜索算法 ,通过大量的数值试验验证其可行性 ;最后对此算法做了适当推广 ,并给出了用它求解 TSP及

完全对换网络的限制连通度

完全对换网络是基于Cayley图模型的一类重要互连网络.一个图G的k-限制点(边)连通度是使得G-F不连通且每个分支至少有k个顶点的最小点(边)子集F的基数,记作kk(λk).它是衡量网络可靠性的重要参数之一,也是图的容错性的一种精化了的度量.一般地,网络的k-限制点(边)连通度越大,它的连通性就越好.证明了完全对换网络CTn的2-限制点(边)连通度和3-限制点(边)连通度,具体来说:当n≥4时,k2(CTn)=n(n-1)-2,k3(CTn)=3n(n-1)/2-6;当n≥3时,λ3(CTn)=n(n-1)-2,λ3(CTn)=3n(n-1)/2-4.

最小K度限制树的构建及算法改进

结合最小k度限制树和一维装箱这两个问题,本文研究了一个新的最优化问题:给定一个简单的连通无向网络G=(V,E;w)及常数L。我们用长度为"L"的材料构建k度限制树T,且T上的每条边至多能用一次料头(指材料构建完某条边后剩下的部分)。假设所用材料的根数为C,目标是C尽可能小。本论文对所提问题的特殊情形设计了一个3/2近似算法,对一般情形设计了一个2-近似算法,接着将2-近似算法改进到7/4-渐进近似。

无向 Kautz 图的限制性连通度和限制性容错直径

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４．

二值命题逻辑中基于信息限制的随机真度

以随机真度为基础,提出了二值命题逻辑中公式的在有限信息Γ限制下的随机真度概念。以此为基础定义了公式的Γ-限制随机相似度和Γ-限制随机伪距离,得到了在有限信息Γ限制下公式到理论结论集的Γ-限制随机伪距离的Γ-限制随机真度表示式,为二值命题逻辑中基于有限信息限制的近似推理的随机化研究提供数值化工具。

一些笛卡尔乘积图的限制连通度(英文)

子集S V(G)称为限制割,若任何点v∈V(G)的邻点集NG(v)都不是S的子集且G-S不连通.若G中存在限制割,则定义限制连通度1κ(G)=min{S:S是G的一个限制割}.考虑了笛卡尔乘积图,证明了:设G=G1×G2×…×Gn,若Gi是满足某些给定条件的ki连通ki正则且围长至少为5的图。

关于金字塔网的限制连通度与(l,k)控制数

金字塔网是并行计算、图像处理的一种很重要的网络拓扑结构,考察了一些金字塔网 的性质,给出它的限制连通度及(l,k)控制数.

二值命题逻辑中Γ限制蕴涵度量与近似推理

基于某信息限制下若A则B的推理思想,以真度为基础,在二值命题逻辑系统中引入有限信息限制下的公式蕴涵度概念,由此定义了信息限制蕴涵度量,并通过信息限制蕴涵度量的真度表示式,给出一系列与有限理论结论集相关的限制蕴涵度量不等式,对二值命题逻辑中基于信息限制蕴涵度量的近似推理问题进行讨论。

有向线图的限制性连通度(英文)

设D=(V(D),A(D))是一个强连通有向图.弧集S(?)A(D)称为D的k-限制性弧割,如果D-S中至少有两个强连通分支的阶数大于等于k.最小k-限制性弧割的基数称为k-限制性弧连通度,记作λ_k(D).k-限制性点连通度κ_k(D)可以类似地定义.有k-限制性弧割(k-限制性点割)的有向图称为λ_k-连通(κ_k-连通)有向图.本文研究有向图D的限制性弧连通度和其线图L(D)的限制性点连通度的关系,证明了对任意λ_k-连通有向图D,κ_k(L(D))≤λ_k(D),当k=2,3时等式成立;若L(D)是κ_(k(k-1))-连通的,则λ_k(D)≤κ_(k(k-1))(L(D));特别地,若D是一个定向图且L(D)是κ_(k(k-1)/2)-连通的,则λ_k(D)≤κ_(k(k-1)/2)(L(D)).

立方体的线图的限制性连通度(英文)

子集SE(G)称为是图G的4-限制性边割,如果G-S不连通且每个连通分支至少有4个点.图G中基数最小的4-限制性边割称为4-限制性边连通度,记为λ4(G).本文确定了λ4(Qn)=4n-8.类似的,子集FV(G)称为图G的Rg-限制性点割,如果G-F不连通且每个连通分支的最小度不小于g.基数最小的Rg-限制性点割称为图G的Rg-限制性点连通度,记为κg(G).本文确定了κ1(L(Qn))=3n-4,κ2(L(Qn))=4n-8,其中L(Qn)是立方体的线图.

修正泡序图的限制性点连通度(英文)

设G=(V,E)是一个图,F V(G)是一个点子集.称F为G的一个k-超点割,如果G F不再连通且G F的每一个连通分支都至少有k+1个点.图G的k-超点连通度,记作κk(G),是图G的最小k-超点割的基数,它是图的容错性的一种精化了的度量.本文研究修正泡序图MBn的κ2,并证明对于n≥4,κ2(MBn)=3n 5.

广义de Bruijn有向图和Kautz有向图的限制性弧连通度

有向图的限制性弧连接度是测量互连网络容错性的重要参数.本文证明了对于直径k≥4和参数d≥4的广义de Bruijn有向图BG(n, d),它的限制性弧连通度是2d-2.对于直径k≥4和参数d≥4或者d≥3, k≥5, n和d的最大公约数g.c.d(n,d)≥2和n可以被d+1整除的广义Kautz有向图KG(n, d),它的限制性弧连通度为2d-2.作为结论, BG(n, d)和KG(n, d)的超限制性弧连通性可以直接得出.本文还证明了对于任意的强连通有向图D有λh(D)≤min{ξh(D),|V1|λ(D2),|V2|λ(D1)}.另外,对于直径k≥4,证明这两类有向图分别跟自己做笛卡尔积得到的有向图的限制性弧连通度分别是d≥3,λ2(BG(n, d)×BG(n, d))=4d-2;d≥2,λ2(KG(n, d)×KG(n, d))=4d-2.

BCube在2-限制连通度下的容错路由算法

BCube是具有良好性能的数据中心网络。相比传统的树形数据中心网络,BCube在扩展和容错性能方面都表现出很大的优势。目前,对于BCube的研究可以归结为对其逻辑图BC_(n,k)(广义超立方体的一种特例)的研究,其中交换机被视为透明设备。在实际应用中,随着网络规模的不断增加,顶点发生故障已经成为一种常态。因此,研究网络的容错路由很有意义。目前,有不少关于BC_(n,k)容错路由的研究,但其2-限制连通度下的容错路由目前还没有被研究。在提出容错路由算法之前,首先证明了BC_(n,k)的2-限制连通度为3(k+1)(n-1)-2n,其中k≥3且n≥3。然后在此基础上提出了一个时间复杂度为O(κ(BC_(n,k))~3)的容错路由算法,其中κ(BC_(n,k))=(k+1)(n-1)是BC_(n,k)的连通度。该算法可以在故障顶点个数小于3(k+1)(n-1)-2n且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径。

交叉立方体的限制性连通度（英文）

G是一个图,h是一个正整数,一个图G的h-限制性连通度是使得G删除G中的某个点集使得G不连通且每个分支中点的度数至少是h的最小点集的基数.交叉立方体网络是超立方体的一个变形,在平行计算系统当中交叉立方体是最重要的网络之一.该文证明了n维交叉立方体2-和3-限制性连通度分别是4n-8(n≥4)和8n-24(n≥5).

折叠交叉立方体的限制连通度

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F■V(G)(F■E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的基数称为图G的h-限制连通度(h-限制边连通度),记为κ_(h)(G)(λ_(h)(G)).本文确定了h=2时n-维折叠交叉立方体FCQ_(n)的κ_(h)(G)和λ_(h)(G).