标题: 图消圈数的研究
Decycling Number on Graphs and Digraphs
作者: 连敏筠
Lien, Min-Yun
傅恒霖
Fu, Hung-Lin
应用数学系所
关键字: 消圈数;反馈点集;外平面图;格子图;广义迪布恩有向图;广义考茨有向图;decycling number;feedback vertex number;outerplanar;grid;generalized de Bruijn digraph;generalized Kautz digraph
公开日期: 2013
摘要: 所谓的消圈集或反馈点集,是无向图或有向图里的一个点集合,满足扣掉这个点集合后,图上没有圈。一个图的消圈数是最小的消圈集的数目。
决定一个一般图的消圈数已经被证明是NP 完备(NPcomplete),甚至在平面图,二部图以及完美图中,找它们的消圈数的复杂度也不会降低。
在图上破坏圈的问题,一开始是应用在组合设计电路。接着也发现可以应用在作业系统中预防死结、约束补偿问题、人工智慧上的贝斯推论、完全控制同步分散式系统、在光学网路上布置变波器,以及在超大型积体电路的晶片设计。
在这篇论文中,我们讨论了在有向图及无向图的消圈数。在无向图中,我们考虑了外部平面图和格子图。对于第一类图,我们利用圈包装数来刻划消圈数,对于格子图,我们改善了已知结果,使得上下界更靠近,在某些群组中,我们得到了消圈数的确切值。在有向图中,
我们考虑了广义考茨有向图以及广义迪布恩有向图,我们给了一个有系统的方法来获得消圈集,进而得到消圈数的上界,这个方法对所有的有向图都是可行的。
A set of vertices of a graph or an digraph whose removal induces an acyclic graph is referred as a decycling set, or a feedback vertex set, of the graph. The minimum cardinality
of a decycling set of a graph G is referred to as the decycling number of G.
The problem of determining the decycling number has been proved to be NP-complete for general graphs, which also
shows that even for planar graphs, bipartite graphs and perfect graphs, the computation complexity of finding their decycling numbers is not reduced.
The problem of destroying all cycles in a graph by deleting a set of vertices originated from applications in combinatorial circuit design. Also, it has found applications in deadlock prevention in operating systems, the constraint satisfaction problem and Bayesian inference in artificial intelligence, monopolies in synchronous distributed systems, the converters’placement problem in optical networks, and VLSI chip design.
In this thesis, we study the decycling number of graphs and
also digraphs. The graphs we consider are outerplanar graphs
and grid graphs. For the first class of graphs, we characterize their decycling number by way of the cycle packing number and for grid graphs, we improve the known results to obtain either tight bounds or exact values. On digraphs, we consider generalized Kautz digraphs and generalized de Bruijn digraphs. Mainly, we use a novel idea in which we find a sequence of subsets of vertex set satisfying certain conditions and then obtain a decycling set. This provides an upper bound of the decycling number of digraphs we consider. Note that this idea can be applied to find the decycling set of general digraphs.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079622809
http://hdl.handle.net/11536/74427
显示于类别:Thesis


文件中的档案:

  1. 280901.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.