Exam 2: Business Efficiency

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

Find the earliest completion time for the following order-requirement digraph.

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

You own a chain of 10 one-day photo development kiosks and a lab where the photos are developed. Each morning and evening a delivery truck leaves the lab, visits each kiosk, and returns to the lab. If it takes 1/3 minute to compute the total length of a tour, how long will it take to apply the brute force algorithm to find the optimal tour for the delivery truck?

Find the earliest completion time for the following order-requirement digraph.

If you add a new vertex to a complete graph of 10 vertices, how many new edges are needed to make the new graph complete?

Construct a complete graph on four vertices.

Kruskal's algorithm for finding minimum-cost spanning trees always gives optimal results.

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

Construct a graph which has an Euler circuit, but not a Hamiltonian circuit.

Can a graph have a Hamiltonian circuit, but not an Euler circuit?

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

A digraph is a graph with exactly two vertices.

Construct an example of a spanning tree on the graph given below.

A spanning tree of a graph must contain every vertex of the graph.

Suppose a college campus decides to install its own phone lines connecting all of the buildings so that calls may be relayed through one or more buildings before reaching their destination. Which technique is most likely to be useful in solving this problem?

Suppose that after a storm an inspection needs to be made of the sewers along the streets in a small village to make sure local flooding is not due to clogging. Which technique is most likely to be useful in solving this problem?

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

In some states, license plates use a mixture of letters and numerals. How many possible plates could be constructed using three letters followed by four numerals?

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