图的(k,d)-着色问题的一个近似算法

摘要

In this paper, we discuss the (k, d)-coloring problem of a graph, and propose a four-layer neural network algorithm. Using this algorithm, one can successively find a feasible (k, d)-coloring of the graph with given circular chromatic number;moreover one can use this algorithm to estimate the circular chromatic number of a graph.%本文讨论了图的(k,d)-着色问题的算法,并给出了一个由四层神经元组成的神经网络算法.当一个图的循环色数已知时(不妨设为k/d),可以利用该算法成功地求出这个图的一个可行(k,d)-着色方案;当一个图的循环色数未知时,可以利用该算法求出这个图的循环色数的近似值.