本论文分如下十章： 1、最大匹配图。 2、完全匹配图。 3、图的与匹配数有关的结构。 4、关卡拟阵图。 5、图的最大关卡集。 6、一类三次图上的Cayley图。 7、匹配可扩图的结构。 8、n—可扩图的一些性质。 9、一类Cayley图模型的一些性质。 10、拟n—可扩图。 本文仅讨论有限图，除第6章外均为简单图。所用的记号和定义除特别声明外均遵从文[1]。 1、@最大匹配图。 最大匹配图是我们于1998年6月在文[9]中提出的新概念。这个概念与1998年10月在文[10]中提出的匹配图相同。到现在止，关于这方面的论文仅有两篇。 设G是一个简单图和Μ={M：M是G的最大匹配}。我们定义如下的一个新图Μ（G），它的顶点集是Μ，边集是{M₁M₂：|M₁-M₂|=1，M₁，M₂∈Μ}。Μ（G）被称为关于G的最大匹配图。D（G）表示V（G）的一个子集，它的每一个点至少有一个最大匹配不覆盖它。A（G）是V（G）-D（G）的一个子集，它的每一个点至少和D（G）的一个点相邻。最后设C（G）=V（G）-A（G）-D（G）。在第一章里，我们讨论了Μ（G）的一些性质。主要结果是：如果在G[C（G）]中存在m_c个完美匹配，则Μ（G）有m_c个连通分支且这m_c个连通分支是同构的。 2、完全匹配图。 一个图G被称为一致可扩的如果它的每一个极大匹配是一个最大匹配。一个一致可扩 图被称为随机可扩的如果它有一个完美匹配。一个没有完美匹配的连通图，它是一致可扩 的充分必耍条件在文门中已经解决了。一个连通图是随机可扩的充分必要条件在文｛11中＿也已经解决。在第二章中，我们提出了一个新的定义，即，一个图C被称为完全可扩的 如果对于 VK)的每一个子集 S；它的导出子图 G间是一致可扩的。在这章中，我们获得 了：一个图G是完全可扩的充分必要条件是G的每一个连通分支是一个完全图或是一个 完全二部图。 3、图的与匹配数有关的结构。 在图G中任意一个最大匹配的基数称为G的匹配数，记作叫G)。图G的亏量，记 作def（），定义由def（）＝IV（G）l—2。（G）．V闷)的一个子集X称为一个关卡集如果 def（—X）＝def（）＋fXI。V（G）一个子集X称为一个障碍如果co（G—X）＝def（）＋以l， 其中coK)表示G的奇分支数。c（D（G））表示D厂)的导出子图的分支数。在第三章第2节 中我们获得下面的结果。（1）设G是连通的和不完全的，则对于pEV闷)和、QE（G）， 。（G一卜，u｝）＝。（G）一1的充分必要条件是（a）G［A（G）l是完全的和 A（G）的每一个点和 C（G） 的每一个点相邻，｛hi C（D（G））一 IAK)卜二和（C）g E D（G－。）对于 y E C（G）。（2）设 GM＆il的和不完全的，则。（G－卜州一（G）－2对于x，gEV（o和。gd趴o的充 分必要条件是 G 2 K，l，n，其中。三 2。在第三章第 3节中我们获得下面的结果。N）设 G 是一个包含一个基数为．的独立集的简单图，其中d三2。如果对于G的每一个基数为i 的独立集都是G的一个关卡集，那么G有一个完美匹配。（2）设G是一个包含一个基数 为6的独立集的连通简单图，其中i22。则对于G的每一个基数为－的独立集X都是G 的一个关卡集的充分必要条件是G＝（队m是一个二部图及仰二肿！三入和对于每一个 Y二叫＊＝。（l三。引－1），门厂）卜仰一丞＋；；；＋二。在第三章第奥节中我们获得下面的 结果。＊）设G是一个包含一个基数为j的独立集X的连通简单图，其中i 2 2。则对于 G的每一基数为－的独立集 X都是 G的一个障碍的充分必要条件是 G一（U W）是一个二 部图及仰叫叮卜i，和对于每一个YGUm＝in（ISmSt一1），山Y)I三。十1。 4、关卡拟阵图。 图G被称为双因子临界的如果它至少包含一条边和对于G的每一对不相同的顶点。和 9，G一。一。有一个完美匹配。空集是一个关卡集。关卡集子集是关卡集。设X和Y是G 的两个关卡集及厂＞IXI。可能存在一点 y E Y—X使得 X U ｛fi｝是一个关卡集。也可能 不存在。在第四章中我们讨论了存在的图类。为此我们给出了如F的概念。设I＝＝《S：S 是G的一个关卡集)。如果M（V（G），工）是一个拟阵，则称G是一个关卡拟阵图。在第四 章中我们研究了关卡拟阵图的一一些性质。主要结果是：（二）设G是一个简单图。则G是 一个关卡拟阵图的充分必要条件是C（G）＝0或出C（G）］的每一个连通分支是双因子临界 的。－ 5、图的最大关卡集。 2 极大关卡集不一定是最大关卡集。在第五章中我们d论1”罔的最大关卡集。l；面的结 果被获得：（）设G是一个简单罔和xE＊IG)l)口(?