Expert Answers

Draw the graph G whose adjacency matrix is

Does G contain an Eulerian cycle? Does G contain a Hamiltonian cycle? Briefly justify your answers.

The following table gives the distances (in miles) between six towns A, B, C, D, E, and F.

  A B C D E F
A 9 26 25 36 16
B 9 22 18 27 20
C 26 22 8 30 12
D 25 18 8 14 38
E 36 27 30 14 28
F 16 20 12 38 28


(a) Use the minimal spanning tree algorithm to find a network of minimal total length linking all six towns. What is the total length of the network?

(b) Use the nearest neighbor algorithm (starting at town A) to find a circular route visiting all six towns. What is the total length of the route?

Relations R and S are defined on the set {1, 2, 3, . . . , 12} as follows:

R = {(x, y) : xy = 12} and S = {(x, y) : 2x = 3y}

(a) List the ordered pairs that belong to the composite relation S o R

(b) Determine the logical boolean matrix representing the composite matrix S o R

The knowledge based system TENNIS contains the following list of basic facts:

Answer the following queries, briefly justifying your answers:

(a)       ? – am(x) and asks(x, charles)

(b)       ? – asks(anita, x) and (not(asks(charles, x)))

(c)       ? – incommon(charles, quentin)

(d)       ? – incommon(x, ron) or asks(x, ron)

Write down formal queries asking each of the following:

(e)       Is there a professional player that bill is prepared to ask to partner him?

(f)        Is there a player whom both a professional player and an amateur player are prepared to ask to partner them?