全國中小學科展

依全國中小學科展屆次查詢

依相關評語查詢

列表著色可約構形之建構法

科展類別

全國中小學科展作品

屆次

第61屆--民國110年

科別

數學科

得獎情形

佳作

學校名稱

臺北市立第一女子高級中學

指導老師

楊宗穎

作者

王嵐;李昀祐

關鍵字

鴿籠原理,可約構形,有向圖

摘要或動機

圖的著色問題為現代數學的一門學問,而列表著色為一般著色問題的推廣,許多研究皆致力在探討各式的充分條件,使得圖可以完成列表著色。在數學歸納法的證明過程中,經常需要利用『可約構形』的概念來化簡圖形,進而確保能完成圖的列表著色。若圖在邊上具有方向性,則稱此圖為有向圖。我們的研究是利用圖在邊上的定向關係,創造一個多變數的多項式,在代數式上運用鴿籠原理,藉著尋求多項式函數值為非零值的可能,證明列表著色方法的存在性,並能有程序性的設計一系列在列表著色中的可約構形與演算法。

050413.pdf

Adobe Reader(Pdf)檔案