| 求邻接对集的一个有效算法 |
| |
| 引用本文： | 李德明,刘彦佩. 求邻接对集的一个有效算法[J]. 北京交通大学学报(自然科学版), 1999, 23(2): 5B |
| |
| 作者姓名： | 李德明 刘彦佩 |
| |
| 作者单位： | 李德明 刘彦佩 北方交通大学理学院，北京100044 |
| |
| 摘 要： | 图的一个邻接对集是指由其互不相交的相邻边对构成的边的子集，且去掉这些相邻边对后，所得之图是连通的．本文提供了求最大邻接对集的一个有效算法，并指出此算法可以求图的最大亏格
|
| 关 键 词： | 邻接对集 可增广路 算法 |
An Efficient Algorithm for Finding an Adjacency Matching of a Graph |
| |
| Li Deming,Liu Yanpei. An Efficient Algorithm for Finding an Adjacency Matching of a Graph[J]. JOURNAL OF BEIJING JIAOTONG UNIVERSITY, 1999, 23(2): 5B |
| |
| Authors: | Li Deming Liu Yanpei |
| |
| Abstract: | An adjacency matching in a graph is a matching that each edge in the graph is matched with an adjacent edge if the edges are not in the adjacency matching inducing a connected spanning subgraph. In this paper, an efficient algorithm on finding a maximum adjacency matching of a graph is provided. |
| |
| Keywords: | adjacency matching augmenting walk algorithm |
| 本文献已被 CNKI 等数据库收录！ |
