全國中小學科展

關於二元根樹上的鏈、反鏈、獨立集的計數及極值

科展類別

臺灣國際科展

屆次

2003年

科別

電腦科學

學校名稱

臺北市立建國高級中學

指導老師

游森棚

作者

吳宗穎、鄒承孝

關鍵字

二元根樹,計數,極值

摘要或動機

二元根樹是資訊科學上最重要的結構之一,因此其結構的探討就很有價值。在這個研究中,我們探討二元根樹上反鏈(Antichain),鏈(Chain),獨立集(Independent set)計數。在每一個子題之下,我們求出計算反鏈,鏈,獨立集的方法。之後我們求出極值(包括最大跟最小值),並且討論該極值之下所有可能的樹形。此外,我們並討論要列出二元根樹上這些資料(反鏈,鏈,獨立集)所需的演算法。In this paper we enumerate the number of antichains, chains, and independent sets of a binary tree of size n. After that we focus on the extreme values (maximal/minimal). we calculate the extreme values and discuss the possible graphs of trees when achieving these extreme values. Moreover, we offer algorithms for listing all the objects in each extreme case.

關於二元根樹上的鏈、反鏈、獨立集的計數及極值

Adobe Reader(Pdf)檔案