March 11 Graph Theory Unit Test

Last updated about 5 years ago

19 questions

3

10

3

5

3

5

10

5

10

3

10

3

8

Library

March 11 Graph Theory Unit Test

Last updated about 5 years ago

19 questions

3

What is the degree of D?

3

10

To get full credit explain in full detail with specific information relating to Euler's Theorem why the graph has no Euler paths or Euler circuits.

3

5

3

5

Determine the number of Hamilton circuits in a complete graph with 8 vertices.

10

5

10

Jon is a traveling salesman for a pharmaceutical company. His territory includes 5 cities and he needs to find the least expensive route to the cities and home.
a. Starting at city A find the optimal route using the Nearest Neighbor Method.
b. Give the total cost of his trip.

3

10

Your goal is to assign a meeting day (Monday - Friday) to each club in such a way that no 2 clubs share a member meet on the same day.
a. Draw a graph that models the problem.
b. Color the club-scheduling graph using as few colors as possible.
c. Make a schedule for the classes based on your colored graph.

3

Find a spanning tree for the graph. Answers will vary because many spanning trees are possible.

8

A) Use Kuskal's Algorithm to find the minimum spanning tree for the weighted graph
B) Give the total weight of the minimum spanning tree.

Which of the following is a possible representation for the graph with the given edges QR, RS, RT, and SS

None of these

The graph above is connected.

True

False

What is the degree of D?

DH is a bridge.

True

False

Determine whether the given path is an Euler Path, Euler Circuit or Neither?
F,A,B,G,D,B,C,D,G,F

Euler Circuit

Euler Path

Neither

To get full credit explain in full detail with specific information relating to Euler's Theorem why the graph has no Euler paths or Euler circuits.

An Euler Circuit always starts and ends at the same vertex.

True

False

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 82 even vertices and no odd vertices.

Euler circuit

Euler path

neither

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 81 even vertices and two odd vertices

Euler circuit

neither

Euler path

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 35 even vertices and three odd vertices.

Euler path

Euler circuit

neither

A Hamilton path must contain every edge in the graph exactly once.

True

False

Determine the number of Hamilton circuits in a complete graph with 8 vertices.

Jon is a traveling salesman for a pharmaceutical company. His territory includes 5 cities and he needs to find the least expensive route to the cities and home.
a. Starting at city A find the optimal route using the Nearest Neighbor Method.
b. Give the total cost of his trip.

The graph above is a tree.

True

False

Your goal is to assign a meeting day (Monday - Friday) to each club in such a way that no 2 clubs share a member meet on the same day.
a. Draw a graph that models the problem.
b. Color the club-scheduling graph using as few colors as possible.
c. Make a schedule for the classes based on your colored graph.

Find a spanning tree for the graph. Answers will vary because many spanning trees are possible.

A) Use Kuskal's Algorithm to find the minimum spanning tree for the weighted graph
B) Give the total weight of the minimum spanning tree.

Which of the following is a possible representation for the graph with the given edges QR, RS, RT, and SS

None of these

The graph above is connected.

True

False

DH is a bridge.

True

False

Determine whether the given path is an Euler Path, Euler Circuit or Neither?
F,A,B,G,D,B,C,D,G,F

Euler Circuit

Euler Path

Neither

An Euler Circuit always starts and ends at the same vertex.

True

False

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 82 even vertices and no odd vertices.

Euler circuit

Euler path

neither

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 81 even vertices and two odd vertices

Euler circuit

neither

Euler path

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 35 even vertices and three odd vertices.

Euler path

Euler circuit

neither

A Hamilton path must contain every edge in the graph exactly once.

True

False

The graph above is a tree.

True

False

March 11 Graph Theory Unit Test

March 11 Graph Theory Unit Test

What is the degree of D?

To get full credit explain in full detail with specific information relating to Euler's Theorem why the graph has no Euler paths or Euler circuits.

Determine the number of Hamilton circuits in a complete graph with 8 vertices.

Jon is a traveling salesman for a pharmaceutical company. His territory includes 5 cities and he needs to find the least expensive route to the cities and home. a. Starting at city A find the optimal route using the Nearest Neighbor Method.b. Give the total cost of his trip.

Find a spanning tree for the graph. Answers will vary because many spanning trees are possible.

A) Use Kuskal's Algorithm to find the minimum spanning tree for the weighted graphB) Give the total weight of the minimum spanning tree.

Which of the following is a possible representation for the graph with the given edges QR, RS, RT, and SS

The graph above is connected.

What is the degree of D?

DH is a bridge.

Determine whether the given path is an Euler Path, Euler Circuit or Neither?F,A,B,G,D,B,C,D,G,F

To get full credit explain in full detail with specific information relating to Euler's Theorem why the graph has no Euler paths or Euler circuits.

An Euler Circuit always starts and ends at the same vertex.

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.The graph has 82 even vertices and no odd vertices.

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.The graph has 81 even vertices and two odd vertices

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.The graph has 35 even vertices and three odd vertices.

A Hamilton path must contain every edge in the graph exactly once.

Determine the number of Hamilton circuits in a complete graph with 8 vertices.

Jon is a traveling salesman for a pharmaceutical company. His territory includes 5 cities and he needs to find the least expensive route to the cities and home. a. Starting at city A find the optimal route using the Nearest Neighbor Method.b. Give the total cost of his trip.

The graph above is a tree.

Find a spanning tree for the graph. Answers will vary because many spanning trees are possible.

A) Use Kuskal's Algorithm to find the minimum spanning tree for the weighted graphB) Give the total weight of the minimum spanning tree.

Jon is a traveling salesman for a pharmaceutical company. His territory includes 5 cities and he needs to find the least expensive route to the cities and home.
a. Starting at city A find the optimal route using the Nearest Neighbor Method.
b. Give the total cost of his trip.

A) Use Kuskal's Algorithm to find the minimum spanning tree for the weighted graph
B) Give the total weight of the minimum spanning tree.

Determine whether the given path is an Euler Path, Euler Circuit or Neither?
F,A,B,G,D,B,C,D,G,F

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 82 even vertices and no odd vertices.

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 81 even vertices and two odd vertices

Use Euler's Theorem to determine whether the graph has an Euler path (but not an Euler circuit), Euler circuit, or neither.
The graph has 35 even vertices and three odd vertices.

Jon is a traveling salesman for a pharmaceutical company. His territory includes 5 cities and he needs to find the least expensive route to the cities and home.
a. Starting at city A find the optimal route using the Nearest Neighbor Method.
b. Give the total cost of his trip.

A) Use Kuskal's Algorithm to find the minimum spanning tree for the weighted graph
B) Give the total weight of the minimum spanning tree.