Books in black and white
 Main menu Share a book About us Home
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

# Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): čüombinatorialoptimi2012.pdf Previous << 1 .. 80 81 82 83 84 85 < 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| : /WÆMjr,, 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; | QiłQ(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. Previous << 1 .. 80 81 82 83 84 85 < 86 > 87 88 89 90 91 92 .. 156 >> Next 