用吴方法解决染色问题
Solve the Dyeing Problem by Wu’s Method
摘要:
染色问题是图论中的著名问题，目前已有人用Groebner基方法解决了染色问题，本文另辟蹊径用吴方法来解决染色问题。吴方法又称特征列方法，是吴文俊于20世纪70年代提出的处理多项式代数问题的一种方法。与Groebner基方法不同之处在于，它完全采用零点集的观点来处理问题，因此在染色问题求解方面较Groebner基方法更有效，本文仅解决染色问题中的三色问题。
Abstract:
Dyeing problem is a famous problem in graph theory; the dyeing problem has been solved by Groebner bases method. This text applies the technique of Wu’s method to solve the dyeing problem. The Wu’s method is also called the feature list method; it is a method to deal with polynomial algebra problem proposed by Wu Wenjun in the 1970s. The difference between Wu’s method with Groebner bases method is that Wu’s method completely uses the viewpoint of zero set to deal with the problem, so it is more effective than Groebner bases method in solving dyeing problems; this paper only solves the 3-color problem in the dyeing problem.
参考文献
|
[1]
|
Adams, W.W. and Loustaunau, P. (2000) An Introduction to Groebner Bases. American Mathematical Society.
|
|
[2]
|
张树功, 雷娜, 刘停战. 计算机代数基础[M]. 北京: 科学出版社, 2005.
|
|
[3]
|
王东明, 夏壁灿, 李子明. 计算机代数[M]. 北京: 清华大学出版社, 2007.
|
|
[4]
|
Cox, D., Little, J. and O’Shea, D. (1996) Ideals, Varieties, and Algoithms. 2nd Edition, Springer, New York.
|
|
[5]
|
Mishra, B. (1993) Algorithmic Algebra. Springer-Verlag, New York. [Google Scholar] [CrossRef]
|
|
[6]
|
Cox, D., Little, J. and O’Shea, D. (1997) Ideals, Varieties and Algorithms. Sprin-ger-Verlag, New York.
|
|
[7]
|
Ritt, J.F. (1950) Differential Algebra. American Mathematical Society, New York. [Google Scholar] [CrossRef]
|
|
[8]
|
Wu, W.-T. (2000) Mathematics Mechanization. Science Press and Kluwer Academic Publish-ers.
|