Contents
1 Introduction
There are three positive examples below. They represent a reasonable collection of example road networks where there are tours. You should be able to take the definition of a tour from the initial assignment document and these examples, and work out further positive examples on your own.
Likewise, given the definition of a tour and the two negative examples below, you should be able to generate further examples of your own.
1. Positive Examples
(a) Trivial
The road network only has one city, a, e.g., “[(a, [])]”. So there is
only one starting city, a and there is only one tour, namely, [a, a], and its cost is 0.
(b) Mostly Trivial
The road network only has two cities, a and b, e.g., “[(a, [(b, 2)]), (b, [(a,1)])]”, where going from a to b costs 2 units and going from b to a costs 1 unit. We could have either a or b as the starting city, assuming a is the starting city then there is only one tour, namely [a, b, a], and its cost is 3.
(c) Less Trivial
Let the road network have 6 cities, a – f, and be the following:
“[(a, [(b, 5), (f, 6)]),
(b, [(a, 5), (e, 1), (c, 4)]),
(c, [(b, 4), (f, 9), (d, 2)]),
(d, [(e, 3), (c, 2), (f, 7)]),
(e, [(b, 1), (d, 2)]),
(f, [(a, 6), (c, 9), (d, 7)])]”
Assume a is the starting city. Then there are only two tours:
• [a,b,e,d,c,f,a],withacostof25; • [a,f,c,d,e,b,a],withacostof26.
2. “Negative” Examples
The next example illustrates a road network where there is no tour.
(a) Trivial
The network has two cities, a and b, but there is only one road going
from a to b but no road going from b to a. This could be represented by the following two networks:
• [(a, [(b,2)])];’
1
• or [(a, [(b,2)])(b, [])].
Niether of these networks can give rise to a tour. So, your solution predicate will fail for both of these networks.
2