Exam 2: Business Efficiency

The local cafe offers three different entrees, 10 different vegetables, and four different salads. A "blue plate special" includes an entree, a vegetable, and a salad. How many different ways can a special be constructed?

Which path listed forms a Hamiltonian circuit on the graph below?

When the traveling salesman problem (Hamiltonian circuit) is applied to six cities, how many tours are possible?

The sorted-edges algorithm for solving the traveling salesman problem always gives optimal results.

A connected graph H has a spanning tree with 50 edges. How many vertices does the spanning tree have? How many vertices does H have? What can one say about the number of edges H has?

On the graph below, which routing is produced by using the nearest-neighbor algorithm to solve the traveling salesman problem, starting at A?

Construct a complete graph whose vertices represent the six largest islands of Hawaii: Kauai, Oahu, Molokai, Lanai, Maui, and Hawaii.

Construct a digraph for the following tasks necessary when building a house: get a building permit, install wiring, pour foundation, build walls, build doghouse, pass final inspection.

When the traveling salesman problem (Hamiltonian circuit) is applied to six cities, how many distinct circuits are possible?

A connected graph G has 32 vertices. How many vertices does a spanning tree of G have?

If a graph of nine vertices is complete, how many edges are there?

The path produced by the nearest-neighbor algorithm when solving the traveling salesman problem may be dependent on the starting city.

There are 3, 4, and 3 distinct paths from the city A to B, B to C, and C to D, respectively. Starting from the city A, you are planning to travel those cities in the order B, C, and D. How many different travel routes are possible?

Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. What is the cost of the tree found?

In the graph below, construct a Hamiltonian circuit.

A nearby ice cream shop offers 31 different flavors and three different types of cones. How many different single scoop cones can be ordered?

Use the brute force algorithm to solve the traveling salesman problem for the graph of the four cities shown below.

For a connected graph of 18 vertices, every possible spanning tree has exactly 17 edges.

Making the best choice at each stage for solving the traveling salesman problem always gives optimal results.

What is a disadvantage of a heuristic algorithm?