偶圈对完全图最小覆盖的若干同余类

完全图K,的m-圈覆盖是指一个序偶(V,D),其中V是K的顶点集,D是一族长为m的圈,使得K1的各边至少在D的一个圈巾.完全图的m-圈覆盖问题研究的关键在于确定最小覆盖的覆盖数.提出了完全图的最小圈覆盖的覆盖数的下界;进一步地直接构造了v ∈|m,m+1,m+2,2m-2,2m-1|时的最小m-圈覆盖.最后,运用递归构造的方法,把顶点数v的研究范围归结到区间[m,3m-1]中的部分数值上来.     

一种最大化传感网络覆盖率的移动辅助部署算法

研究了使用移动传感器提高传感网络覆盖率的问题,提出了一个基于二部图匹配的移动传感器部署算法．设目标区域可以划分成多个小区域或网格,首先把初始网络描述成一个二部图G,G的顶点集合由移动节点集合和需要覆盖的网格集合组成．如果某个移动节点可以覆盖某个网格,则它们之间存在一条边．衡量移动的花费可以使用移动的距离、消耗的能量或者跳跃的次数等．对构造的二部图G求它的最小花费的最大匹配基,则该匹配基对应着一个最优的移动方案,按此方案部署的网络覆盖率最大且总的移动花费最小．     

求偶图最大匹配的矩阵算法

深入研究了偶图与其简化邻接矩阵之间的关系，提出了(0，1)—矩阵的无关元对角形概念，利用此概念给出了定理“任一(0，1)—矩阵的项秩与线秩相等”的一种直接简单证明，得到了判断(0，1)—矩阵的无关元集为最大无关元集的充要条件。最后给出了寻找偶图最大匹配的算法——矩阵算法，该算法与匈牙利算法比较具有较高的运算效率和易于在计算机上实现等优点。     

求图的最小顶点覆盖集的一个近似算法

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.     

基于语义的发布订阅系统匹配算法研究

结合事件/订阅本体模型,提出了一种高效、基于语义的事件/订阅匹配算法,称为多维索引匹配计数(MIC)算法.将事件和订阅表示成资源描述框架(RDF)图和RDF图模式.根据RDF订阅图模式的特点,采用多维哈希表和二叉排序树分别对RDF订阅图模式中弧和顶点对的概念类型约束,以及谓词条件约束建立多层索引,以加速订阅图模式中弧和顶点对的匹配.并利用订阅图模式之间的概念类型约束、谓词条件约束的覆盖关系减少重复匹配.实验结果表明,该算法的匹配效率优于已有的图模式匹配算法,适合大规模发布/订阅应用的需求.     

矩阵论中的图论匹配法

G.Birkhoff用代数的方法证明了如果一个矩阵是双随机矩阵,则它能表示成置换矩阵的凸线性组合.设G是具有两分类(X,Y)的二部图,则G中含有饱和X中的所有顶点的匹配M的充分必要条件为:对(A)S(∈)X,有dG(S)≥|S|.文章借助上述二部图的匹配思想,给出这一结论的图论证明.     

图的星色数的两个结果

图G的星染色是图G的正常点染色,使得图G中没有长为3的路2-染色.通过应用概率方法中的非对称局部引理,证明了任一最大度为Δ的图的星色数χs（G）≤48Δ3.通过应用第一矩量原理和Markov不等式,证明了对任一有n个顶点的最大度为Δ的图G,其星色数χs（G）≤nΔ.     

PE-匹配图的可分性

为了得出一类密度矩阵的可分判据研究了特殊图,利用图理论、拉普拉斯矩阵性质、部分转置正判据、图上顶点与其部分转置图上对应顶点之间的度数关系,分别给出了完全纠缠(perfect entangled,PE)匹配图在C~pC~q与C~3C~4量子系统中的可分判据.证明了在C~pC~q量子系统中,若n=pq个顶点上的PE-匹配图的部分转置不是PE-匹配的,则该图的密度矩阵是纠缠的,否则其部分转置是非负(positive partialtranspose,PPT)的;并给出了C~3C~4系统中n=3×4个顶点上的PE-匹配图的密度矩阵可分的充要条件是该图的部分转置也是PE-匹配图.     

围长为4的无7-和8-圈的平面图的3-选色

图G的选色数,记为XL(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在图G顶点的一个正常着色.文章证明了每个围长至少为4且不含7-圈和8-圈的平面图是3-可选择的.     

平面格子图P_m×P_n的最小填充

一个图的最小填充数就是确定顶点的一个标号顺序,按此顺序消去顶点时最少的添加边数.格子图是实际中遇到最多的一类稀疏图.利用图的分解定理和约化准则,讨论了平面格子图PmPn的最小填充,确定了m=4,5,6时的填充数表达式和它的一些界.     

全制约数的上界

设Ｇ＝（Ｖ，Ｅ）是无孤立点的简单图．设Ｔ是Ｖ的子集，如对任意Ｕ∈Ｖ，存在ｕ∈Ｔ使得ｕｖ∈Ｅ，则称Ｔ为Ｇ的全制约集．全制约集的最小基数称为Ｇ的全制约数，记作γｔ（Ｇ）．本文证明了如Ｇ是阶数ｎ≥３，最小度至少为２的连通图，则γｔ（Ｇ）≤４「（ｎ＋ｌ）／７」     

图与它的补图的匹配多项式

指出了图G是匹配唯一的当且仅当它的补图G是匹配唯一的 并给出了一个二分图G与它的完全二分补图G的匹配多项式之间的关系     

基于表象式语义网络的图匹配算法

提出了一种在表象式语义网络中的查找方法,表象式语义网络问题的求解一般都是通过图匹配实现的,首先根据待求解的问题的要求构造一个带变量节点的语义网络,然后与计算机视觉系统中己存储的语义网络进行图匹配。当语义网络中的询问部分与系统中的语义网络图匹配后,则与询问部分匹配的事实就是问题的解。图匹配问题可以通过构造一个图的附属数据结构来完成,这个附属数据结构也称为相连图(association graph),对于两个图G=(V,A)以及G′=(V′,A′),构造相联图G″=(V″,A″),也就是说,V″是所有可能节点匹配对的集合,A″是所有相容节点匹配的集合。这相当于在相联图中寻求一个最大的基团(clique),其中基团定义为G″的完全连通的一个子图。最大基团满足其节点集合不是任何其他基团节点集的适当子集。     

关于最小度至少为3的图的全控制数

设G是一个没有孤立点的简单图.G的顶点集的一个子集S是一个全控制集,如果G的每个顶点都相邻于S中的某个顶点.图G的全控制数,用γt(G)来表示,是G的全控制集中的顶点数最少的全控制集的顶点数.证明了如果G是一个最小度至少为3的图,那么γt(G)≤n/2.从而证明了Favaron, Henning, Mynhart和Puech提出的一个猜想成立.     

一种公平的路边基站下行业务调度算法

To improve the fairness performance of the downlink traffic scheduling algorithm, a network flow based downlink traffic scheduling algorithm is proposed for the roadside unit (RSU) in vehicular networks. In the proposed algorithm, a bipartite graph is constructed firstly, where the node set is composed by the vehicle set and the timeslot set. At any given timeslot if a vehicle can communicate with the RSU, then an edge between the given timeslot and that vehicle is added into the edge set. Next, a flow network graph is constructed based on the bipartite graph by adding a virtual source node and a virtual sink node. By applying the conventional minimum cost maximum flow algorithms, a minimum cost maximum flow can be computed, which is converted to the fair traffic scheduling strategy. Simulation results show that, when the total vehicle requirements are maximized, compared with the existing algorithms, the fairness performance of the proposed algorithm is improved by 116.4％ in the offline case, and by 25.9％ in the online case.     

混合图有向树集直积生成

将混合图G分解成二分图G(v1)和G(v2 )以及离集Ec,分别生成二分图G(v1)和G(v2 )的k-树集 (k=1,2 ,… ,m) ,并给出了消除伪树的方法 .在此基础上 ,应用直积运算原理建立了生成混合图全部有向树的二分图公式 .该方法具有较好的系统性和直观性 ,并且无伪树成分 ,应用该方法可以生成二分图G(v1)和G(v2 )的有向k -树集 ,并能扩大计算机所能拓扑分析的电网络规模 .     

高度不正则图的全着色

图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。     

完全二部图Km,n的广播数rn（Km,n）

利用图的顶点之间的距离与多水平标号的最大-最小值原理,依据顶点排序累积距离最大作为优化多水平距离标号的衡量标准,证明了完全二部图Km,n的广播数的计算公式rn（Km,n）=m＋n。修正和填补了图的多水平距离标号研究领域的相关问题。另外,图的标号在科学技术和工程领域中有广泛的应用,同时又是图染色理论的推广,所以有一定研究价值与应用前景.     

关于图是[a,b;m]-均匀图的一个邻域条件

设G是一个n阶的图,并设a和b是整数,使得1≤a＜b,以及δ(G)是G的最小度.证明了:如果δ(G)≥a 1,n≥2(a b)(a b-1)/b,以及ING(x)UNG(y)l≥an/(a b-1) 2对G的任意两个不相邻的顶点x和y都成立,那么G是一个[a,b;m]-均匀图.