Question 1

The edges in a certain graph represent roads, and the vertices represent intersections. We want to time the traffic signals at each intersection and not visit any intersection twice. Should we look for an Euler circuit or a Hamilton circuit?

Accepted Answer

A Hamilton circuit visits every vertex exactly once, which is what we want to do when timing the traffic signals at each intersection without revisiting any intersection. On the other hand, an Euler circuit visits every edge exactly once which does not necessarily guarantee that we can visit every intersection exactly once without backtracking. Therefore, we should look for a Hamilton circuit.

Question 2

Find a Hamilton circuit for the figure below.

Accepted Answer

The answer of Find a Hamilton circuit for the figure...

Question 3

If each vertex of a graph is connected to every other vertex by an edge, then it is called a(n) _______________ graph.

Accepted Answer

A complete graph is defined as a graph where every pair of distinct vertices is connected by a unique edge. Thus, if each vertex is connected to every other vertex, it must necessarily be a complete graph. Hamilton and Euler graphs are types of paths/cycles within a graph, while direct graphs have directed edges.

Question 4

The edges in a certain graph represent roads, and the vertices represent intersections. We want to clean all of the roads and not require the street sweeper to move along streets that have already been cleaned. Should we look for an Euler circuit or a Hamilton circuit?

Accepted Answer

An Euler circuit is the correct choice because it involves traversing every edge (road) exactly once, which aligns with the goal of cleaning all roads without retracing any.

Question 5

The following table shows the distance (in miles) between cities A, B, C, and D. When a traveling salesman visits all four cities, how many miles does he travel if he uses the cheapest link algorithm?

Accepted Answer

The answer of The following table shows the distance (in...

Question 6

Finding a Hamilton circuit with the shortest distance for a given complete graph is called _______________.

Accepted Answer

The problem of finding a Hamilton circuit with the shortest distance for a given complete graph is commonly known as the traveling salesman problem.

Question 7

A traveling salesman must visit all four cities indicated in the figure below. When he starts in A, what is the second city to visit according to the nearest-neighbor algorithm?

Accepted Answer

According to the nearest-neighbor algorithm, the salesman chooses the nearest unvisited city as the next destination. In this case, the nearest unvisited city from A is B, so the salesman visits B second.

Question 8

If a graph has a vertex of degree _____, then each edge meeting that vertex must be part of any Hamilton circuit.

Accepted Answer

The answer of If a graph has a vertex of...

Question 9

When applying the nearest-neighbor algorithm, if there are two or more vertices equally nearby, any one of them may be selected.

Accepted Answer

In the case of a tie between two or more vertices, any one of them may be selected.

Question 10

When applying the cheapest-link algorithm, do not choose an edge that would result in a vertex of degree ___.

Accepted Answer

The cheapest-link algorithm avoids choosing an edge that would result in a vertex of degree 3 to prevent the creation of sub-tours, ensuring a single tour is formed for the solution.

Question 11

The nearest-neighbor algorithm constructs a(n) _______________ circuit in a complete graph by starting at a vertex.

Accepted Answer

The nearest-neighbor algorithm constructs a Hamiltonian circuit in a complete graph by starting at a vertex and connecting to the closest unvisited vertex until all vertices have been visited. Therefore, the best choice is D, Hamilton, as it is the only option that represents a circuit in a complete graph that visits each vertex exactly once.

Question 12

Find a Hamilton circuit for the figure below.

Accepted Answer

Starting at A, the circuit can go to F, then C, then D, then E, then B, and finally back to A, forming the Hamilton circuit AFCDEBA.

Question 13

The following table shows the distance (in miles) between cities A, B, C, and D. When a traveling salesman visits all four cities, how many miles does he travel if he starts in city A and uses the nearest-neighbor algorithm?

Accepted Answer

The answer of The following table shows the distance (in...

Question 14

How many smaller circuits can be a part of a Hamilton circuit?

Accepted Answer

A Hamilton circuit must visit every vertex exactly once. Therefore, there can only be one circuit that includes all the vertices. If there were smaller circuits within the Hamilton circuit, that would mean some vertices are not part of the smaller circuits and therefore not being visited exactly once, violating the definition of a Hamilton circuit.

Question 15

If a circuit of a graph visits each vertex exactly once, then it is called a(n) _______________.

Accepted Answer

A Hamilton circuit in a graph is a circuit that visits each vertex exactly once. Euler circuits, on the other hand, involve traversing each edge exactly once, not necessarily each vertex. Vector circuits and Fleury circuits are not standard terms in the context of graph theory for describing a circuit that visits each vertex exactly once.

Question 16

A traveling salesman must visit all four cities indicated in the figure below. Which is the shortest route he can take if he wants to begin and end in city A?

Accepted Answer

The answer of A traveling salesman must visit all four...

Question 17

A traveling salesman must visit all four cities indicated in the figure below. How many miles does he travel if he starts in A and then visits B, C, and D before returning to A?

Accepted Answer

The answer of A traveling salesman must visit all four...

Question 18

The graph below has two odd-degree vertices, so no Euler circuit exists. Suppose we would like to find a route that backtracks as little as possible. What duplicate edge could we create to help us find this route?

Accepted Answer

The answer of The graph below has two odd-degree vertices,...

Question 19

Which of the following is not a practical situation where finding an Euler circuit may be important?

Accepted Answer

An Euler circuit is a path through a graph that visits every edge exactly once and returns to the starting vertex. This concept is often used in practical situations that involve traversing a network without retracing any steps, which is important for efficiency.
A) Delivery of groceries - This could potentially involve an Euler circuit if the goal is to deliver groceries along various routes without retracing any paths, ensuring that each street is visited only once.
B) Garbage pickup - Similar to grocery delivery, garbage pickup routes can be optimized using an Euler circuit to ensure that each street is visited once, which can save time and fuel.
C) Street sweepers - Street sweepers can use an Euler circuit to clean streets without passing the same street more than once, which is an efficient way to cover an entire area.
D) Driving kids to school - This situation is less likely to require an Euler circuit because the route might not need to cover every street, and the path may involve backtracking or taking the shortest or fastest route rather than covering every edge in a network. Additionally, the priority in this situation is often time-sensitive and based on a fixed schedule, which may not align with the requirements of an Euler circuit.

Question 20

If a complete graph has five vertices, then how many edges are in the graph?

Accepted Answer

A complete graph with $n$ vertices has $\frac{n(n-1)}{2}$ edges. For $n=5$, this gives $\frac{5(5-1)}{2} = \frac{5 \times 4}{2} = 10$ edges.

Quiz 7: Graph Theory

The edges in a certain graph represent roads, and the vertices represent intersections. We want to time the traffic signals at each intersection and not visit any intersection twice. Should we look for an Euler circuit or a Hamilton circuit?

Find a Hamilton circuit for the figure below.

If each vertex of a graph is connected to every other vertex by an edge, then it is called a(n) _______________ graph.

The edges in a certain graph represent roads, and the vertices represent intersections. We want to clean all of the roads and not require the street sweeper to move along streets that have already been cleaned. Should we look for an Euler circuit or a Hamilton circuit?

The following table shows the distance (in miles) between cities A, B, C, and D. When a traveling salesman visits all four cities, how many miles does he travel if he uses the cheapest link algorithm?

Finding a Hamilton circuit with the shortest distance for a given complete graph is called _______________.

A traveling salesman must visit all four cities indicated in the figure below. When he starts in A, what is the second city to visit according to the nearest-neighbor algorithm?

If a graph has a vertex of degree _____, then each edge meeting that vertex must be part of any Hamilton circuit.

When applying the nearest-neighbor algorithm, if there are two or more vertices equally nearby, any one of them may be selected.

When applying the cheapest-link algorithm, do not choose an edge that would result in a vertex of degree ___.

The nearest-neighbor algorithm constructs a(n) _______________ circuit in a complete graph by starting at a vertex.

Find a Hamilton circuit for the figure below.

The following table shows the distance (in miles) between cities A, B, C, and D. When a traveling salesman visits all four cities, how many miles does he travel if he starts in city A and uses the nearest-neighbor algorithm?

How many smaller circuits can be a part of a Hamilton circuit?

If a circuit of a graph visits each vertex exactly once, then it is called a(n) _______________.

A traveling salesman must visit all four cities indicated in the figure below. Which is the shortest route he can take if he wants to begin and end in city A?

A traveling salesman must visit all four cities indicated in the figure below. How many miles does he travel if he starts in A and then visits B, C, and D before returning to A?

The graph below has two odd-degree vertices, so no Euler circuit exists. Suppose we would like to find a route that backtracks as little as possible. What duplicate edge could we create to help us find this route?

Which of the following is not a practical situation where finding an Euler circuit may be important?

If a complete graph has five vertices, then how many edges are in the graph?