| 图的路匹配 |
| Alternative Title | Path-matchings of graphs
|
| 晏静之 |
| Thesis Advisor | 张和平
|
| 2008-05-20
|
| Degree Grantor | 兰州大学
|
| Place of Conferral | 兰州
|
| Degree Name | 博士
|
| Keyword | 路匹配
完美路匹配
Gallai-Edmonds 型结构分解
因子临界图
D1导出图
正则图
无 K1,t图
联接数
极集合
路匹配数
|
| Abstract | 作为匹配和拟阵交的共同推广, Cunningham 和 Geelen 在 1996 年引入了图的路匹配的概念. 他们指出许多领域的问题都可以转化为路匹配问题, 也就是说,利用路匹配可以解决例如匹配、拟阵、多面体以及代数等很多方面的问题. 作为路匹配的应用, 他们给出了可匹配集合多面体的强多项式分离算法, 并证明了最大路匹配的值就等于给定图所确定的匹配拟阵中顶点集合的秩, 同时也等于 Tutte 矩阵的秩等等. |
| Other Abstract | As a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings in 1996. They showed that problems in many fields can be transformed into path-matching problems. In other words, by using path-matchings many problems in matchings, matroid, polyhedron and algebra can be
solved. As the applications of path-matchings, they developed a
strongly polynomial separation algorithm for the matchable set
polyhedron, and proved that the maximum value of a path-matching is
the rank of vertices set in the matching matroid determined by some
given graph, and is also equal to the rank of an Tutte matrix, etc. |
| URL | 查看原文
|
| Language | 中文
|
| Document Type | 学位论文
|
| Identifier | https://ir.lzu.edu.cn/handle/262010/224630
|
| Collection | 数学与统计学院
|
Recommended Citation
GB/T 7714 |
晏静之. 图的路匹配[D]. 兰州. 兰州大学,2008.
|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
