Vizing定理是圖論中的定理。它描述了邊著色數與度的關係。
定理陳述
Vizing定理：任意(簡單, 無向)圖 G 的邊著色數 (edge chromatic number, χ′(G)) 等於 Δ(G) 或 Δ(G) + 1，其中 Δ(G) 指圖 G 中最大的度。
分類法
由Vizing定理可知χ′(G)=Δ(G) 或 Δ(G) + 1。若為前者，稱G為第一類圖(Class 1)，否則稱為第二類圖 (Class 2)。雖然只有兩類，但證明了，確定任意圖屬於哪一類是一個NP完全問題。
不過，對於特定類型的圖也有部分的解答。比如對於簡單平面圖，自己證明了，如果Δ(G)≥8 則是第一類的，但對於Δ(G)=2,3,4,5 的情況則有第二類圖存在：把正多面體的其中一邊截成兩條，即可得到 Δ(G)=3,4,5 的平面圖，他們是第二類的；而任何長度是奇數的圈(比如三角形)就是 Δ(G)=2 的第二類圖。對於剩下的兩種情況，Vizing提出了猜想：
*平面圖Vizing猜想：
※任何簡單平面圖如果 Δ(G)≥6 (或7)，則是第一類的。
在 Δ(G)≥7 的情形， 給出了肯定的結果。因此只剩下 Δ(G)≥6 的情形尚待解決。
不過一般來講，
相关
- ER随机图
參考資料
*[https://web.archive.org/web/20091119053311/http://planetmath.org/encyclopedia/VizingsTheorem.html Planet math]
*[http://mathworld.wolfram.com/VizingsTheorem.html Weisstein, Eric W. "Vizing's Theorem." From MathWorld--A Wolfram Web Resource.]
*.
*.
*. (In Russian.)
评论 (0)