CS447 Lecture 3: L6.pdf
Document Summary
The following simple (and loop-free) path is, in fact, prime: p = Ppc includes this path as a test requirement. The test path meets the test requirement induced by p even though it is not prime. Note that a test path may satisfy the prime path test requirement even though it is not prime. Recall that our de nition of tour is strict: for path p to tour subpath p(cid:48) = [n1, n2, n3], p must contain exactly the sequence n1 n2 n3 in that order. There may not be any extra edges or nodes in p if it is to tour p(cid:48). s0 a d sf b c. The path is never toured by any path containing c because: q = [a, b, d] For instance, the paths p = [s0, a, b, c, b, d, sf ] p(cid:48) = [s0, a, b, c, d, sf ] don"t tour q using our de nition of tour .
