| 1-可扩偶图的刻划 |
| |
| 引用本文： | 娄定俊,王伟. 1-可扩偶图的刻划[J]. 中山大学学报(自然科学版), 2003, 42(5): 117-118,124 |
| |
| 作者姓名： | 娄定俊 王伟 |
| |
| 作者单位： | 中山大学计算机科学系,广东,广州,510275 |
| |
| 摘 要： | 设G是一个具有二分类(X，Y)的偶图且M是G的一个完美对集。文章证明：G是1—可扩图当且仅当G有如下耳朵分解G=e P1 P2 … Pr使得e∈M并且每个只是起始和终止边都在E(G)＼M中的M-交错路。文章还给出一个有效算法判定一个偶图是否1—可扩图并找出该图的耳朵分解。
|
| 关 键 词： | 偶图 1-可扩图 耳朵分解 M-交错路 |
Characterization of 1-Extendable Bipartite Graphs |
| |
| Abstract: | It is shown that let G be a bipartite graph withbipartition (X, Y) and with a perfect matching M, then G is 1-extendable if and only if G has an ear decomposition G = e + P1 + P2 + … + Pr such that e ∈ M and each Pi is an Malternating path starting and ending with edges in E(G) M . Then a polynomial time algorithm is provided to determine 1-extendable bipartite graph by finding the ear decomposition. |
| |
| Keywords: | bipartite graph 1-extendable graph ear decomposition M-alternating path |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
