图的k-星着色的Gröbner基求解
Solving the k- Star Coloring Problem of Graph by Gröbner Bases
-
摘要: 对于具有 n 个顶点的简单连通图 G, 首先证明求解 G 的 k-星着色等价于一个多元多项式方程组在 1, 2, …, k 上的求解问题, 其次使用 Gröbner 基给出求解该多元多项式方程组的方法, 从而得到求 G 的星色数的一个可行途径, 最后通过实例验证了此代数计算方法的有效性.Abstract: In the report,let G be a simple connected graph of n vertices,that solving star chromatic number of G is equivalent to finding all1,2,…,k solutions of a system of multivariate polynomial equations; Gröbner bases were used to propose the solving method of the multivariate polynomial equations,that a feasible way of finding star chromatic number of G was obtained; the numerical example was presented to illustrate the effectiveness of the algebraic computational method.