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

關(guān)鍵詞：高中數(shù)學(xué)；計(jì)數(shù)原理；頂點(diǎn)染色；計(jì)數(shù)公式

中圖分類號(hào)：G633.6" " "文獻(xiàn)標(biāo)識(shí)碼：A" " "文章編號(hào)：1673-8284（2024）06-0059-06

引用格式：蘇克義. 芻議圖頂點(diǎn)正常染色的計(jì)數(shù)公式［J］. 中國(guó)數(shù)學(xué)教育（高中版），2024（6）：59-64.

在貫穿古普魯士K?nigsberg城（哥尼斯堡）的Pregel河上有七座橋，連接兩岸及河中的兩個(gè)小島. 當(dāng)時(shí)困擾當(dāng)?shù)鼐用竦囊粋€(gè)問(wèn)題是：是否存在一種走法，走過(guò)每座橋恰好一次. 雖然當(dāng)時(shí)多數(shù)人不相信存在這種走法，但是沒(méi)有人能解釋其原因. 當(dāng)時(shí)，數(shù)學(xué)家Euler（歐拉，1707—1783）把每塊地用一個(gè)頂點(diǎn)代替，把每座橋用連接對(duì)應(yīng)頂點(diǎn)的一條邊代替，該問(wèn)題就被抽象為圖1. 為了解決這個(gè)問(wèn)題，他提出了判定一般圖存在這種走法的充要條件，并給出了必要性的證明. 這一成果發(fā)表于1736年，被公認(rèn)為第一篇圖論文章，他本人也被尊崇為圖論和拓?fù)鋵W(xué)之父.

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

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

一、 圖的頂點(diǎn)正常染色及計(jì)數(shù)

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

給定四種顏色對(duì)圖2進(jìn)行區(qū)域染色等價(jià)于對(duì)圖3進(jìn)行頂點(diǎn)染色. 若使相鄰的頂點(diǎn)染不同的顏色（稱為頂點(diǎn)正常染色），則不同的染色方案共有24種. 實(shí)際上，對(duì)圖3進(jìn)行邊染色等價(jià)于對(duì)其進(jìn)行頂點(diǎn)染色. 本文將這三類染色歸結(jié)成一類，主要討論圖的頂點(diǎn)正常染色問(wèn)題.

若給定[λ λ∈N*]種顏色，用[PG，λ]表示最多用[λ]種顏色對(duì)圖[G]進(jìn)行頂點(diǎn)正常染色的方案數(shù)目，則圖3的頂點(diǎn)正常染色計(jì)數(shù)公式為[PG，λ=λ3-3λ2+2λ]，該式被稱為圖3的色多項(xiàng)式. 數(shù)學(xué)家Read和Tutte（塔特）對(duì)色多項(xiàng)式進(jìn)行了專題研究. 至今，國(guó)內(nèi)外很多學(xué)者對(duì)色多項(xiàng)式進(jìn)行了研究，得到了很多研究成果.

例1" 計(jì)算圖4的色多項(xiàng)式[PG，λ].

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

例2" 計(jì)算圖5的色多項(xiàng)式[PG，λ].

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

解法1：先對(duì)點(diǎn)[A1]進(jìn)行染色，共有[λ]種染法，再對(duì)[A2]進(jìn)行染色，有[λ-1]種染法，以此類推，到對(duì)點(diǎn)[An]進(jìn)行染色時(shí)，若還用[λ-1]種顏色進(jìn)行染色，會(huì)出現(xiàn)點(diǎn)[A1]和點(diǎn)[An]同色、點(diǎn)[A1]和點(diǎn)[An]異色兩種情形.

二、[PG，λ]的兩條重要性質(zhì)

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

性質(zhì)2：[PG，λ]的各項(xiàng)系數(shù)的絕對(duì)值具有以下兩個(gè)性質(zhì).

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

（2）對(duì)數(shù)凹的：在這個(gè)序列中任取三個(gè)連續(xù)的數(shù)，這三個(gè)數(shù)總是滿足“左右兩個(gè)數(shù)的乘積小于中間數(shù)的平方”的規(guī)則.

上述（1）（2）即為“Read猜想”，這一猜想已被韓裔數(shù)學(xué)家June Huh（許埈珥）解決. 之后他在解決這一猜想的基礎(chǔ)上，進(jìn)一步解決了“Rota猜想”，即任意擬矩陣的特征多項(xiàng)式的系數(shù)總是對(duì)數(shù)凹的. 正是因?yàn)镴une Huh解決了這兩個(gè)猜想，他獲得了2022年菲爾茲獎(jiǎng).

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

研究并求出[PG，λ]意義重大，在中學(xué)數(shù)學(xué)的學(xué)習(xí)中也經(jīng)常遇到染色計(jì)數(shù)問(wèn)題.

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

（A）540種 （B）360種

（C）300種 （D）420種

解：將圖7等價(jià)轉(zhuǎn)化為圖8，圖8為一個(gè)輪圖[G]，它是由圈[C4]的4個(gè)頂點(diǎn)和圈內(nèi)的一個(gè)頂點(diǎn)都相關(guān)聯(lián)所得的圖. 先染1號(hào)頂點(diǎn)，再染[圈C4]，則有[PG，λ=][5PC4，4=54-14+-144-1=420]（種）. 故答案選D.

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

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

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

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

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

四、[PG，λ]的一般表達(dá)式

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

五、有限制條件的頂點(diǎn)正常染色計(jì)數(shù)公式

對(duì)圖[G]進(jìn)行染色時(shí)，若增加一些限制條件，可以產(chǎn)生各種各樣的染色問(wèn)題，在奧林匹克數(shù)學(xué)競(jìng)賽中也經(jīng)常出現(xiàn)這類計(jì)數(shù)問(wèn)題. 下面以2022年全國(guó)中學(xué)生數(shù)學(xué)奧林匹克競(jìng)賽（預(yù)賽）暨2022年全國(guó)高中數(shù)學(xué)聯(lián)合競(jìng)賽一試B卷第8題為例進(jìn)行說(shuō)明.

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

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

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

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

六、結(jié)束語(yǔ)

圖[G]的頂點(diǎn)染色計(jì)數(shù)問(wèn)題是圖論中的一個(gè)難點(diǎn)問(wèn)題，當(dāng)[VG]比較小且圖[G]比較特殊時(shí)，可以命制求染色計(jì)數(shù)的中學(xué)數(shù)學(xué)題目.

這類問(wèn)題豐富，解法靈活多樣，解決過(guò)程可以很好地訓(xùn)練學(xué)生的數(shù)學(xué)思維，培養(yǎng)學(xué)生進(jìn)行數(shù)學(xué)抽象和邏輯推理的數(shù)學(xué)核心素養(yǎng)，在初等數(shù)學(xué)領(lǐng)域具有一定的研究和教學(xué)價(jià)值.

參考文獻(xiàn)：

［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］. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，41（2）：163-171.

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

［9］中華人民共和國(guó)教育部. 普通高中數(shù)學(xué)課程標(biāo)準(zhǔn)（2017年版2020年修訂）［M］. 北京：人民教育出版社，2020.

［10］史寧中，王尚志.《普通高中數(shù)學(xué)課程標(biāo)準(zhǔn)（2017年版2020年修訂）》解讀［M］. 北京：高等教育出版社，2020.

基金項(xiàng)目：寧夏大學(xué)研究生教育改革創(chuàng)新與實(shí)踐項(xiàng)目——基于專業(yè)需求的教學(xué)實(shí)施——以“數(shù)學(xué)文化”和“數(shù)學(xué)競(jìng)賽研究”課程為例（JXAL202205）.

作者簡(jiǎn)介：蘇克義（1977— ），男，高級(jí)教師，碩士研究生導(dǎo)師，主要從事圖論和數(shù)學(xué)教育研究.