芻議圖頂點正常染色的計數公式

摘" 要：圖的染色計數問題是高中數學“計數原理”章節的常見題型. 圖的染色問題主要有頂點染色、邊染色和面染色三類，這三類染色問題都可以歸結為頂點染色問題. 介紹了圖頂點正常染色計數公式的背景、重要性質、“刪邊減收縮”算法和一般表達形式，最后舉例介紹有特殊限制條件的頂點正常染色計數公式.

關鍵詞：高中數學；計數原理；頂點染色；計數公式

中圖分類號：G633.6" " "文獻標識碼：A" " "文章編號：1673-8284（2024）06-0059-06

引用格式：蘇克義. 芻議圖頂點正常染色的計數公式［J］. 中國數學教育（高中版），2024（6）：59-64.

在貫穿古普魯士K?nigsberg城（哥尼斯堡）的Pregel河上有七座橋，連接兩岸及河中的兩個小島. 當時困擾當地居民的一個問題是：是否存在一種走法，走過每座橋恰好一次. 雖然當時多數人不相信存在這種走法，但是沒有人能解釋其原因. 當時，數學家Euler（歐拉，1707—1783）把每塊地用一個頂點代替，把每座橋用連接對應頂點的一條邊代替，該問題就被抽象為圖1. 為了解決這個問題，他提出了判定一般圖存在這種走法的充要條件，并給出了必要性的證明. 這一成果發表于1736年，被公認為第一篇圖論文章，他本人也被尊崇為圖論和拓撲學之父.

將圖1（稱為圖G）定義為[G=VG，EG]. 其中，[VG=A，B，C，D]稱為頂點集合，[EG=][AC，AC，AB，AB，CD，AD，BD]稱為邊集合. 頂點[C，D]稱為邊[CD]的端點，稱頂點[C，D]相鄰；頂點[C，B]之間無直接關聯的邊，稱頂點[C，B]不相鄰. 若一條邊的兩個端點相同，則稱為環. 若兩個頂點之間有多條邊，則稱為重邊. 不包含環和重邊的圖稱為簡單圖，本文只研究簡單圖.

早在1852年，Guthrie（古特里）就提出了“四色猜想”：在一個平面或球面上的任何地圖只需要用四種顏色來染色，就可以使得相鄰地區染不同顏色.“四色猜想”提出后，由于問題陳述的簡單性和幾何上的微妙性，在歷史上出現了很多錯誤的證明. 1976年，美國數學家Appel（阿佩爾）和Haken（哈肯）利用計算機花費了1 200多個小時，進行了約100億次邏輯判斷，終于完成了“四色猜想”的證明. 后來，很多數學家簡化了這一證明，但至今還沒有得到理論證明. 1912年，Birkhoff（伯克霍夫）為攻克“四色猜想”，提出了色多項式的概念. 色多項式即圖的頂點正常染色的計數公式. 雖然這一思想方法并沒有完成“四色猜想”的理論證明，但從此色多項式理論得到了不斷發展.

一、 圖的頂點正常染色及計數

圖2是一塊地圖，有三個地區，記為[A，B，C]，它們兩兩相鄰. 用數學家Euler（歐拉）的方法，用三個頂點[A，B，C]表示三個地區，相連的三條邊表示[A，B，C]兩兩相鄰，如圖3所示，記為[G=VG，EG]，其中[VG=A，B，C]，[EG=AB，BC，AC].

給定四種顏色對圖2進行區域染色等價于對圖3進行頂點染色. 若使相鄰的頂點染不同的顏色（稱為頂點正常染色），則不同的染色方案共有24種. 實際上，對圖3進行邊染色等價于對其進行頂點染色. 本文將這三類染色歸結成一類，主要討論圖的頂點正常染色問題.

若給定[λ λ∈N*]種顏色，用[PG，λ]表示最多用[λ]種顏色對圖[G]進行頂點正常染色的方案數目，則圖3的頂點正常染色計數公式為[PG，λ=λ3-3λ2+2λ]，該式被稱為圖3的色多項式. 數學家Read和Tutte（塔特）對色多項式進行了專題研究. 至今，國內外很多學者對色多項式進行了研究，得到了很多研究成果.

例1" 計算圖4的色多項式[PG，λ].

解：先染頂點[C]，有[λ]種染法，再依次染頂點[A，B，D，E]，得[PG，λ=λλ-1λ-2λ-12=λ5-][5λ4+9λ3-7λ2+2λ.]. . . . . .

例2" 計算圖5的色多項式[PG，λ].

解：按點[A，C]同色和異色分兩類進行研究：若點[A，][C]同色，則先染點[A，C]，再染點[B，D]，共有[λλ-12]種染法；若點[A，C]異色，則先染點[A，C]，再染點[B，D]，共有[λλ-1λ-22]種染法. 所以色多項式[PG，λ=][λλ-12+λλ-1λ-22=λ4-4λ3+6λ2-3λ].

解法1：先對點[A1]進行染色，共有[λ]種染法，再對[A2]進行染色，有[λ-1]種染法，以此類推，到對點[An]進行染色時，若還用[λ-1]種顏色進行染色，會出現點[A1]和點[An]同色、點[A1]和點[An]異色兩種情形.

二、[PG，λ]的兩條重要性質

性質1：“四色猜想”[?][PG，4gt;0].

性質2：[PG，λ]的各項系數的絕對值具有以下兩個性質.

（1）單峰值：這個序列總是先遞增，達到某個最大值（頂峰）以后就一直遞減，不會再上升.

（2）對數凹的：在這個序列中任取三個連續的數，這三個數總是滿足“左右兩個數的乘積小于中間數的平方”的規則.

上述（1）（2）即為“Read猜想”，這一猜想已被韓裔數學家June Huh（許埈珥）解決. 之后他在解決這一猜想的基礎上，進一步解決了“Rota猜想”，即任意擬矩陣的特征多項式的系數總是對數凹的. 正是因為June Huh解決了這兩個猜想，他獲得了2022年菲爾茲獎.

三、“刪邊減收縮法”求[PG，λ]

研究并求出[PG，λ]意義重大，在中學數學的學習中也經常遇到染色計數問題.

例4" 如圖7，一個地區分為五個行政區域，現給該地圖染色，要求相鄰區域不得使用同一種顏色，現有5種顏色可供選擇，則不同的染色方法有（" " ）.

（A）540種 （B）360種

（C）300種 （D）420種

解：將圖7等價轉化為圖8，圖8為一個輪圖[G]，它是由圈[C4]的4個頂點和圈內的一個頂點都相關聯所得的圖. 先染1號頂點，再染[圈C4]，則有[PG，λ=][5PC4，4=54-14+-144-1=420]（種）. 故答案選D.

推廣：可以將上述輪圖染色問題推廣到具有[n+1 n≥3，n∈N*]個頂點的情形，由公式[PCn，λ][λ≥4，λ∈N*]很容易能得到具有[n+1]個頂點的一般輪圖[G]的頂點染色計數公式[PG，λ=λPCn，λ-1=][λλ-2n+-1nλ-2][=λλ-2n+-1nλλ-2.]

在中學數學中有很多類似的染色問題，本文不再贅述. 當然，這些問題一般都是給定具體顏色數目的染色計數問題，較為簡單，利用計數原理和排列組合知識就可以解決. 但求一個簡單圖[G]的頂點染色計數公式[PG，λ]是一件困難的事情，即使頂點數[VG]比較小且圖[G]比較特殊時，[PG，λ]也不容易計算. Biggs在著作Algebraic Graph Theory中對[PG，λ]的計算進行了詳細闡述. F.M.Dong，K.M.Koh和K.L.Teo對[PG，λ]的計算方法進行了系統總結. 下面介紹一種由Biggs提出的求[PG，λ]的方法，這種算法具有一般性，當[VG]比較小時，方便操作. 這一方法可以用來解決中學數學中相關的染色問題，也可以解答相關奧林匹克數學競賽的題目.

定理：設[e]為簡單圖[G]的一條邊， 用[Ge]表示在[G]中刪除邊[e]所得的圖，[Ge]表示在[G]中收縮邊[e]所得的圖，則[PG，λ=PGe，λ-PGe，λ].

證明：考慮[Ge]的最多使用了[λ]種顏色的頂點正常染色有[PGe，λ]種染色方法，可將其分為兩類：當[e]的兩個端點染不同顏色時，有[PG，λ]種染法；當[e]的兩個端點染相同顏色時，有[PGe，λ]種染法. 由此可得[PGe，λ=PG，λ+PGe，λ]，即[PG，λ=][PGe，λ-PGe，λ].

推廣：圖9為梯子形圖，由兩個正方形圖拼接而成，將其記為[T2]，圖5可以記為[T1]，用“刪邊減收縮法”對[Tn+1 n≥2，n∈N*]進行一次操作. 如圖10，易得遞推公式[PTn+1，λ=λ-12PTn，λ-λ-2PTn，λ=][λ2-3λ+3PTn，λ]，其中[PT1，λ=λ4-4λ3+6λ2-3λ].

四、[PG，λ]的一般表達式

稱[V?VG]為圖[G]的獨立集. 若[V]中任意兩個頂點都互不相鄰，記[VG=n]，[λ∈N*]，用[mrG]表示將[VG]分成[r]個非空獨立集的不同的無序劃分數，令[λr=λλ-1…λ-r+1]，則有[PG，λ=r=1nmrGλr.]

五、有限制條件的頂點正常染色計數公式

對圖[G]進行染色時，若增加一些限制條件，可以產生各種各樣的染色問題，在奧林匹克數學競賽中也經常出現這類計數問題. 下面以2022年全國中學生數學奧林匹克競賽（預賽）暨2022年全國高中數學聯合競賽一試B卷第8題為例進行說明.

例10" 一個單位方格的四條邊中，若存在三條邊染了三種不同的顏色，則稱該單位方格是“多彩”的. 如圖12，一個[1×3]方格表的表格線共含10條單位長線段，現要對這10條線段染色，每條線段染為紅、黃、藍三色之一，使得三個單位方格都是“多彩”的. 這樣的染色方式數為

解：若一個方格被染好顏色，則相鄰方格的一條邊已染色，還剩三條邊待染色.

下面先解決問題：當一個方格的一條邊被染色以后，不妨設[AB]已染好顏色，問這個方格的“多彩”染色有多少種？分兩類考慮：如圖13，若[AB]和[CD]同色，則“多彩”染色有2種；如圖14，若[AB]和[CD]不同色，易得“多彩”染色有10種. 由此可知，當單位方格已有一條邊被染色后，共有12種染法可以使得方格是“多彩”的.

推廣1：圖12就是梯子形圖[T3]，它的“多彩”染色數目記為[fT3，3=]5 184，容易得到[fTn，3=][3×12n n∈N*]，其中[fT1，3=36].

六、結束語

圖[G]的頂點染色計數問題是圖論中的一個難點問題，當[VG]比較小且圖[G]比較特殊時，可以命制求染色計數的中學數學題目.

這類問題豐富，解法靈活多樣，解決過程可以很好地訓練學生的數學思維，培養學生進行數學抽象和邏輯推理的數學核心素養，在初等數學領域具有一定的研究和教學價值.

參考文獻：

［1］BIGGS N. Algebraic Graph Theory：second edition［M］. Cambridge：Cambridge University Press，1993.

［2］BONDY J A，MURTY U S R. Graph Theory with Applications［M］. Great Britain：The Macmillan Press Ltd，1976.

［3］APPEL K，HAKEN W. Every planar map is four colorable［J］. Bulletin of the American Mathematical Society，1976，82（5）：711-712.

［4］BIRKHOFF G D. A determinant formula for the number of ways of coloring a map［J］. Annals of Mathematics，1912，14（1 / 4）：42-46.

［5］CHEN X E，SU K Y，YAO B. A Note on Chromatic Uniqueness of Certain Complete Tripartite Graphs［J］. Ars Combinatoria，2012，105：205-211.

［6］SU K Y，CHEN X E. A Note on Chromatic Uniqueness of Completely Tripartite Graphs［J］. Journal of Mathematical Research ＆ Exposition，2010，30（2）：233-240.

［7］蘇克義，陳祥恩. 一類完全三部圖的色唯一性［J］. 數學的實踐與認識，2011，41（2）：163-171.

［8］蘇克義，陳祥恩，劉信生. 一類完全三部圖的色唯一性［J］. 西北師范大學學報（自然科學版），2008，44（4）：10-14.

［9］中華人民共和國教育部. 普通高中數學課程標準（2017年版2020年修訂）［M］. 北京：人民教育出版社，2020.

［10］史寧中，王尚志.《普通高中數學課程標準（2017年版2020年修訂）》解讀［M］. 北京：高等教育出版社，2020.

基金項目：寧夏大學研究生教育改革創新與實踐項目——基于專業需求的教學實施——以“數學文化”和“數學競賽研究”課程為例（JXAL202205）.

作者簡介：蘇克義（1977— ），男，高級教師，碩士研究生導師，主要從事圖論和數學教育研究.