赋双权二部图中最大权最小权完美匹配

本文涉及的是在赋双权的二部图中求关于第一个权最大的限制下、第二个权最小的完美匹配的网络模型，给出了这一模型的有效算法，并用此算法解决了企业的优化组合分工中的挖潜问题。

二部图中的完美匹配子集权的极小化问题

主要研究了二部图中的完美匹配子集权的极小化问题,针对完美匹配两个子集权的极小化问题,证明了最小权重优先算法SWF的最坏情况界为3/2,并应用一一互换思想,设计了最坏情况界至多为4/3的改进算法.

DNA自组装计算模型求解二部图完美匹配问题

针对二部图完美匹配问题,提出了一种基于DNA计算自组装模型的算法.首先,通过该算法求解了一个具有10个顶点的二部图完美匹配问题的实例,实例中给出DNA计算自组装模型算法所涉及到的DNA Tile的编码设计方案、自组装计算步骤及结果分析;然后,给出了任意二部图完美匹配问题的求解方案;最后,针对DNA计算自组装模型算法解决任意二部图完美匹配问题的时间和空间消耗进行了讨论.结果表明:对任意二部图只需14种Tile类型就能够得到完美匹配.

赋模糊权二部图的最佳匹配

本文建立了赋模糊数为边权的二部图中，据模糊决策来求解最佳匹配的网络模型。

一类二部图的几乎完美匹配数(英文)

图 的一个 匹配称 为几 乎完美 匹配，若 它覆 盖了一 个顶点 以外 的所有 顶点． 本文 给出具 正 Ｓｕｒｐ ｌｕ ｓ二部图有 Ｖ（ Ｇ）＋ １个几乎 完美匹配的两个

平面二部图的完美匹配集合上的有向根树结构及其生成

图的完美匹配或１－因子指覆盖了其所有顶点的独立边集．对含有完美匹配的平面二部图，其所有完美匹配通过某旋转变换形成层次组织结构，可用有向根树或半格表示．

赋权二部图最大匹配的灵敏分析

本文主要从理论上讨论赋权二部图的权的变化对最优解的影响 。

一般图与二部图中完美匹配关于距离无符号拉普拉斯谱半径的存在性

令D(G)=(D_(i,j))为连通图G的距离矩阵,其中D_(i,j)等于顶点v_(i)和v_(j)之间的距离.令η1(G)为图G的距离无符号拉普拉斯谱半径,即距离无符号拉普拉斯矩阵Q(G)=Diag(Tr)+D(G)的最大特征值,其中Diag(Tr)为对角矩阵,Diag(Tr)_(ii)=Σ_(vivj∈E)(G)D_(i,j).在本文中,我们研究图中完美匹配的存在性与距离无符号拉普拉斯谱半径之间的关系,并分别给出关于距离无符号拉普拉斯谱半径的一般图和二部图存在完美匹配的充分条件.

关于极大二部匹配可扩图

若简单图G的每一个二部匹配都可增扩为G的一个完美匹配,则称图G是二部匹配可扩图(简称BM-可扩图)。BM-可扩图广泛地存在于相对稠密的图类之中。讨论树梯图、加强树梯图和正则加强树梯图等图类,并在树梯图图类中确定了正则加强树梯图是加强树梯图中的极大BM-可扩图的刻画。该结论与Wang Xiu-mei一起给出了三类极大BM-可扩图的完全刻画。

导出匹配可扩二部图度和条件的改进

研究并改进了导出匹配可扩二部图的度和条件.主要结论如下:若图G是一个有二部划分(A,B)的二部图,且|A|=|B|=n=3k+1(k≥2),如果对图G中任意不相邻的顶点u和v,有d(u)+d(v)≥4k+1,那么图G是导出匹配可扩的,并且该结果是最佳可能的.

基于有权二部图模型的武器目标分配

武器-目标分配(WTA)是多平台武器系统指挥控制的核心环节之一。针对常用的智能优化算法在进行分配问题求解时存在着收敛速度慢、寻优精度差等不足,提出采用有权二部图模型对问题进行刻画,并结合KM算法进行求解。针对复杂的多重分配问题,提出了一种匹配度矩阵的扩展形式,将武器与目标之间的匹配度进行统一表示。仿真实验结果验证了算法的有效性。

一种符合二部图的船舶运输神经网络算法

运用神经网络优化算法 ,对一种符合二部图最大权匹配的船舶运输线路进行了优化计算 ,仿真计算表明其结果是正确的 ,为船务公司的生产决策提供了定量依据 .此算法表明 。

饱和二部图

没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X■V(G),Γ(X)表示V(G)中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=(U,W)是饱和的当且仅当(a)存在唯一X■U,使得X>Γ(X),X-1>Γ(X)且G的导出子图G[X∪Γ(X)]是完全二部图;(b)G的导出子图G[(U-X)∪(W-Γ(X))]是完全二部图,且满足U-X+1=W-Γ(X);(c)U-X中每个顶点与W中的每个顶点都相邻,且X∪(W-Γ(X))是图G的一个独立集.

最大权完美匹配的“原始—对偶”算法

给出了利用"互补松弛原理"以及"原始—对偶原理"在一个完全赋权二部图G=(X,Y,E,ω),ω≥0,|X|=|Y|=n中寻找最大权完美匹配的算法和过程.

局部颜色特征在基于内容的图像检索中的应用

全局颜色直方图是基于内容的图像检索中使用最广泛的特征之一。然而 ,它不包含颜色的空间分布关系 ,因此不同的图像可能具有同样的颜色直方图。采用图像分块的局部直方图方法考虑了颜色的位置信息 ,但却不具有旋转、平移不变性。文中利用分块颜色矩 ,借助带权二部图的最小完美匹配提出了一种新的相似度量方法 ,既考虑了颜色的空间分布关系 ,又具有旋转、平移不变性。

均衡二部图中的M-2-因子

设G=(X,Y)是一个二部图,若|X|=|Y|,则称G是一个均衡二部图,文章证明了设G是2n阶均衡二部图,对任意正整数k≥2,若n≥4k-3,且最小度δ(G)≥n+2(k-1)2,则任给G的一个完美匹配M,G中存在一个包含M的所有边的恰含k个分支的M-2-因子。

几乎导出匹配可扩图的一些度条件

目的:研究图的完美匹配与几乎导出匹配可扩性的关系,研究无爪图是几乎导出匹配可扩图的度条件。方法:利用无爪图导出匹配的性质和几乎导出匹配可扩图的定义,以及n-可扩图度和条件的Plummer定理,推导证明度条件。结果:得到了几乎导出匹配可扩无爪图的度条件,研究了二部图的几乎导出匹配可扩性。结论:若图G是一个顶点数为2n-1的无爪图,如果对图G中任意不相邻的顶点u和v,有d(u)+d(v)≥2n+1,那么图G是几乎导出匹配可扩的,并证明了不存在几乎导出匹配可扩的二部图。

基于高校排课系统中的图论问题研究

文章针对高校排课系统的现状,转化教师、班级、教室之间的关系为集合关系,然后,从中建立两个二部图模型来解决:教师与上课班级的二部图;每节课与教室的二部图。第一个问题转化为求二部图最小匹配数,第二个问题转化为求二部图中渗透集合每个点的一个匹配。

二部图匹配强迫数的谱

改进了Riddle的尾点法,得到自然数k属于二部图匹配强迫数谱的必要条件,给出了二部图的最小强迫数等于一个颜色集所有规范序最小尾点数的充要条件。

一类非匹配分配格

讨论了一类含有一个割点的有限分配格,给出了一类非匹配分配格:当m,n≥3时,m+n型有限分配格L是非匹配分配格.