Graphs have at least one Hamiltonian circuit

11. Does each of these graphs have an Euler circuit? If so, find it.

12. Does each of these graphs have an Euler circuit? If so, find it.

13. Eulerize this graph using as few edge duplications as possible. Then, find an Euler circuit.

17. Does each of these graphs have at least one Hamiltonian circuit? If so, find one.

19. A company needs to deliver product to each of their 5 stores around the Dallas, TX area. Driving distances between the stores are shown below. Find a route for the driver to follow, returning to the distribution center in :

a. Using Nearest Neighbor starting in Fort Worth

b. Using Repeated Nearest Neighbor

c. Using Sorted Edges

21. When , some companies will install a sonet ring; a full loop of cable connecting multiple locations. This is used so that if any part of the cable is damaged it does not interrupt service, since there is a second connection to the hub. A company has 5 buildings. Costs (in thousands of dollars) to lay cables between pairs of buildings are shown below. Find the circuit that will minimize cost:

a. Using Nearest Neighbor starting at building A

b. Using Repeated Nearest Neighbor

c. Using Sorted Edges

23. Find a minimum cost spanning tree for the graph you created in problem #3