臺灣國際科展

m×n圖改造成一座森林的探討

科展類別
臺灣國際科展作品
屆次
2021年
科別
數學
得獎情形
青少年科學獎
學校名稱
臺北市立建國高級中學
指導老師
黃世穎;褚雪惠
作者
蘇庭昀
關鍵字
m×n圖、森林、連通圖
備註
大會獎 一等獎;美國ISEF正選代表

摘要或動機

本研究試圖找出一些策略,以了解在mxn的格狀街道中,最少應該放入幾個吸螞蟻的裝置,便保證能抓到所有螞蟻。這問題等價於在圖G(m,n)中,最少應放入幾個紅點後,便能使G中的所有環都能碰到至少一個紅點。更等價於在圖G(m,n)中,最少應扣除幾個點後,便可形成一森林。 我們將這些點數記作k(m,n)。特別地,當m=n時記作k(n) 。本文推得:k(m,n)≧[mn+1/3],並將等號成立時的k(m,n) 稱為完美的。經過構造後發現k(2n)、k(3,n)、 k(3n,m)、k(2+6m,2+6n),k(4+6m,4+6n) , 亦為完美的,並且將k(m,n)壓到只剩兩種可能。也得知了在無限擴張的格子圖中被移除點的密度為1/3。


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

檔案名稱 檔案大小 格式
TISF2021-010024.pdf 2 MB Adobe Reader(Pdf)檔案