完美整数k-匹配和k-因子临界图

本文研究完美整数k-匹配和k-因子临界图的存在性.扩张常数表示图的连通强度,对于正则图,利用扩张常数给出了完美整数k-匹配存在的一个充分条件,这推广了Hamers等人和Cioabǎ等人的结果.此外,对于正则图,基于扩张常数还给出了k-因子临界图存在的一个充分条件.

图的Aα-谱半径与k-匹配数

令G表示为图,图G的k-匹配是一个函数f,它为G的每个边分配{0,1,…, k}中的一个数,使得G的每个顶点v均有Σe~vf(e)≤k,这里的求和表示取遍所有与定点邻接的边e。在本文中,我们探讨了当k为奇数时,图的Aα-谱半径与整数k-匹配数之间的关系。

基于k-匹配的极值五角链

An表示由n个五边形组成的五角链的集合.对任意的An∈An,mk(An)表示An中k-匹配的数目.本文证明了对任意的五角链An∈An及任意的k≥0,mk(Zn2)≤mk(An)≤mk(Zn1),且只有当An=Zn2时,左边等式成立;只有当An=Zn1时,右边等式成立.这里Zn1和Z2n分别为第一类链和第二类链.

星形h多边形cactus的k-匹配与k-独立集

文章在Farrell对六边形cacti的匹配的研究基础上,给出了具有n个多边形的星形h多边形Cacti链的k-匹配与k-独立集多项式的明确表达式。

随机图G(2n,p)中k-匹配的相变性质

随机图G(n,p)模型中有两个参数n和p,n表示图中的结点数,p表示图中任意两个不同结点之间独立生成边的概率。证明了随机图G(2n,p)中存在k-匹配的临界值为p=kn-2。实验分析了随机图G(2n,p)实例中10-匹配和25-匹配以及k=n-1匹配的相变。最后总结出临界函数与匹配的边数和结点数有关系。实验表明,理论与实验一致。

基于GPU实现允许k-差别近似串匹配并行算法

为了在GPU上实现允许k-差别近似串匹配并行算法,并进一步提高在GPU上的算法性能,在综合考虑GPU的存储层次前提下,采取了多种访存优化措施,并提出了避免bank冲突的解决方案。测试结果表明,所用优化措施及方案使算法性能明显提高。

Harary图的k-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等.

步长为1和4的循环图的k-偶匹配可扩性

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配。判定图是否含有基数为k的偶匹配是NP-困难问题,该文主要刻画了循环图C_(2n)(1,4)的k-偶匹配可扩性。

单圈图的k-距离匹配控制数

单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(G)是G的一个k-距离控制集且导出子图〈D〉有完美匹配,则称D是G的一个k-距离匹配控制集.k-距离匹配控制数γkp(G)是G的最小k-距离匹配控制集的势.主要证明了单圈图k-距离匹配控制数的一个重要引理,由此找到了单圈图k-距离匹配控制数的上界,并构造了极图.

2k-点可删的导出匹配可扩图

设G是一个简单图.称G是2k-点可删的导出匹配可扩图,如果对于V(G)的任一满足|S|=2k的子集S,G-S是导出匹配可扩的.给出了2k-点可删的导出匹配可扩图的两个充分条件,证明了这两个条件都是最好可能的.

循环图C_(2n)(1,3)的2-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的.

似星树匹配能的极图

一个图G的能量等于图G的特征值的绝对值。最近Gutman和Wagner提出图G的匹配能定义为■,其中u1,u2,…,un为图G的匹配多项式的根。在此文中,我们主要确定了似星树匹配能的极图。

循环图C_(2n)(1,2n/3)的2-偶匹配可扩性

文章主要刻画了循环图C2n(1,2n/3)的k-偶匹配可扩性,得出对任意的n(n>3),C2n(1,2n/3)是2-偶匹配可扩性的。

几类特殊图的匹配可扩性

如果图G的每一个偶匹配都可以扩充为G的一个完美匹配,则称图G是偶匹配可扩的。论文主要刻画了图Cm×Pn、Pm×Pn和双轮图的匹配可扩性,从而为研究这些图的可扩性奠定了基础。

循环图C_(2n)(1,4)的偶匹配可扩性

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,根据图的k-偶匹配可扩性完全刻画了循环图C2n(1,4)的偶匹配可扩性.

n-正则(n-2)-边可删的导出匹配可扩图

设图G是有2n个顶点的简单图,如果对于E(G)的任一满足|F|=k的子集F,G-F均为导出匹配可扩的,则称图G是k-边可删的导出匹配可扩图.证明了n-正则(n-2)-边可删的导出匹配可扩图只有Kn,n,其中n≠4k,k≥3.

最短时限缺省指派问题的一种解法

将周良泽在 1998年提出的最短时限缺省指派问题转化成赋权二分图的最小权 K-匹配问题。研究了其解的最优性充分及必要条件 ,并给出了适合在图上求解的生长树法及适合在表上直接求解的标号法 ,最后给出一个实例。该解法是一种较简便的算法。

带选择策略的最优分配问题

从图论的观点出发 ,将带选择策略的最优分配问题转化成偶图的 k-匹配问题 ,并用最大匹配、最小费用流的方法分别研究了它的 min- max和 min- sum两个基本模型 。

关于六角蜘蛛图的一些结果(英文)

利用X-多项式、Y-多项式、Merrifield-Simmons指标和Hosoya指标的运算性质,得到了六角蜘蛛图的k-匹配数与k-独立集数的不等关系式,及Merrifield-Simmons指标和Hosoya指标的不等关系式,并刻画了相应的极值图.

基于专家案例推理的板级电路智能故障诊断研究

针对传统专家系统推理机所存在的匹配冲突问题,提出了一种将专家案例推理用于板级电路故障诊断的方法;该方法重点研究了专家案例推理的索引策略和匹配原则,并给出了案例的表示和组织存储方法及案例库的维护措施;根据研究表明,将分层多级索引机制和k-近邻匹配原则相结合,利用专家案例推理对板级电路进行故障诊断,能够解决匹配冲突等瓶颈问题.通过以航空机载电子设备中电源电路出现故障为例,得出专家案例推理具有诊断速度快、精确度高等优点.