算法合集之平面圖在信息學(xué)中的應(yīng)用-wenkub.com
2024-10-13 20:30 本頁面
【正文】 相信隨著對平面圖的研究不斷深入，平面圖的應(yīng)用一定會更加廣闊。（區(qū)域數(shù) =500） 對于任意平面圖 G，是否都能用不超過 5種顏色著色？ 應(yīng)用 例 3:地圖著色 (ACM Shanghai 2021) 定理：對于任意平面圖 G，都能用不超過 5種顏色著色 . 證明：只需考慮 G是連通簡單平面圖的情形 . 若 |V|≤5，則命題顯然成立 . 假設(shè)對所有的平面圖 G=V， E，當(dāng) |V|≤k時命題成立 .現(xiàn)在考慮圖 G1=V1， E， |V1|=k+1的情形 .由推論 2可知：存在 v0∈ V1，使得 d(v0)≤ G1中刪去 v0，得圖 ，圖 G1v0可用 5種顏色著色 . 若鄰接結(jié)點(diǎn)使用顏色數(shù)不超過 4，則可對 v0著色，得到一個最多是五色的圖 G1. 應(yīng)用 例 3:地圖著色 (ACM Shanghai 2021) 若 d(v0)=5且各鄰接點(diǎn)分別著不同的顏色 ， 則設(shè)與之相鄰的點(diǎn)的按順時針排列為 v1,v2,v3,v4,色 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五個點(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的子圖中含有一個圈 C， 而 v2,v4不能同時在圈的內(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的不同的分圖 .做與上面類似的調(diào)整 ， 又可得到 G1的一種五著色 . 故對任何連通簡單平面圖 G， G是五著色的 . v1 v5 v4 v3 v2 v0 v1 v5 v4 v3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1