论文部分内容阅读
健壮性图着色问题(Robust Graph Coloring Problem-RGCP)是经典图着色问题的一种新的扩展。RGCP则着重针对着色方案的健壮性,使之能处理现实中经常出现的不可预见的突发事件,即需要考虑补边出现的情况。对RGCP在特殊情况下的最优解进行了研究,由此推导与证明了平均颜色定理,以及推广到一般RGCP求解的优化。