Harary图的偶匹配可扩性

对Harary图的偶匹配可扩性进行了研究,得到结论:对于任意的n1,仅当n=2,3时H3,2n是BM可扩图;对于任意的n(n≥3),H4,2n均不是BM可扩图;对于任意的n(n≥3),当n=3,4时,H5,2n是BM-可扩图;当n≥5时H5,2n不是BM可扩图;对于任意的n(n3),r≥6时,Hr,2n是BM-可扩图等等.     

无爪双临界偶匹配可扩图的结构

图G是有完美匹配的简单连通图．称图G是偶匹配可扩的，是指G的每一个偶匹配都可以扩充成为G的一个完美匹配．在本章中，我们得到若干无爪双临界偶匹配可扩图的结构性质。     

蛛网图的偶匹配可扩性(英文)

图G的匹配M是偶匹配,如果G[V(M)]是偶图.图G是k-偶匹配可扩的(1≤k≤(V(G)-2)/2),如果G的每一个基数不大于k的偶匹配都可以扩充为G的一个完美匹配.研究蛛网图的偶匹配可扩性得出的结论是:蛛网图不具有偶匹配可扩性和2-偶匹配可扩性.     

导出匹配可扩偶图的度条件

称简单图Ｇ为导出匹配可扩图，若Ｇ的任一导出匹配均含于Ｇ的完美匹配中。本文给出了导出匹配的可扩偶图的一些度条件。     

Cn×P2的2-偶匹配可扩性

称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V（M）]是偶图称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中为了进一步地研究图的偶匹配可扩性,我们考虑图G的偶匹配数,即图G中最大偶匹配所含的边数,记为BM（G）,我们证明了Cn×P2是2-偶匹配可扩的。     

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

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

关于n—可扩偶图一个极值问题的注记

本文讨论了ｎ－可扩偶图的一个极值问题，证明了任意具有ｐ≥２（ｎ＋１）个顶点、ｑ条边的有完美匹配的偶图是ｎ－可扩的充分条件是ｑ≥ｐ／２（ｐ／２－１）＋ｎ＋１。     

循环图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-偶匹配可扩性的.     

拟轮图的导出匹配可扩性

从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.     

1-可扩偶图的刻划

设G是一个具有二分类(X，Y)的偶图且M是G的一个完美对集。文章证明：G是1—可扩图当且仅当G有如下耳朵分解G=e P1 P2 … Pr使得e∈M并且每个只是起始和终止边都在E(G)＼M中的M-交错路。文章还给出一个有效算法判定一个偶图是否1—可扩图并找出该图的耳朵分解。     

r一致导出匹配可扩张超图及性质

讨论了r一致导出匹配可扩张超图及其性质,并找到了1种寻找边数较少的导出匹配可扩张超图的方法。     

饱和二部图

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

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

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

二分图对集的可扩性

设G是一个连通二分图,G=(X,Y;E),本文主要证明了当|X|=|Y|,若δ(G)≥2n+1(1≤n≤|X|2,n∈N),且对G的任两个距离3的顶点u,v有d(u)+d(v)≥|X|+2n时,G是2n-可扩充的     

直径为2的无爪图的导出匹配可扩性

研究直径为2的无爪图的导出匹配可扩性,得出结论:直径为2的无爪图G是导出匹配可扩的,当且仅当对图G的任意的导出匹配M,|M|≤3,G-V(M)没有奇分支,从而,直径为2的无爪图的导出匹配可扩性是多项式时间可解的.     

二部双圈图的拉普拉斯系数

研究二部双圈图的Laplacian系数,将二部双圈图分为三类,利用α-变换及图的Laplacian特征多项式的计算,得到每一分类中具有较小拉普拉斯系数的图,然后对其Laplacian特征多项式进行比较,得到了阶数固定的二部双圈图中具有最小Laplacian系数的图.     

在加权完全偶图中求2边最优匹配的算法

给出不完全最优匹配的定义,并提出在加权完全偶图中求2边最优匹配的算法,最后举例说明其应用.     

二分图中相互独立的圈

证明了下面的结论：设k≥1是一个整数，G＝（V1,V2；E）是一个二分图，满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1，y∈V2，都有d(x) d(y)≥2k 2，并且δ（G）≥2，则G包含k个相互独立的图。