圖消圈數的研究

Abstract

所謂的消圈集或反饋點集，是無向圖或有向圖裡的一個點集合，滿足扣掉這個點集合後，圖上沒有圈。一個圖的消圈數是最小的消圈集的數目。 決定一個一般圖的消圈數已經被證明是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.