关于圈图C_n的连2距k着色计数

研究圈图Cn的连2距k着色计数问题,通过求解递推关系得到若干计数公式.

着色问题在测试用例集约简中的研究

基于I/O关系的黑盒测试用例集约简技术能够保证约简后的测试集Tred具有和原完全组合测试集相同的检错能力。该文提出了Red(I)和Red(O)两个对问题空间(I,O)约简的算法;构建了I/O关系图,将问题空间(I,O)划分为若干子问题(Ii,Oi);并引入着色问题得到每个子图的同色等价类,进一步得到其基类Ii′,然后实施等价类替换和运用算法Red(O);进而运用贪心算法求解覆盖每个子问题空间的测试用例集Treid;最后水平拼接各Treid构成问题空间(I,O)的约简测试用例集Tred。这样得到的测试集不仅保持了检错能力,而且规模较小,同时又降低了贪心算法的时空复杂度。

κ-树及其邻点可区别全染色

G是一个简单图,G的一个全染色f是指使相邻顶点和相邻边着不同颜色且每条关联边与它的顶点着以不同颜色的全染色。设f为图G一个全染色,对任意x∈V(G),用C(x)表示在f下顶点的颜色以及与x关联的边的颜色所构成的集合。若任意uv∈E(G),u≠v,有C(u)≠C(v),则称f是图G的邻点可区别的全染色,该问题的主要目的是确定图G的邻点可区别全色数。基于树的基本结构,构造了一种新的图类—κ-树,讨论并给出了两类κ-树S(n,1),S(n,2)的邻点可区别全色数。

多边形三角化图三色问题证明的一个注记

对“简单多边形三角形化图S是可以3-色”的定理证明中用到的关键定理:“简单多边形三角形化图S的对偶图T是一棵树”作了十分简化的证明,从而简化了3-色问题及Art Gallery问题Watchman定理的证明.