Deck 2: Business Efficiency

Question 1

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.

Answer 1

Answers will vary. One solution is:

Question 2

You want to create a mileage grid showing the distance between every pair of the 10 Canadian provincial and territorial capitals. How many numbers will you have to compute?

Answer 2

(10)(9)/2 = 45

Question 3

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

Answer 3

Answers will vary. One solution is:

Question 4

You own a chain of 12 apartment complexes (including your residence) and you want to plan a trip to visit each of your properties. If it takes 1/2 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?

Question 5

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?

Question 6

What is a disadvantage of a heuristic algorithm?

Question 7

Identify six tasks necessary when building a sandwich, and construct a digraph for these tasks.

Question 8

Construct a complete graph on four vertices.

Question 9

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

Question 10

What is an advantage of a heuristic algorithm?

Question 11

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?

Question 12

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

Question 13

Construct an example of a graph with no Hamiltonian circuit.

Question 14

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

Question 15

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?

Question 16

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?

Question 17

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

Question 18

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

Question 19

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

Question 20

Identify six tasks necessary when preparing for a picnic, and construct a digraph for these tasks.

Question 21

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

Question 22

Which of the following describes a Hamiltonian circuit for the graph below?

A) ABCDEFJIHG
B) ABCDEAFJDIHBGFEJICHGA
C) ABCDEAGHIJFA
D) AEDCBGHIJFA

Question 23

Will the nearest-neighbor algorithm ever use the most expensive edge of a graph?

Question 24

Which of the following describes a Hamiltonian circuit for the graph below?

A) ABCDEJHIGF
B) AEDCBGIHJFA
C) ABCDEAFGHIJFA
D) ABCDEAFGBGIDIHCHJEJFA

Question 25

The route of a delivery truck generally follows a Hamiltonian circuit. Under what circumstances should it instead follow an Euler circuit?

Question 26

What is critical about the critical path of an order-requirement digraph?

Question 27

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?

Question 28

In the graph below, construct a Hamiltonian circuit.

Question 29

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?

Question 30

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

A) ABCDA
B) ABDCA
C) ACBDA
D) ABCD

Question 31

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.)

Question 32

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

Question 33

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

Question 34

Which of the following describes a Hamiltonian circuit for the graph below?

A) ABCDEFGA
B) ACBAEGFDEA
C) ACBFGDEA
D) ABCDGEF

Question 35

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

Question 36

How many distinct Hamiltonian circuits can you find on the following graph?

Question 37

In the graph below, construct a Hamiltonian circuit.

Question 38

The route of a neighborhood garbage truck generally follows an Euler circuit. Under what circumstances should it instead follow a Hamiltonian circuit?

Question 39

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

Question 40

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

Question 41

On a map there are roads from town A of length 10, 26, 12, and 50 miles. Using the nearest-neighbor algorithm for finding a Hamiltonian circuit starting at town A, which road would be traveled first?

A) Road of length 10
B) Road of length 26
C) Road of length 12
D) Road of length 50

Question 42

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

A) 3
B) 6
C) 12
D) 24

Question 43

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

A) 60
B) 120
C) 360
D) 720

Question 44

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

A) 120
B) 60
C) 24
D) 12

Question 45

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

A) 20
B) 14
C) 19
D) 22

Question 46

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

A) 10
B) 11
C) 14
D) 15

Question 47

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

A) 5
B) 9
C) 12
D) 15

Question 48

On the graph below, which algorithm has different routing from others to solve the traveling salesman problem?

A) The sorted-edges algorithm
B) The nearest-neighbor algorithm starting from A
C) The nearest-neighbor algorithm starting from B
D) The nearest-neighbor algorithm starting from D

Question 49

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

A) 23
B) 20
C) 16
D) 5

Question 50

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

A) 215
B) 220
C) 235
D) 295

Question 51

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

A) 22
B) 28
C) 32
D) 49

Question 52

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

A) 40
B) 58
C) 60
D) 66

Question 53

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

A) 47
B) 25
C) 22
D) 15

Question 54

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

A) 60
B) 54
C) 62
D) 66

Question 55

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

A) 215
B) 220
C) 235
D) 295

Question 56

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

A) 360
B) 720
C) 2520
D) 5040

Question 57

If the order-requirement digraph for a collection of tasks is shown below, then what is the minimum completion time for the collection of tasks?

A) 64 minutes
B) 43 minutes
C) 36 minutes
D) 28 minutes

Question 58

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

A) ADCBFGHEA
B) ABCDHGFE
C) ABCDHGFEA
D) ABCDHGFEHDA

Question 59

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

A) 220
B) 225
C) 235
D) 295

Question 60

Given the order-requirement digraph for a collection of tasks shown below, what would the critical path be?

A) T₁, T₂, T₃
B) T₄, T₂, T₃
C) T₄, T₃
D) T₄, T₅, T₆

Question 61

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

Question 62

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

Question 63

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

A) 27 minutes
B) 17 minutes
C) 21 minutes
D) 48 minutes

Question 64

Suppose an architect needs to design an intercom system for a large office building. Which technique is most likely to be useful in solving this problem?

A) Finding an Euler circuit on a graph
B) Applying the nearest-neighbor algorithm for the traveling salesman problem
C) Applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph
D) None of these techniques is likely to apply

Question 65

Suppose a veteran wants a visit to all the war memorials in Washington, D.C. in one day. Which technique is most likely to be useful in solving this problem?

A) Finding an Euler circuit on a graph
B) Applying the nearest-neighbor algorithm for the traveling salesman problem
C) Applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph
D) None of these techniques is likely to apply

Question 66

The minimum-cost spanning tree produced by applying Kruskal's algorithm will always contain the lowest cost edge of the graph.

Question 67

Suppose an employee of a power company needs to read the electricity meters outside of each house along the streets in a residential area. Which technique is most likely to be useful in solving this problem?

A) Finding an Euler circuit on a graph
B) Applying the nearest-neighbor algorithm for the traveling salesman problem
C) Applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph
D) None of these techniques is likely to apply

Question 68

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

Question 69

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.

Question 70

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

A) 10 minutes
B) 17 minutes
C) 40 minutes
D) 15 minutes

Question 71

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

Question 72

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

Question 73

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

A) 16 minutes
B) 19 minutes
C) 30 minutes
D) 60 minutes

Question 74

A heuristic algorithm will always produce optimal results.

Question 75

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

A) 15 minutes
B) 22 minutes
C) 34 minutes
D) 19 minutes

Question 76

A digraph is a graph with exactly two vertices.

Question 77

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

A) Circuits are not permitted in the tree.
B) The tree contains the edge of the graph of minimum cost.
C) The tree is not necessarily connected.
D) The tree may contain the edge of the highest cost.

Question 78

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

Question 79

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

Question 80

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