论文摘要
作为匹配和拟阵交的共同推广，Cunningham和Geelen在1996年引入了图的路匹配的概念．他们指出许多领域的问题都可以转化为路匹配问题，也就是说，利用路匹配可以解决例如匹配、拟阵、多面体以及代数等很多方面的问题．作为路匹配的应用，他们给出了可匹配集合多面体的强多项式分离算法，并证明了最大路匹配的值就等于给定图所确定的匹配拟阵中顶点集合的秩，同时也等于Tutte矩阵的秩等等．本文共分为六章，第一章着重介绍了路匹配的应用背景以及路匹配自引入以来的主要研究成果，并且在此基础上概述了本文得到的主要结论．第二章和第三章主要是通过最大路匹配来刻画图的结构，在最后的三章中我们考虑了给定图的最大路匹配的大小以及完美路匹配的可扩性等问题．在2004年，Spille和Szego给出了与通常匹配意义下的Gallai-Edmonds分解{A，C，D}类似的一种顶点分解{A1，C1，D1}，并且给出了相应的结构定理．我们已经知道集合A就等于图中所有极大障碍集合的交集．在第二章中，我们将这一著名结果推广到了路匹配的框架中，从而得到了关于A1的一个表达式．在Gallai-Edmonds结构定理中，由D所导出的图的每个分支都是因子临界的（即删去任意一点后都有完美匹配）．对于这类图的刻画在匹配理论中已经得到了．而路匹配分解中的D1所导出的图不一定是因子临界的．因此，在第三章中我们刻画了由D1所导出的图，并且讨论了D1所导出的图中两类分支之间的内在关系．Frank和Szego给出了一般图中有完美路匹配的一个刻画，事实上这个结果是Tutte定理的一个直接推广．但是从这个结果中得到的一个图有完美路匹配的充分条件却非常强，很难满足．因此，在第四章中我们集中考虑了完美路匹配在一般图以及一些特殊图类中存在的条件．对于一般图给出了极集合条件和联接数型条件，并且更进一步地证明了这些联接数型条件在某种意义下是最好的．对于特殊图，我们考虑了正则图和以t+1个顶点的星作为禁止子图的无K1，t图，得到了在这两类图中存在完美路匹配的条件．一个图G=（V，T1，T2；E）的路匹配数val（G）是描述G中最大路匹配大小的一个参数．在第五章中，我们用两种不同的方式给出了val（G）的界．第一个界是用关于联接数b，|V|，和|Ti|的一个函数给出来的，这里i=1，2．并且从这个结果可以得到Woodall关于图的最大匹配所含边数的界．第二个界所考虑的是无K1,t图，我们用关于t，连通度m，|V|，和|Ti|的某个函数给出了val（G）的界．在第四章中，我们已经讨论了一个图有完美路匹配的充分条件．那么如果我们加强这些条件是否就能够使得任意一个值为n的正常路匹配都可以通过某种扩张成为完美路匹配呢?在本文的最后一章中，我们给出了关于路匹配n-可扩的定义，这种定义从本质上讲是匹配可扩的一个推广．我们得到了一个图在顶点数|V|和n+k有相同的奇偶性，或k>n时n-可扩的联接数型充分条件（这里k是图G中端集合的大小），并且说明了这些充分条件在某种意义下是最好的．由此产生的一个推论将Chen关于匹配可扩性中的结果改进到了最好．那么在|V|和n+k奇偶性不同，并且k≤n时，我们说明了在这种情况下图的可扩性与联接数是没有直接关系的．最后我们给出了无K1,t图n-可扩的充分条件．
论文目录
相关论文文献
标签：路匹配论文; 完美路匹配论文; 型结构分解论文; 因子临界图论文; 导出图论文; 正则图论文; 联接数论文; 极集合论文; 路匹配数论文; 路匹配可扩论文;