Exam 2: Business Efficiency

Construct an example of a connected graph that does not have a Hamiltonian circuit.

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

The minimum-cost spanning tree produced by applying Kruskal's algorithm may contain the most expensive edge of the graph.

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A?

When Kruskal's algorithm is used to find a minimum-cost spanning tree on a graph, which of the following is false?

The graph below shows the cost (in hundreds of dollars) of installing telephone wires between the workspaces in an office complex. Use Kruskal's algorithm for minimum-cost spanning trees to find the cost for establishing this phone network.

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

The nearest-neighbor algorithm for solving the traveling salesman problem always produces the same result as the sorted-edges algorithm.

Kris has three pairs of pants of different colors, five shirts of different colors, and two pairs of shoes. How many different outfits can Kris create?

For the graph below, which routing is produced by using the nearest-neighbor algorithm starting at D?

The best-known guarantee for a heuristic algorithm for a traveling salesman problem yields a cost no worse than one and a half times the optimal cost.

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A?

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the sorted-edges algorithm?

How many distinct Hamiltonian circuits can you find on the following graph? (Do not count a circuit and the reverse of the same circuit as distinct.)

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the sorted-edges algorithm?

What is the earliest possible completion time for a job whose order-requirement is shown below?

In which of the diagrams below do the wiggly edges represent spanning trees?

You want to create a mileage grid showing the distance between every pair of the 50 U.S. state capitals. How many numbers will you have to compute?

A college student has six pairs of pants, eight T-shirts, three sweatshirts, and two pairs of tennis shoes. If an outfit consists of pants, a T-shirt, a sweatshirt, and a pair of tennis shoes, how many different outfits can the student wear before repeating one?

In which of the diagrams below do the wiggly edges represent spanning trees?