Weisstein, Eric W. "Vizing's Theorem." From MathWorld--A Wolfram Web Resource. (页面存档备份,存于互联网档案馆)
Holyer, Ian, The NP-completeness of edge-coloring, SIAM Journal on Computing, 1981, 10: 718–720.
Sanders, Daniel P.; Zhao, Yue, Planar graphs of maximum degree seven are class I, Journal of Combinatorial Theory, Series B, 2001, 83 (2): 201–212.
Vizing, V. G., Critical graphs with given chromatic class, Metody Diskret. Analiz., 1965, 5: 9–17. (In Russian.)
十月 21, 2023
vizing定理, 是圖論中的定理, 它描述了邊著色數與度的關係, 目录, 定理陳述, 分類法, 相关, 參考資料定理陳述, 编辑, 任意, 簡單, 無向, 的邊著色數, edge, chromatic, number, 等於, 其中, 指圖, 中最大的度, 分類法, 编辑由可知χ, 若為前者, 稱g為第一類圖, class, 否則稱為第二類圖, class, 雖然只有兩類, 但holyer, 1981, 證明了, 確定任意圖屬於哪一類是一個np完全問題, 不過, 對於特定類型的圖也有部分的解答, 比如對於簡單平面. Vizing定理是圖論中的定理 它描述了邊著色數與度的關係 目录 1 定理陳述 2 分類法 3 相关 4 參考資料定理陳述 编辑Vizing定理 任意 簡單 無向 圖 G 的邊著色數 edge chromatic number x G 等於 D G 或 D G 1 其中 D G 指圖 G 中最大的度 分類法 编辑由Vizing定理可知x G D G 或 D G 1 若為前者 稱G為第一類圖 Class 1 否則稱為第二類圖 Class 2 雖然只有兩類 但Holyer 1981 證明了 確定任意圖屬於哪一類是一個NP完全問題 不過 對於特定類型的圖也有部分的解答 比如對於簡單平面圖 Vizing 1965 自己證明了 如果D G 8 則是第一類的 但對於D G 2 3 4 5 的情況則有第二類圖存在 把正多面體的其中一邊截成兩條 即可得到 D G 3 4 5 的平面圖 他們是第二類的 而任何長度是奇數的圈 比如三角形 就是 D G 2 的第二類圖 對於剩下的兩種情況 Vizing提出了猜想 平面圖Vizing猜想 任何簡單平面圖如果 D G 6 或7 則是第一類的 Vizing 1965 在 D G 7 的情形 Sanders amp Zhao 2001 給出了肯定的結果 因此只剩下 D G 6 的情形尚待解決 不過一般來講 大多數 的圖都是第一類的 來源請求 相关 编辑ER随机图參考資料 编辑Planet math Weisstein Eric W Vizing s Theorem From MathWorld A Wolfram Web Resource 页面存档备份 存于互联网档案馆 Holyer Ian The NP completeness of edge coloring SIAM Journal on Computing 1981 10 718 720 Sanders Daniel P Zhao Yue Planar graphs of maximum degree seven are class I Journal of Combinatorial Theory Series B 2001 83 2 201 212 Vizing V G Critical graphs with given chromatic class Metody Diskret Analiz 1965 5 9 17 In Russian 取自 https zh wikipedia org w index php title Vizing定理 amp oldid 71699955, 维基百科,wiki,书籍,书籍,图书馆,