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?