前言:
該法用於不用用完色的情況下
復雜的要用到色多項式,這個相關研究還很稀缺
將圖形轉化為點陣
以分離出的閉合圖形(三角,四邊,五邊…)為基本,
使用環排塗色公式
[{a_n} = {left( {k – 1} right)^n} + left( {k – 1} right){left( { – 1} right)^n}], k 為色數,n 為點數
其他的連接點為其衍射
常見模型:
1.魚圖:
先對 triangle [ABC] 用環染色公式 [{a_3} = {left( {k – 1} right)^3} + left( {k – 1} right){left( { – 1} right)^3}] ,再單獨對D
因其鄰BC,故再乘個 [left( {k – 2} right)]
其實此為間隔一點必不同情況
若間隔兩點則要分類討論
如
如圖 討論BD是否同色
2.有心圖
先對中心點O,塗 k
剩下隻能塗 [left( {k – 1} right)] 色
再對外圍x個點圖用環染色公式 [{a_x} = {left[ {left( {k – 1} right) – 1} right]^x} + left[ {left( {k – 1} right) – 1} right]{left( { – 1} right)^x}]
【若先四周後中心,可能存在顏色不夠用的情況】
3.樹
先對中心點O,塗 k
剩下隻能塗 [left( {k – 1} right)] ,再對外圍各個互相獨立而無影響的x個點有累塗 [{left( {k – 1} right)^x}]
有時題目會在模型中挖去一些線
此可能要用到高階著色多項式思想 即 [{P_k}left( {G – e} right) = {P_k}left( G right) + {P_k}left( {Ge} right)]
加點倒是沒太大關系
隨便殺幾道題
1.
三級改寫:將其改寫成點圖
即上述所講的有心圖
先塗裡面塗4色
剩下3色再塗外面有 [{left( {3 – 1} right)^4} + left( {3 – 1} right){left( { – 1} right)^4} = 18]
共 [4 times 18 = 72]
2.
改寫點圖
三角形環染色 [{left( {4 – 1} right)^3} + left( {4 – 1} right){left( { – 1} right)^3} = 24]
剩下的點與上頂點異色,隻能塗3色
共 [3 times 24 = 72]
3.
改寫點圖
先塗124 環染色公式: [{left( {4 – 1} right)^3} + left( {4 – 1} right){left( { – 1} right)^3} = 24]
3隻能塗2色
5隻能塗3色
故 [24 times 2 times 3 = 144]
等下,答案是96
有問題?
回往前提
該法用於不用用完色的情況下
若要深入研究:
原創思考,未經作者允許,禁止轉載