欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
设▽（G）表示最少的点数,这些点去掉后图中无圈（即森林）.称这个数▽（G）为图G的消圈数.通常,确定图的消圈数是NP完全的.Bau和Beineke曾提出以下问题：哪些阶数为n的3正则图G的消圈数满足▽（G）=[（n＋2）/4]？本文回答了这个问题：阶数为n的3正则图G的消圈数满足▽（G）=[（n＋2）/4]当且仅当G是上嵌入的（即以最多两个面嵌入在可定向曲面上）.其次,对于一般3正则图,得出其消圈数的计算公式为▽（G）=γ_M（G）＋ζ（G）,这里γ_M（G）表示图的最大亏格,ζ（G）表示图G的Betti亏数.由此可知,3正则图的最大亏格的计算的多项式算法是存在的,所以3正则图的消圈数的计算也是多项式可解的.
英文摘要：
Let ▽（G） denote the minimum number of vertices whose removal results in an acyclic graph（i.e.,a forest）.Such a number ▽（G） is called the decycling number of graph G.In general,deciding the decycling number of a graph is NP-complete.Bau and Beineke proposed the following question：Which cubic graphs G of order n satisfy ▽（G） =[（n＋2）/4]？ In this paper we solve this problem and show that a cubic graph G of order n has decycling number▽（G） =[（n＋2）/4]if and only if G is upper-embeddable（i.e.,may be embedded in an orientable surface having at most two faces）.Furthermore,we find that the decycling number of a cubic graph G is ▽（G） = γ_m（G） ＋ ζ（G）,where γ_m（G） and ζ（G） are,respectively,the maximum genus of G and the Betti deficiency of G.Since there exists a polynomial time algorithm to find the maximum genus of cubic a graph,there also exists a polynomial time algorithm to find the decycling number of a cubic graph.
同期刊论文项目
同项目期刊论文
期刊信息
位置：