Chinese Quarterly Journal of Mathematics ›› 2001, Vol. 16 ›› Issue (3): 75-79.

Previous Articles     Next Articles

Finding a Smooth Frame Decomposition of a Graph

  

  1. 首都师范大学数学系 北京100037,北方交通大学数学系 北京100044 
  • Received:2000-06-03 Online:2001-09-30 Published:2024-06-04
  • About author:LI De-ming(1968-),male,native of Liaocheng,Shandong,an associate professor of Capital Normal University,engages in specialization of combinatorics and optimization;HAO Rong-xia(1965-),female,native of Beijing,an associate professor of Northern Jiaotong University,engages in specilization of combinatorics and optimization.

Abstract: G是一个图 ,A为其边集的子集 .G的一个支架分解是 (G -A ,A) ,其中G-A 是去掉A后的连通图 ,G的一个光滑支架分解是适合下列条件的支架分解 :( 1 )G-A的每一叶具有连勇余树 ;( 2 )G-B(G -A)的割边集为A ,其中B(G-A)为G-A的割边集 .本文给出了求一个图的光辉支架分解的一个有效算法. 

Key words: 光滑支架分解, 算法, 桥, 支撑树,  ,

CLC Number: