臺灣國際科展

平面圖的四元列表著色

科展類別
臺灣國際科展作品
屆次
2017年
科別
數學
得獎情形
一等獎
學校名稱
臺北市立第一女子高級中學
指導老師
楊宗穎
作者
林芮吟
關鍵字
平面圖,列表著色,放電論證法

摘要或動機

給定一個簡單圖G(simple graph ),令V(G)、E(G)分別為G的頂點與邊所形成的集合。對於兩個不同的頂點u, v∈V(G),若存在一條邊連結頂點u, v,則將此邊記為uv,以uv∈E(G)表示。給定函數f: V(G)→ℕ,若對任意的邊uv∈E(G),函數f皆滿足f(u)≠f(v),則稱函數f為圖G的一個著色函數(proper coloring)。對於圖G,任意給定每個頂點v∈V(G)一個可用的顏色清單L(v)⊂ℕ,其中清單內各有四個可用顏色(|L(v)|=4 ,每個頂點的顏色清單可以不相同),若總是存在一個著色函數f,滿足∀v∈V(G),f(v)∈L(v),則稱圖G為『可四元列表著色(4-choosable )』。對於平面圖( plane graph),針對長度較小的圈(cycle)進行限制,我們設計充分條件,使得滿足條件的平面圖為可四元列表著色。


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

檔案名稱 檔案大小 格式
平面圖的四元列表著色 1 MB Adobe Reader(Pdf)檔案