March 11 Graph Theory Unit Test

3

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

3

The graph above is connected.

3

What is the degree of D?

3

DH is a bridge.

3

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

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

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

5

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.

5

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

5

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.

3

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

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

The graph above is a tree.

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

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.

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.