算法合集之平面圖在信息學(xué)中的應(yīng)用-資料下載頁(yè)
2025-10-07 20:30本頁(yè)面
【正文】 c1,c2,c3,c4,c5. 考慮點(diǎn)集 Vc1,c3={v|v∈ V(G1v0)∧ a(v)=c1或 c3}所誘導(dǎo)的G1v0的子圖 Vc1,c3.若 v1,v3屬于 Vc1,c3的不同的分圖 ， 則在v1所在的分圖中 ， 調(diào)換顏色 c1與 c3后 ， v1,v2,v3,v4,v5五個(gè)點(diǎn)是四著色的 ， 再令 v0著 c1色 ， 得到 G1的一種五著色 . v1 v5 v4 v3 v2 v0 v1 v5 v4 v3 v2 v0 應(yīng)用 例 3:地圖著色 (ACM Shanghai 2021) 若 v1,v3屬于 Vc1,c3的同一的分圖 ， 則點(diǎn)集 Vc1,c3∪ {v0}所誘導(dǎo)的 G1的子圖中含有一個(gè)圈 C， 而 v2,v4不能同時(shí)在圈的內(nèi)部或外部 ， 即 v 2 , v 4 不是鄰接點(diǎn) ， 于是考慮Vc2,c4={v|v∈ V(G1v0)∧ a(v)=c2或 c4}所誘導(dǎo)的子圖 Vc2,c4，v2,v4必屬于 Vc2,c4的不同的分圖 .做與上面類(lèi)似的調(diào)整 ， 又可得到 G1的一種五著色 . 故對(duì)任何連通簡(jiǎn)單平面圖 G， G是五著色的 . v1 v5 v4 v3 v2 v0 v1 v5 v4 v3 v2 v0 v1 v5 v4 v3 v2 v0 應(yīng)用 例 3:地圖著色 (ACM Shanghai 2021) 算法： procedure Paint(G:Graph)。 ? 找出度最小的點(diǎn) v0 ? Paint(Gv0) ? 考慮圖 G， 若無(wú)法對(duì) v0著色 ， 則對(duì) v0的相鄰點(diǎn) ， 枚舉所有點(diǎn)對(duì) ,直到找到屬于不同分圖的點(diǎn)對(duì) ， 對(duì)其進(jìn)行調(diào)整 . ? 任選剩下的一種顏色 ， 對(duì) v0著色 時(shí)間復(fù)雜度： O(N2) 空間復(fù)雜度： O(N) 總結(jié) 以上例子分別論述了平面圖理論在幾類(lèi)信息學(xué)問(wèn)題中的應(yīng)用。我們研究平面圖就是為了更深刻地認(rèn)識(shí)平面圖，提高算法效率，但有時(shí)候單獨(dú)應(yīng)用平面圖理論還不夠，還需要和其它理論知識(shí)綜合起來(lái)應(yīng)用。然而要達(dá)到理想的效果并非一朝一夕的事情，它還需要我們平時(shí)多積累、多思考，遇到問(wèn)題時(shí)才能運(yùn)用自如。相信隨著對(duì)平面圖的研究不斷深入，平面圖的應(yīng)用一定會(huì)更加廣闊。 謝謝 !
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1