共查询到14条相似文献,搜索用时 15 毫秒
1.
本文给出一种求解任一具有n个顶点的有限图G的极大独立集和独立数的代数计算方法.该方法是通过将求解G的极大独立集问题加强为对每个1≤k≤n求解G的k-独立集问题来给出的.首先证明了G中k-独立集的存在性等价于一个多元多项式方程组的解的存在性,使得可以通过使用多项式理想的Grbner来判断所得方程组解的存在性并进一步求解方程组.由于k-独立集存在时只有有限多个,得到的Grbner基构成的方程组是很容易求解的三角形方程组,G的极大独立集和独立数在求解最多n个方程组即可得到.最后,通过实例验证了代数计算方法的有效性. 相似文献
2.
在当前无线传感器网络的相关研究中,虚拟骨干网的构造引起广泛的关注.通过引进虚拟骨干网来设计路由协议,使得路由更加可靠和高效,从而减少广播风暴.无线传感器网络中具有容错功能的虚拟骨干网的构造可转化为圆盘图中的最小 k-连通 m-控制集问题.本文研究了具有不同传输半径的双向圆盘图中的最小 k-连通 m-控制集问题,给出了一个构造最小 k-连通 m-控制集的多项式时间近似算法,理论分析表明该算法具有较好的近似比.最后,在不同的网络拓扑上进行了仿真实验,仿真结果进一步验证了算法的有效性. 相似文献
3.
4.
5.
6.
关于图的分数k-可扩性的若干结果 总被引:1,自引:0,他引:1
一个图称为是分数k-可扩的,若图G含有k条边的对集且对图G的任意一个k条边的对集M,都存在G的一个分数1-因子Gh,使得对任意的e∈M有h(e)=1.我们研究了分数k-可扩图的特征,给出了带有某些约束的分数k-可扩图存在充分条件,以及极大分数k-可扩图的特征. 相似文献
7.
ID-临界因子图的度和条件 总被引:1,自引:0,他引:1
本文研究ID-因子临界图的度和条件,得到使得图G是ID-因子临界图的任意两个不相邻的顶点的度和的下界,同时说明这些结果是最好可能的。 相似文献
8.
本文讨论了由自相似集生成图递归集的算法。利用辅助函数迭代系,针对压缩率的为整数的倒数和数字集为有理数的自相似集,给出了一个新的算法,使得所生成的图递归集满足强分离条件。 相似文献
9.
10.
11.
12.
研究了可分无限维复Hilbert空间中框架、ω-独立框架以及Riesz基之间的关系,得出框架膨胀的充分条件以及Riesz基膨胀的充要条件. 相似文献
13.
针对大规模图集的子图查询问题,给出了一种基于节点与决策模式映射(NDFM)的索引结构——NDFM-Index,并在此索引结构的基础上提出了一种图集的子图查询算法。NDFM-Index利用图中关键节点所携带的结构信息以及邻居的标号分布,与决策模式形成映射,从而不通过枚举直接得到查询图所包含的索引模式,得到更小的候选集。理论与实验的分析结果表明,该算法不但能避免索引筛选过程中对查询图子图的枚举过程,而且能显著地减小候选集尺寸,进而大大降低查询图与候选集之间的子图同构测试次数,提高查询效率。 相似文献
14.
《中国计量学院学报》2018,(1):105-109
令γ_(LR)(G)表示图G的误报容错支配数,G×H表示图G和图H的笛卡尔乘积.文章参考已有误报容错支配数知识及笛卡尔乘积图P_m×C_n的相关结论,研究确定了路与圈笛卡尔乘积图P_m×C_n(m=3,4)的误报容错支配数,并给出n≥5时的精确值. 相似文献