首页 | 本学科首页   官方微博 | 高级检索  
     检索      

图的光滑支架分解
引用本文:李德明,郝荣霞.图的光滑支架分解[J].数学季刊,2001,16(3):75-79.
作者姓名:李德明  郝荣霞
作者单位:[1]首都师范大学数学系,北京100037 [2]北方交通大学数学系,北京100044
摘    要:设G是一个图,A为其边集的子集。G的一个支架分解是(G-A,A),其中G-A是去掉A后的连通图,G的一个光滑支架分解是适合下列条件的支架分解:(1)G-A的每一叶具有连通余树;(2)G-B(G-A)割边集为A,其中B(G-A)为G-A的割边集。本文给出了求一个图的光辉支架分解的一个有效算法。

关 键 词:光滑支架分解  算法    支撑树  连通图  

Finding a Smooth Frame Decomposition of a Graph
LI De-ming,HAO Rong-xia.Finding a Smooth Frame Decomposition of a Graph[J].Chinese Quarterly Journal of Mathematics,2001,16(3):75-79.
Authors:LI De-ming  HAO Rong-xia
Institution:LI De-ming1,HAO Rong-xia2
Abstract:Let G be a graph and A be a subset of the edges of G. A frame decomposition of G is a pair (G-A,A) such t ha t G-A is connected. A smooth frame decomposition of G is a frame decompo sition satisfying the two conditions: (1) Every leaf of G-A has a connected cotree and (2) The set of bridges of G-B(G-A) is A, where B(G-A) is the set of bridges of G-A. An efficient algorithm on finding a smooth frame decompositi on of a graph is provided.
Keywords:smooth frame decomposition  algorthm  bridge  spanning tree
本文献已被 CNKI 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号