共查询到20条相似文献,搜索用时 78 毫秒
1.
冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。 相似文献
2.
3.
4.
连通图生成的Cayley图是作为互连网络的群论模型提出来的概念。猜想:设G=(V,E)是具有顶点集{1,2,…,n}(n>2)和m条边的连通图。如果m=2r,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m-2k个完美对集的并;如果m=2r+1,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m-2k个完美对集的并。特别地,对于k=r和星网络,这个猜想的特殊情形是1998年由师海忠提出来的。 相似文献
5.
7.
n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树(transposition tree)的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。 相似文献
8.
传感器网络中高效的最小连通支配集求解算法 总被引:1,自引:1,他引:0
在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。 相似文献
9.
连通支配集在无线传感器网络中有着重要的作用,通过对连通支配集的深入分析得到了关于连通支配集的一个新特性,即最小连通支配集是图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论设计了一种全新的连通支配集求解算法,即通过建立一棵含叶子节点较多的生成树来寻找一个较小的连通支配集。仿真实验表明,新算法较前人的算法有明显的改进。 相似文献
10.
无线传感器网络的一个虚拟骨干是一个节点子集,虚拟骨干中的节点负责相关的路由任务。设计的虚拟骨干越小,网络的相关开销就越少,虚拟骨干的大小是衡量虚拟骨干质量的关键因素。通常,单位圆盘图被用来模拟一个无线传感器网络。在无线传感器网络中寻找最小虚拟骨干问题可以抽象为求单位圆盘图中的最小连通控制集问题。然而,求单位圆盘图中的最小连通控制集问题是NP难问题,许多工作都是致力于寻找最小连通控制集的近似算法。无线传感器网络中构造3连通多跳控制集可以有效地减小连通控制集的大小和节点间转发的信息总数,是寻找最小虚拟骨干的有效近似。为此提出了一个无线传感器网络中构造3连通多跳控制集的算法,获◢得一个大小不超过5(2r+2β+1)(r+1)β|U*△|-10(2+β)(r+1)-5r-12的3连通多跳控制集。最后通过仿◣真实验对提出的算法性能作了相应分析,实验结果符合算法的预期效果。 相似文献
11.
为多种密码学构造性质良好的布尔函数一直是对称密码学研究中的一个难点问题。最近,涂自然和邓映蒲
基于一个二元组合猜想的正确性,构造了两类具有最优代数免疫度的布尔函数,其中第一类函数是具有最优代数免疫
度的13cnt函数,另一类是平衡且具有最优代数免疫度的高非线性度函数。涂一邓猜想引起了国内外密码学者的高度
关注。现通过分析涂一邓猜想中参数t满足二tC}>=3情形时的二元Hamming重量的特性,给出涂一邓猜想在二tCt}=3
情形下的证明,并以推论的形式推出二t相似文献
12.
首先分析了具有多个非线性特性的 SIMO 和 MISO 系统的绝对稳定性问题, 指出应用已知的频域判据来解决上述问题很难奏效. 然后, 基于所有孤立部分传递函数都正实的充分必要条件给出了上述系统为稳定的一个猜想, 当传递函数的零极点都位于虚轴上时, 由这一猜想得到了一个已知的结论; 当传递函数的零极点都位于实轴上时, 由这一猜想得到了一个新的结论, 本文证明该结论是正确的; 最后, 根据这一猜想, 给出了传递函数极点位于复平面的一个例子, 它涉及到一类系数矩阵为时变正定矩阵的振动方程的稳定性问题, 值得去深入研究. 相似文献
13.
14.
Drugs and other chemical compounds are often modeled as polygonal
shapes, where each vertex represents an atom
of the molecule, and covalent bonds between atoms are represented by edges between
the corresponding vertices. This polygonal shape derived from a chemical
compound is often called its molecular graph, and can be a
path, a tree, or in general a graph. An indicator defined over this molecular graph,
the Wiener index, has been shown to be strongly correlated to various
chemical properties of the compound.
The Wiener index conjecture for trees states that for any integer n (except for
a finite set), one can find a tree with Wiener index n.
This conjecture has been open for quite some time, and many authors have presented incremental progress
on this problem. In this paper we present further progress towards proving this conjecture—through
the design of efficient algorithms, we show that enumerating all possible
trees to verify this conjecture (as done by all the previous approaches) is not necessary,
but instead searching in a small special family
of trees suffices, thus achieving the first polynomial (in n) time algorithm to verify the
conjecture up to integer n.
More precisely, we
(i) present an infinite family of trees and prove various properties of these trees,
(ii) show that a large number of integers, up to at least 108
(compared with the previous best 104) are representable as Wiener indices of trees in this
succinct family,
(iii) provide several efficient algorithms for computing trees with given Wiener indices, and
(iv) implement our algorithms and experimentally show that their performance is asymptotically
much better than their theoretical worst-case upper bound. 相似文献
15.
16.
We consider products of matrix exponentials under the assumption that the matrices span a nilpotent Lie algebra. In 1995, Gurvits conjectured that nilpotency implies that these products are, in some sense, simple. More precisely, there exists a uniform bound l such that any product can be represented as a product of no more than I matrix exponentials. This conjecture has important applications in the analysis of linear switched systems, as it is closely related to the problem of reachability using a uniformly bounded number of switches. It is also closely related to the concept of nice reachability for bilinear control systems. The conjecture is trivially true for the case of first-order nilpotency. Gurvits proved the conjecture for the case of second-order nilpotency using the Baker-Campbell-Hausdorff formula. We show that the conjecture is false for the third-order nilpotent case using an explicit counterexample. Yet, the underlying philosophy behind Gurvits' conjecture is valid in the case of third-order nilpotency. Namely, such systems do satisfy the following nice reachability property: any point in the reachable set can be reached using a piecewise constant control with no more than four switches. We show that even this form of finite reachability is no longer true for the case of fifth-order nilpotency. 相似文献
17.
18.
19.