匹配理论是图论的核心内容之一.由于得到应用领域的支持，并与其他理论课题发生密切联系，受到众多学者的关注，产牛出许多含义丰富而深刻的理论结果.例如，刻画偶图具有完美匹配的：Hall定理、刻画一般图具有完美匹配的Tutte定理、不具有完美匹配图的Gallai-Edmonds结构定理、求偶图最大权匹配的匈牙利方法、求非偶图最大权匹配的开花算法等，都是影响深远的传世之作.同时关于匹配的一系列研究专题不断涌现出来.例如，匹配多面体、基本图(elementary graph)、因子临界图、完美匹配计数等都成为活跃的研究领域.匹配可扩性-包括k-可扩性、导出匹配可扩性和k-因子临界性-也是其中之一。k-因子临界图和k-可扩图有密切的关系：2k-临界图是k-可扩的：对于每一个连通的非偶图.如果它是k-可扩的，k是偶数，那么它是k-因子临界的。 在k-可扩图、导出匹配可扩图和k-因子临界图的研究工作基础上，考虑到非偶图匹配问题与偶图匹配问题有本质差别的事实，我们提出另外一个新的概念一偶匹配可扩图.称图G的匹配M是偶匹配，是指M关联的顶点集在G中的导出子图是偶图.称图G是偶匹配可扩的(简称BM-可扩的)，是指G的每一个偶匹配都可以扩充为G的一个完美匹配.基于以下两方面的动机，BM-可扩图是值得深入研究的。 一方面BM-可扩图与其他匹配可扩图的关系很密切，构成一个整体：k-可扩的(k=m(G))=>BM-可扩的=>导出匹配可扩的=>1-可扩的=>基本的，其中m(G)是图G的最大匹配的基数.事实上，我们建立的基本定理"BM-可扩图或者是双临界的或者是可均衡分解的"(见第三章)阐明了BM-可扩性的思想渊源可以追溯到因子临界图、双临界图及Gallai-Edmonds分解结构，充分显示出它与经典匹配理论的内在联系.因此，对BM-可扩图的任何研究进展都是对整个匹配可扩性理论的贡献.特别地，揭示从偶图匹配到非偶图匹配的演变规律也是有重要意义的。 另一方面：BM-可扩图在化学图论中有潜在的应用.在量子化学中，一个分子图G的Kekulé结构就是完美匹配M：所谓共振圈就是M-交错圈.共振圈中的匹配实际上是一个偶匹配，它包含于G的完美匹配之中.因此共振圈概念与BM-可扩图有着自然的联系.正因如此，在已知的BM-可扩图中，其Clar指标(两两不相交的共振圈的最大数目)达到最大，可见对应分子结构具有最大可能的谐振能量.从Kekulé结构计数的观点上看，这类分子结构由于完美匹配数目很大，也有良好的稳定性. 在已有的理论中，关于k-可扩图、导出匹配可扩图、k-因子临界图的研究内容.除了基本性质外主要集中在：结构特征、与图参数的关系、特殊图类的刻画、极图问题等.在系统地掌握该领域的文献资料和前沿工作的基础上，本学位论文对于我们提出的新概念 -BM-可扩图的研究也是围绕上述主流课题进行的。 本学位论文主要取得如下五个方面的创新成果： 1.计算复杂性问题 本文证明了判定图G是否含有基数为k的偶匹配是NP-完全问题；判定图G是否BM-可扩的是co-NP-完全问题.这说明有关问题都是困难问题.对于多项式可解情形，给出了偶图、完全多部图、3-正则图等是BM-可扩图的完全刻画和判定算法。 2.结构特征 本文证明BM-可扩图是2-连通的；由Tutte定理得到判定BM-可扩图的充分必要条件；对于删顶点、删边、收缩项点、膨胀顶点等图运算下BM-可扩图的性质，也得到了一些结果.所有这些结果在进一步研究中起到基础作用。 关于BM-可扩图与因子临界图及双临界图的关系，本文证明：如果G是BM-可扩图，那么G或者是双临界的或者是可均衡分解的.如果G是可均衡分解的，那么G-S的每一个分支都是因子临界的，其中S是G的一个极大屏障.另外，对于不是双临界的BM一可扩图G，本文得到这样的"双临界性".如果S是G的极大屏障，那么对于任意的u∈S，v∈V(G)S，G-{u，v}中存在完美匹配.对于不含三角形的可均衡分解的BM-可扩图，给出了完全刻画.这些结果确立了BM-可扩性在匹配可扩性理论中的地位。 关于围长，本文证明：BM-可扩图的围长是3或4.利用韧度，本文给出了BM-可扩图的充分条件；至于必要性，可以构造韧度值为任一给定有理数的偶匹配可扩图。 3.度条件 k-可扩图、导出匹配可扩图和k一因子临界图对与度相关的图参数-最小度、度和、两个顶点度的最大值一都有研究。关于BM-可扩图，本文也进行了相应的研究，给出借助这些度型参数判定BM-可扩性的结果.对于一般图，给出了度和条件、范型条件和最小度条件；对于无爪图，给出了度和条件和最小度条件；对于正则图和正则无爪图，给出了度条件.而且对于这些度型条件：我们都构造图实例说明得到的界是最好可能的.这些条件说明这样一个事实：BM-可扩图广泛地存在于相对稠密的图类之中。 4.正则图的刻画 对于无爪的4-正则导出匹配可扩图，文献中已给出了完全刻画.本文经过较复杂的论证，完全解决了4-正则BM-可扩图的刻画问题：仅有的4-正则BM-可扩图是等部完全偶图K<,4,4>和加强圈梯T<,4n>。 5.极图问题 已有文献完全刻画了极大导出匹配不可扩图、极大非k-可扩图、极大非k-可扩偶图、极大非k-因子临界图、极大和极小k-可扩图(k取1，n，n-1，其中n为图的顶点数).本文给出了极大BM-不可扩图的完伞刻画；找到了三类极大BM-可扩图：偶图图类中的等部完全偶图，完全多部图图类中的偶数个顶点的完全图，加强树梯中的正则加强树梯.对于导出匹配可扩图，原晋江猜想：极大导出匹配可扩的非偶图是仅有偶数个顶点的完全图.作为极大BM-可扩图的正则加强树梯的存在，说明把该猜想限制在BM-可扩图图类上不成立.但是我们证明：对完全多部图以及由它们增加一些边得到的图的图类，对于上述猜想是正确的.关于极小BM-可扩图，我们得到：等部完全偶图和加强树梯是极小BM-可扩图.所有这些极图问题都是在传统意义的边集包含关系偏序下的。 此外，在可达意义偏序下，等部完全偶图不再是极大的.我们证明：完全图可以分别从等部完全偶图和BM-可扩的完全多部图每次增加至多两条边得到，而且得到的中间图都是BM-可扩的.最后,我们初步考虑了给定顶点数的BM-可扩图的边数最小值问题。