臺灣國際科展

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

科展類別
臺灣國際科展
屆次
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.


「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
關於二元根樹上的鏈、反鏈、獨立集的計數及極值 5 MB Adobe Reader(Pdf)檔案