扇形圖之生成樹列舉、排位與反排位演算法

Generating Spanning-tree Sequences of a Fan Graph and Ranking/Unranking Algorithms

曾政嘉(Cheng-Chia Tseng)

指導教授 ： 張肇明

國立臺北商業大學/管理學院/資訊與決策科學研究所/碩士(2022年)

摘要

Cameron 等人最近提出了一個演算法，在 O(1) 平均分攤時間列舉扇形圖的所有生成樹。生成樹的列舉滿足樞軸 (pivot) 格雷碼特性，因此連續的樹透過某個頂點旋轉單個邊而不同。他們也提出了使用 O(n) 的時間及 O(n) 空間對列舉中的生成樹進行排位與反排位的演算法。本論文我們首先觀察扇形圖的所有生成樹都可以自然地利用整數序列表示，因此它們的編碼樹具有規律性。然而，我們提出了一個簡單的演算法，根據這些屬性在 O(1) 的平均分攤時間依字典次序列舉其生成樹整數序列。根據字典次序，我們也提出了使用 O(n) 時間及 n + O(1) 空間 (空間的大小略大於n) 的排位與反排位演算法。此外，我們也提出了無迴圈演算法在 O(1) 的時間列舉生成樹整數序列，記憶體空間為3n + O(1)。

關鍵字

生成樹 ； 扇型圖 ； 生成演算法 ； 排位/反排位演算法 ； 平均分攤時間演算法 ； 無迴圈演算法

並列摘要

Cameron et al. [27th Int. Conf. Computing and Combinatorics (COCOON 2021), LNCS 13025, pp.49-60] recently presented an algorithm for generating all spanning trees of a fan graph in O(1)-amortized time. The listing of spanning trees fulflls the so-called pivot Gray code property so that successive trees differ by pivoting a single edge around a vertex. They also presented algorithms for ranking and unranking a spanning tree in the listing in O(n) time using O(n) space. In this thesis, we first observe that all spanning trees of a fan graph can be naturally represented by integer sequences so that their coding tree has properties with regularity. Then, we propose a simple algorithm for generating spanning-tree sequences in lexicographic order in O(1)-amortized time according to these properties. Additionally, based on the lexicographic order, we develop ranking and unranking algorithms in O(n)-time using n+O(1) space (i.e., the size of the space is just slightly larger than n). In addition, we also design a loopless algorithm for generating in O(1)-time using 3n + O(1) space

並列關鍵字

spanning trees ； fan graphs ； generation algorithms ； ranking/unranking algorithms ； constant amortized time algorithms ； loopless algorithms

參考文獻

[1] Bottomley, H.: The on-line encyclopedia of integer sequences, http://oeis.org, Sequence A059929 (2001)

[2] Bogdanowicz, Z.R.: Formulas for the number of spanning trees in a fan. Appl. Math. Sci. 2(16), 781-786 (2008)

[3]Cameron, B., Grubb, A., Sawada, J.: A pivot Gray code listing for the spanning trees of the fan graph. in: Proceedings of 27th International Conference on Computing and Combinatorics (COCOON 2021), Tainan, Taiwan, Oct. 24-26, 2021, LNCS 13025, Springer, Cham, pp. 49-60 (2022)

[4] Chakraborty, M., Chowdhury, S., Chakraborty, J., Mehera, R., Pal, R.K.: Algorithms for generating all possible spanning trees of a simple undirected connected graph: an extensive review. Complex Intell. Syst. 5(3), 265-281 (2019)

[5] Chang, Y.-H., Wu, R.-Y., Lin, C.-K., Chang J.-M.: A loopless algorithm for generating (k,m)-ary trees in Gray code order. Optim. Lett. 15(4), 1133-1154 (2021)