中山大学学报(自然科学版)2003，Vol.42Issue(5)：117-118,124,3.
1-可扩偶图的刻划
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.关键词
偶图/1-可扩图/耳朵分解/M-交错路Key words
bipartite graph/1-extendable graph/ear decomposition/M-alternating path分类
数理科学引用本文复制引用
娄定俊,王伟..1-可扩偶图的刻划[J].中山大学学报(自然科学版),2003,42(5):117-118,124,3.基金项目
国家自然科学基金资助项目(10071076) （10071076）
