# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**82**> 83 84 85 86 87 88 .. 156 >> Next

More precisely, this formulation of the gcp as a unicost version of the well-known set covering problem (scp) (see Chapter 7 of this book) is as follows.

Suppose that Mi, M2,..., Mp represent the family of mis of G, and for each Mj define the 0-1 variable y, as:

yf = 1 if Mj is present in the optimal colouring of G = 0 otherwise.

Again with

ei}? = 1 if x, e Mj = 0 otherwise

we have the following program:

P

min z = X y,

1 = 1

s-*- I e,y, & 1 i = l,...,n

>, =0,1 / = 1, ...,p

where the inequalities correspond to possible over-colourings.

Thus for the example of Figure 8.1, there are 9 mis, viz.

M2 = {xl,x1}, M3 = {x2,x3}, M4 = {i2, x5}, M5 = {x3, x6}, M6 = {x3, x7}, M7 = {x4, xs}, M8 = {x4, x6}, M9 = {xs, x7}, so that p = 9 with the matrix [efj] being as shown in Figure 8.2.

216

Samuel M. Korman

1 i

1 1

i i 1

i i 1

1 i 1

1 1

1 1 1

Figure 8.2

We note that the optimum solution given earlier can be derived from any one of the following three solutions to the scp.

(a) y1 = y2 = y4 = y5 = l; y3 = y6=y7 = y8 = y9 = 0

(b) yi = y4 = y5 = y6 = i; y2 = y3 = y7 = y8 = y9 = o

(c) yi = y4 = y5 = y9 = 1; y2 = y3 = y6 = yj = ya = 0

these corresponding respectively to the over-colouring of vertices Xj, x3, and

x5.

This latter formulation is considerably better than those mentioned earlier, and although it involves the additional problem of determining all the mis of a graph, it is a viable method of solution for the gcp, as efficient algorithms exist (e.g. Bron and Kerbosch, 1973) for mis enumeration.

Before going on to consider more specific methods for solving the gcp, we conclude this section by describing some simple and well-known results (Berge, 1973; Roschke and Furtado, 1973) which often allow a reduction in the amount of work involved in solving the gcp.

8.1.3 Elementary Reductions in Problem Size

(i) Suppose xs and X( are two vertices of the graph G = (X, F) with the property that Txs ? Txt. (Note that this implies, in particular, that xs is not adjacent to xt.) It is then readily seen that any colour which is feasible for vertex ^ (in the course of any algorithm) would also be feasible for xs, so that we need only in fact use the algorithm to optimally colour the (sub)graph G' = (X', T) where X' = X-{xs}, and then assign the colour C(x,) to xs.

The Graph-Colouring Problem

217

(ii) Again, suppose that the graph G contains an articulating set which is a clique, Q, of cardinality p, say. That is, removing Q from the graph will divide the graph into two, day, disjoint components, G1 = (X1,ri) and G2 = (X2, T2), where X1UX2 = X Q so that the colouring of X, is unaffected by the colouring of X2, and vice versa. Then it is readily seen that the graphs G' = (X, U Q, T) and G" = (X2 U Q, T)where T is restricted in each case to the appropriate vertex set (X, U Q)can each be coloured separately (using at least p colours), and then combined (overlapping at Q) to obtain an optimal colouring of G, with y(G) = max [y(G), y(G")].

Thus, in this case, the problem of optimally colouring G is reduced to the simpler problems of colouring G' and G"; and obviously an analogous reasoning applies should Q divide G into more than two components.

We note here that two results most often used for graph reduction (Roschke and Furtado, 1973) correspond to the cases p = 1 and p = 2.

8,2 Vertex-Sequential Graph-Colouring Algorithms

In this and the following sections we develop various tree search methods for solving the gcp directly.

8.2.1 The Basic Algorithm and Some Variations

8.2.1.1 A Simple Vertex-by-Vertex Colouring Algorithm

In what follows we shall assume that the vertices of G = (X, T) have an associated sequential ordering (at this stage arbitrary) xu x2,.. . , x*. An elementary and well-known algorithm (Brown, 1972) for finding an optimal colouring of G is then to assign colours to the vertices of G in ascending order of their index as follows.

Initially we assign colour 1 to xl5 and then colour the remaining vertices in sequence by assigning to vertex xi; 2^ i =? n, the colour C(xi) represented by the lowest integer which has not been assigned to any of the vertices of index lower than i which are adjacent to x,. That is, each vertex in order is assigned the lowest feasible colour, so that C(Xj)*SmaxI<; {C(x,-)} + l, i = 1,2,..., n.

When x has been coloured in this manner, a feasible colouring of G will have been achieved using ql5 say, colours where q, =max1SlSn (C(x,)}. Though this colouring will rarely be optimal (after the first pass), q1 will obviously serve as an upper bound for the next phase of the algorithm, whereby we attempt to generate a feasible colouring using q2=s9i~l colours. To accomplish this we would of course have to recolour (at least) those vertices to which we had assigned colour q,. Hence we backtrack to

218

Samuel M. Korman

vertex xk, where xk+1 is the vertex of lowest index which has been assigned colour ql.

We then attempt to colour xk with its smallest (feasible) alternative colour greater than its current colour C(xk). If no such alternative colour, c, exists which is smaller then qx we backtrack to xk_,. On the other hand if c<qlt we recolour xk with c, and proceed forward as before, colouring xk+1 with its smallest feasible colour, etc., until such time as either x is coloured or some vertex x, is reached which requires colour q1.

**82**> 83 84 85 86 87 88 .. 156 >> Next