# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**86**> 87 88 89 90 91 92 .. 156 >> Next

M(G) = {( jt, , jr3), (jr,, Jr4, Jr7). (x2, jr7), < jt2 , jt5, ^7), ( /2,*5,/8),(jr3,/5),(jr3,x6),(x6,ira)}

___________I

( Gq'-G )

v------"----' M(G0) = M(G)

x* = x| : /WMjr,, jr3) , M*={xt,x4, x7)

M(G]) = {( *2 , x41*7)1 ( *6'*8b

(x2.Jf5.Jf7), (x2,X5,x x* - x4 M2*(x2, x4,x7)

M(GZ) = {(x5,x8)( xg.Xg)}

f* = jr5 :

(GrGo -«DC GrG 3-*0

}

m\

4 5

(cH! - "0 C \

(7) 6

-"D (*§« > ? «0

M(G^) - ((x2,x5,xe)1(x3,x5), (x3,xs),(x6,x8)} x*--xz M$*{x2,xs,xe)

M«?|) = {U3.x6)}

*3 1 *3 - *^ = (Jf3.^6>

Terminate with y (G) = 3, ana

2 2 2 associated colouring ( My ,M^M^ )

Figure 8.6

The Graph-Colouring t-roblem

227

represents the /th subgraph of the as yet uncoloured vertices to be considered at any level r, M[ represents the set of vertices to be assigned colour r (so leading to subgraph G'r), while the order in which the nodes are considered for branching purposes is indicated by the index to the upper right of each node.

8.3.3 An Equivalent Depth-First Approach

The breadth-first tree search just described can easily be adapted to a

depth-first procedure in the usual fashion. We detail below the exact

description of a depth-first graph-colouring algorithm (Wang, 1974) which corresponds to the method described in the previous section.

8.3.3.1 A Depth-First Graph-Colouring Algorithm

Step 0 Calculate M(G), the family of mis of G.

Set q = |X| and initialize C(j) = j, j = 1,. .., q.

Step 1 Set G' = G, r = l.

Step 2 If r^q go to 8, otherwise continue to 3.

Step 3 Derive M(G') (from M(G)) and establish x* as that vertex contained in the least number of sets in M(G'), say these are M), M?,. . ., M71.

Step 4 Set pr = m, hr = 0.

Step 5 If h, = pT go to 8, otherwise increment h, = hr + 1 and continue to

Step 6.

Step 6 Set M'= mr\ G'= G'-M'. If G' = 0 go to 7, otherwise increment r = r + 1 and return to Step 2.

Step 1 A feasible colouring using r colours has been attained, viz. M^1, M^2,.. ?, set q = r and define C(j) = {jq | xf e Mp) for j = 1,..., r.

Step 8 If r = l, STOP with -y(G) = q and associated colouring function C( ), otherwise set r = r-l, G' =G'UM[\ and return to Step 5.

Example The search-tree obtained when applying the above algorithm to the graph G in Figure 8.5 is essentially similar to that depicted in Figure 8.6, but with the nodes considered in a different order.

Thus we would first proceed down the left-most path of the tree considering in turn nodes 1, 2, 4, and 7, and so generate a further node (emanating from 7) by assigning colour 4 to the vertex set M\ = {x6}. At this stage a feasible colouring using 4 colours is achieved and we would backtrack to node 1 (via nodes 7, 4, and 2 as no branching alternatives exist for these

228

Samuel M. Korman

nodes) and then proceed down the alternative path in an attempt to find a colouring involving 3 colours or less.

As such a colouring is found we use this latter to update the feasible solution found earlier and backtrack once more, but as no further branching alternatives exist, the algorithm would terminate with the identical optimal solution found in the previous example.

(It is to be noted that if we would have considered Ml for branching purposes before M], so that the first feasible colouring generated would have been' (Ml, Ml, M|), only as many nodes would have been considered as were used in the breadth-first method of Figure 8.6, since node 7 would not have been considered due to the bound cut-off.)

We consider next a tree-search algorithm for graph colouring which involves an alternative strategy in an attempt to reduce further the size of the search-tree.

8.3.4 A Multiple Algorithm lor Graph Colouring

In this section we describe a depth-first tree-search algorithm, based on Theorem 8.5 below, which (relative to the algorithms based on Theorem 8.4) further restricts the choice of sets to be considered at each stage of the tree-search.

8.3.4.1 An Intersection Theorem and Some Consequences

Let us denote the family of cliques of G of maximum size (hereafter termed the maximum cliques of G) as:

Q(G) = {Q; | QiQ(G),|Qj = w(G)}

where Q(G) represents the family of cliques of G (so that Q(G) s Q(G)).

Theorem 8.5 (Intersection Theorem) (Korman, 1975) If for a graph G, y(G) = o>(G), then an optimum colouring of G can be obtained by first colouring with colour 1 an mis of G, say Mu such that

IM^ 0,1 = 1 VO, e Q(G)

then colouring with colour 2 an mis of the graph Gl, say M2, such that

\M2 n Q,| = 1 VQi eQ(Gj), etc.

until all the vertices of G are coloured; where, as before,

k

Gk = (Xfc, T) with Xk = X- U Mj (and G0 = G).

j = i

The Graph-Colouring Problem

229

The implementation of the actual algorithms can be simplified by using instead the graphs Gk obtained by successively joining, at every stage fc, a pseudo-vertex xk, representing Mk, to each vertex of (Gk + {xls x2,..., xk_,}).

Thus, consider any arbitrary sequence of sets {M,, M2, ? ? ?, Mp} where Mk is an mis of the graph Gk _, in the sequence of graphs G0, GGp defined as above, where for notational convenience we now write Gk for Gk.

**86**> 87 88 89 90 91 92 .. 156 >> Next