Chapter 14

In Exercises 5-6, draw two equivalent graphs for each description. The vertices are \(A, B, C\), and \(D\). The edges are \(A B, B C, B D\), \(C D\), and \(C C\).

Draw two equivalent graphs for each description. The vertices are \(A, B, C\), and \(D\). The edges are \(A D, B C, D C\), \(B B\), and \(D B\)

Eight students form a math homework group. The students in the group are Zeb, Stryder, Amy, Jed, Evito, Moray, Carrie, and Oryan. Prior to forming the group, Stryder was friends with everyone but Moray. Moray was friends with Zeb, Amy, Carrie, and Evito. Jed was friends with Stryder, Evito, Oryan, and Zeb. Draw a graph that models pairs of friendships among the eight students prior to forming the math homework group.

An environmental action group has six members, A, B, C, D, \(\mathrm{E}\), and F. The group has three committees: The Preserving Open Space Committee (B, D, and F), the Fund Raising Committee (B, C, and D), and the Wetlands Protection Committee (A, C, D, and E). Draw a graph that models the common members among committees. Use vertices to represent committees and edges to represent common members.

In Exercises 11-16, a graph with no loops or more than one edge between any two vertices is described. Which one of the following applies to the description? i. The described graph is a tree. ii. The described graph is not a tree. iii. The described graph may or may not be a tree. The graph has five vertices, and there is exactly one path from any vertex to any other vertex.

A graph with no loops or more than one edge between any two vertices is described. Which one of the following applies to the description? i. The described graph is a tree. ii. The described graph is not a tree. iii. The described graph may or may not be a tree. The graph has five vertices, is connected, and every edge is a bridge.

A graph with no loops or more than one edge between any two vertices is described. Which one of the following applies to the description? i. The described graph is a tree. ii. The described graph is not a tree. iii. The described graph may or may not be a tree. The graph has eight vertices and five edges.

In Exercises 13-18, a connected graph is described. Determine whether the graph has an Euler path (but not an Euler circuit), an Euler circuit, or neither an Euler path nor an Euler circuit. Explain your answer. The graph has 60 even vertices and no odd vertices.

A graph with no loops or more than one edge between any two vertices is described. Which one of the following applies to the description? i. The described graph is a tree. ii. The described graph is not a tree. iii. The described graph may or may not be a tree. The graph has nine vertices and six edges.

The graph has 60 even vertices and no odd vertices. The graph has 80 even vertices and no odd vertices.

A graph with no loops or more than one edge between any two vertices is described. Which one of the following applies to the description? i. The described graph is a tree. ii. The described graph is not a tree. iii. The described graph may or may not be a tree. The graph has five vertices and four edges.

In Exercises 15-18, determine the number of Hamilton circuits in a complete graph with the given number of vertices. 3

A connected graph is described. Determine whether the graph has an Euler path (but not an Euler circuit), an Euler circuit, or neither an Euler path nor an Euler circuit. Explain your answer. The graph has 58 even vertices and two odd vertices.

A graph with no loops or more than one edge between any two vertices is described. Which one of the following applies to the description? i. The described graph is a tree. ii. The described graph is not a tree. iii. The described graph may or may not be a tree. The graph has four vertices and three edges.

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

A connected graph is described. Determine whether the graph has an Euler path (but not an Euler circuit), an Euler circuit, or neither an Euler path nor an Euler circuit. Explain your answer. The graph has 78 even vertices and two odd vertices.

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

A connected graph is described. Determine whether the graph has an Euler path (but not an Euler circuit), an Euler circuit, or neither an Euler path nor an Euler circuit. Explain your answer. The graph has 57 even vertices and four odd vertices.

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

A connected graph is described. Determine whether the graph has an Euler path (but not an Euler circuit), an Euler circuit, or neither an Euler path nor an Euler circuit. Explain your answer. The graph has 77 even vertices and four odd vertices.

Use a tree to model the parent-child relationships in the following family: Peter has three children: Zoila, Keanu, and Sandra. Zoila has two children: Sean and Helen. Keanu has no children. Sandra has one child: Martin. Use vertices to model the people and edges to represent the parent-child relationships.

Use a tree to model the employee relationships among the chief administrators of a large community college system: Three campus vice presidents report directly to the college president. On two campuses, the academic dean, the dean for administration, and the dean of student services report directly to the vice president. On the third campus, only the academic dean and the dean for administration report directly to the vice president.

What is a tree?

If a graph is given, how do you determine whether or not it is a tree?

Describe the relationship between the number of vertices and the number of edges in a tree.

What is a subgraph?

What is a spanning tree?

Describe how to obtain a spanning tree for a connected graph.

What is a Hamilton path? How does this differ from an Euler path?

What is a Hamilton circuit? How does this differ from an Euler circuit?

In Exercises 49-52, draw a graph with the given characteristics. The graph has four even vertices.

In your own words, briefly describe how to find the minimum spanning tree using Kruskal's Algorithm.

What is a complete graph?

Describe a practical problem that can be solved using Kruskal's Algorithm.

How can you look at a graph and determine if it has a Hamilton circuit?

Draw a graph with the given characteristics. The graph has four odd vertices and at least one loop.

Describe how to determine the number of Hamilton circuits in a complete graph.

Draw a graph with the given characteristics. The graph has eight vertices and exactly one bridge.

What is a weighted graph and what are the weights?

What is a graph? Define vertices and edges as part of your description.

What is the traveling salesperson problem? What is the optimal solution?

Describe how to determine whether or not a point where two of a graph's edges cross is a vertex.

Although the Nearest Neighbor Method does not always give the Hamilton circuit for which the sum of the weights is a minimum, Kruskal's Algorithm always gives the spanning tree with the smallest possible total weight.

Describe the Brute Force Method of solving traveling salesperson problems.

What are equivalent graphs?

Why is the Brute Force Method impractical for large numbers of vertices?

Because a graph can be drawn in many equivalent ways, describe the important part in drawing a graph.

Give an example of a tree with six vertices whose degrees are \(1,1,2,2,2\), and 2 .

Describe the Nearest Neighbor Method for approximating the optimal solution to traveling salesperson problems.

What is meant by the degree of a graph's vertex and how is it determined?