Scheduling Practice Assignment | Essay Help Services

Hello Must show work clearly. If you are doing on a separate sheet of paper, you need to copy the graph as well as the table to complete the work

Total Points: 20

1. Find two different Hamiltonian circuits in the following graph.

2. a. How many different Hamiltonian circuits are there in a complete graph with 8 vertices?

_______________

1. How many edges does the same graph have? ______________

3. Nicole wants to tour Asia. She will start and end her journey in Tokyo and visit four other cities: Hong Kong, Bangkok, Seoul and Beijing. The airfares between the cities is given in the following table in US Dollars. Draw a weighted graph to represent the data and find an optimal route using the repeated neighbor algorithm.

4. Find a route for the above problem # 3 using the Cheapest Link Algorithm.
5. Find the minimum cost spanning tree on the graph above using Kruskal’s algorithm.

6. a. How many edges are there in a complete graph of 6 vertices?
7. How many edges are there in a complete graph of 7 vertices?
8. What is the difference in the number of edges in answers a and b. How do you explain it?

7. Explain why a graph that has a bridge cannot have a Hamilton circuit.

8 Find an optimal eulerization of the graph to the right.

9. A city has hired you to plan a parade route. A layout of the city with land masses and bridges is shown to the right. Draw a graph that models the layout of the city.