超立方體最小控制集建構方式的探討

科展類別
臺灣國際科展作品
屆次
2020年
科別
數學
得獎情形
二等獎
學校名稱
臺北市私立復興實驗高級中學
指導老師
陳俊佑
作者
吳映賢
關鍵字
超立方體、最小控制集、同構

摘要或動機

本研究將至多8維的超立方體(hypercube)Qn最小控制集(minimum dominating set)MDS(Qn)建構方式一般化,並藉由同構(isomorphic)的分類討論提出的建構模式之唯一性與否。由文獻得出的各超立方體最小控制集大小γ(Qn)以及已知的控制集形式,並從控制集重複控制的次數R(MDS(Qn )),我們得出Qn的平方圖中最小控制集形成的子圖Qn2 [MDS(Qn )]可能的連通分量(component)數,最後透過Qn層狀圖(layered graph)中各層控制點數的運算,篩選得出可行的建構方式。 研究得出MDS(Q1 )、MDS(Q2)、MDS(Q3)、MDS(Q5)、MDS(Q7)只有一種同構;MDS(Q4)、MDS(Q6)有兩種同構,同時我們發現MDS(Q5)與MDS(Q6)構造上的關聯;Q8的情況較為複雜,我們先是證明了γ(Q8 )=32,並討論MDS(Q8)與MDS(Q7)構造上的關聯,提出了建構MDS(Q8)之方式。


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

檔案名稱 檔案大小 格式
010021.pdf 1 MB Adobe Reader(Pdf)檔案