[其他] 線性規劃 地圖著色

[LATOG2013 (Latog2013)]

台灣地圖著色，將台灣本島每個縣市著色，
相鄰的縣市需著不同的顏色，且要用最少的顏色畫完地圖。
使用線性規劃求解
這樣的題目要如何解?


謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.33.72.206
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1460427590.A.271.html
→ freePrester : 四色定理？
推 arthurduh1  : 圖著色是整數規劃問題
→ LATOG2013   : 好像要用0 1去設   只是不清楚限制式該怎麼列
→ arthurduh1  : 對每個 (頂點,顏色) 做一個 binary indicator
→ arthurduh1  : 根據著色的定義去列限制式
→ arthurduh1  : 對頂點 v, 顏色 c, x(v,c)=1 若且唯若 v 著顏色 c