在代數圖論中,色多項式是喬治·戴維·伯克霍夫為了嘗試證明四色定理而定義的一種多項式。
色多項式
的值是在圖
中頂點的不同的
-著色數目,是關於
的多項式。
例如當圖
為一點時,
。
特殊圖的色多項式
完全圖![{\displaystyle K_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2b988ea630d2c5571afe47efa3d3b251708acb) |
|
樹![{\displaystyle T_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d9241493be76739f2400f258f32c24f9689161f) |
|
環![{\displaystyle C_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0301812adb392070d834ca2df4ed97f1cf132f33) |
|
佩特森圖 |
|
給定
階圖
,色多項式
是關於
的多項式,且滿足以下性質[1]:
- 多項式
的次數為
。
的係數為1。
的係數為
。
的係數不為0且正負交替出現。
特別的,設
有
個連通分量,分別為
,那麼
的係數為0。
![{\displaystyle P(G)=\prod _{k=1}^{n}P(G_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c708e203830f64a862dd3d55ff72536e5a995691)
遞推公式[編輯]
對於邊uv的邊收縮(G / {uv})示意圖。
給定圖
與
,那麼
![{\displaystyle P(G,k)=P(G-e,k)-P(G/e,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df02ac9de6a60942dcc30a7b3cf4a6816d3b82ac)
其中
代表邊收縮:令
所連接的兩個頂點計為
和
,而邊收縮會使頂點
和
合併成一個新的頂點
,並使原本與
和
相連的所有邊都連到
。
證明[2] 假設
所連接的兩個頂點為
和
,考慮圖
。
- 當
和
的顏色相同時,這種著色方式也是
的一種合理著色方式,反之亦然。所以對圖
將
和
染上相同顏色的著色方式有
種。
- 當
和
的顏色不同時,這種著色方式也是
的一種合理著色方式,反之亦然。所以對圖
將
和
染上不同顏色的著色方式有
種。
所以圖
的不同著色方式數目為
![{\displaystyle P(G-e,k)=P(G/e,k)+P(G,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/446d11e1cc3129f72c4887583e8a4b23d888b507)
加點或減點[編輯]
若點
在圖
上與其它所有點連邊,則所有點的顏色都與該點的顏色互異,記除去頂點
的圖為
。
![{\displaystyle P(G,t)=tP(G-v,t-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13d560d9a2f379b32351ead0b1c2753a6f2539d8)
![{\displaystyle P(K_{n},t)=tP(K_{n-1},t-1)=t(t-1)(t-2)...(t-(n-1))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8348226e22441f6fe8111008fa92426e6b647a7f)
在圖
的一邊
上添加點
所得圖記為
,兩端點著同色時有
種著色法,兩端點著不同色是有
種著色法。
[3]
![](//upload.wikimedia.org/wikipedia/commons/thumb/f/fc/L%28G%29.png/220px-L%28G%29.png)
為
的補圖的線圖的補圖。
若
為有
個頂點的圖,且它的獨立數<3,
[4]
其中
表示階乘冪,
為圖
中所含的完全子圖
的個數。
如右圖,
中有5個頂點,6條邊,2個三角形,所以
參考資料[編輯]
- ^ Whitney, Hassler, The coloring of graphs, Annals of Mathematics (JSTOR), 1932: 688–718
- ^ Harris, John; Hirst, Jeffry L.; Mossinghoff, Michael, Combinatorics and Graph Theory, Undergraduate Texts in Mathematics, Springer-Verlag New York: 98–99, 2008, ISBN 978-0-387-79711-3, doi:10.1007/978-0-387-79711-3
- ^ 林翠琴. 图的色多项式的几个递推公式. 數學雜誌. 1987, (3) [2015-03-07]. (原始內容存檔於2016-03-04).
- ^ 劉儒英. 关于图的色多项式. 青海師範大學學報(自然科學版). 1986, (Z1) [2015-03-07]. (原始內容存檔於2019-06-16).