西安电子科技大学$6.6.1图着色的基本概念软件学院解答：（a）用韦尔奇·鲍威尔法对G进行着色，整个过程如图9.6-2所示。+首先将G中结点按照度数由大到小排序，得到序列(b,c,d,e,f,a,g)。首先，将结点b看上红色，并且将与b不邻接的结点f也看上红色；其次，将结点c看上黄色，并将与c不接的e着上黄色：接下来，将结点d着上蓝色，并将与d不邻接的a着上蓝色，g与d和a均不邻接，因此它也可以着上蓝色。这样整个着色过程就结束了，G的色数x(G)=3。+结点结点颜色结点结点飘色颜色颜色H42AL黄英c3A美2红A0蓝(2)(3)(1)(4) 图9.6-2韦尔奇·鲍威尔法对图进行着色的过程+（b）对于图H可以用与G同样的着色过程，只是在对结点g着色时，因为g与a邻接，所以它不能着蓝色，必须使用一种新的颜色对其着色，因此G的色数X(H)-4+西安电子科技大学 §6.6.1 图着色的基本概念 软件学院