| 最大匹配的路变换图 |
| |
| 引用本文： | 刘岩,雷梦霞,黄晓娴.最大匹配的路变换图[J].运筹学学报,2019,23(2):104-112. |
| |
| 作者姓名： | 刘岩 雷梦霞 黄晓娴 |
| |
| 作者单位： | 华南师范大学数学科学学院, 广州 510631 |
| |
| 基金项目： | 国家自然科学基金（No.11551003），广州市科技计划项目（No.201510010265） |
| |
| 摘 要： | 图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.
|
| 关 键 词： | 最大匹配 路变换图 因子临界图 有正赢量的二部图 |
| 收稿时间： | 2017-07-14 |
Path-transformation graph of maximum matchings |
| |
| LIU Yan,LEI Mengxia,HUANG Xiaoxian.Path-transformation graph of maximum matchings[J].OR Transactions,2019,23(2):104-112. |
| |
| Authors: | LIU Yan LEI Mengxia HUANG Xiaoxian |
| |
| Institution: | School of Mathematical Science, South China Normal University, Guangzhou 510631, China |
| |
| Abstract: | The path-transformation graph of maximum matchings of a graph G, denoted by NM(G), is a graph where vertices are maximum matchings of G and two maximum matchings M1 and M2 are adjacent in NM(G) if the symmetric difference of M1 and M2 induces a path (there is no limit for the length of the path). In the paper, we study the connectivity of the transformation graph, and obtain the necessary and sufficient condition that the transformation graph is a complete graph or a tree or a cycle, respectively. |
| |
| Keywords: | maximum matching path-transformation graph factor-critical graph bipartite graph with positive surplus |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
