有向二部图中的独立有向6-圈

证明了若有向二部图D=(V1,V2:A)的最小度至少为5k,则D有k个顶点不交的独立有向6-圈.其中 |V1|=|V2|=3k, k为整数.     

二部图匹配强迫数的谱

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

饱和二部图

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

饱和二部图

没有完美匹配的二部图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的一个独立集.     

k-连通图中生成树和完美匹配上的可收缩边

给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2+1条可收缩边。     

二部图的完备匹配及其实际应用举例

二部图的完备匹配的定义,二部图存在完备匹配的两个充分必要条件,求二部图的完备匹配的算法,二部图的完备匹配的实际应用.     

二部图匹配的一个判别条件

根据Hall定理,二部图G=(V1,V2;E)有一个浸润V1匹配的充要条件是:SV1,N(S)∩V2≥S,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数。当V1中的顶点数较多时,用该条件判定较为困难。本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题。     

均衡二部图中的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-因子。     

二部图最大匹配的快速动态优化算法

建立了二部图C=（V，U，E）的二级优先匹配规则，在此规则下，用改进的深度优先搜索对匹配算法进行改进，使得算法能够根据连通分量的个数动态优化算法的性能，使动态最大匹配算法的时间复杂度提高到0（max（｜V｜，｜E｜，m｜E｜））．     

6连通图完美匹配上的可收缩边

采用分类讨论的方法,研究了6-连通图中可收缩边在完美匹配上的分布情况,得到了如下新结果.设G是阶大于12的6-连通图,M是G的一个完美匹配,若图G的任意断片的阶都大于3,则M上至少有2条可收缩边.     

完美匹配单圈图的维纳指数

主要研究单圈图的维纳指数的性质.给出阶数为2β的完美匹配单圈图的维纳指数下界,并刻画了达到下界的所有极图.     

完美T形树的匹配唯一性

研究了完美T形树T（l1,l2,l3)的匹配唯一性，给出了其匹配唯一的充分必要条件，定理A 设G=T（l1,l2,l3)是T形树，若l1,l2,l3至少有一对相等，则G必匹配等价于一类Q∪P型图。定理B 设G=T（l1,l2,l3)是完美T形树，则图G匹配唯一的充分必要条件是l1,l2,l3互不相等。     

多部图的导出匹配可扩性

k-部图G指图的顶点集V(G)被剖分成k个子集,使每一条边所关联的两个顶点不在同一个子集之中.主要研究了完全多部图的导出匹配可扩性,给出了完全多部图是导出匹配可扩图的充要条件.     

三部图的K3-匹配问题

文章就三部图的匹配问题进行了研究,描述了K3 匹配的定义,提出2-匹配的概念,给出三部图存在K3 匹配的充要条件及有关三部图的2-匹配的性质,为解决复杂的指派问题奠定了一定的理论基础。     

多部图的最大匹配算法

匹配理论是图论中一个重要的分支,已被广泛地应用于许多领域,如组合优化、线性规划、人工智能和矩阵论等.给出一个求解多部图的最大匹配算法,并用仿真例子说明其实用性和有效性,此算法为解决复杂的指派问题开辟了新途径.     

四类图完美匹配的计数公式

用划分,求和,再递推的方法给出了四类图完美匹配数目的显式表达式.所给方法可以计算出许多二分图所有完美匹配的数目.     

正盈量二部图的最大匹配数下界的紧性

无向简单图G的亏度（deficiency）是未被最大匹配所覆盖的顶点数；一个二部图G（A，B）具有正盈量（posidve surplus）（对A而言）当且仅当对A的任何非空集合X所包含的顶点数一定小于其邻集所包含的顶点数。对具有正盈量的二部图，刻画了其当亏度def（G）给定时达到最大匹配数下界的二部图，从而验证了此类二部图最大匹配数下界的紧性。     

存在完美匹配4正则连通图的分类

本用Tutte定理对存在完姜匹配的4正则连通图给以明确分类,并由此得出关于4正则连通图完美(极大)匹配的一些重要性质．