Deck 14: Available Online: Other Mathematical Systems

Question 1

$$\text { Determine whether or not the graph is a tree. If it is not, explain why. }$$

A) The graph is not a tree because two edges overlap.
B) The graph is not a tree because it is disconnected.
C) The graph is not a tree because it contains a circuit.
D) The graph is a tree.

Answer 1

The graph is not a tree because it is disconnected.

Question 2

$\text { Find a Hamiltonian circuit. }$

A) F, D, C, B, A, E, D, F
B) E, B, A, D, F, C, E
C) A, E, B, C, F, D, E, A
D) F, D, E, A, B, C, F

Answer 2

F, D, E, A, B, C, F

Question 3

Determine if an Euler path or an Euler circuit exists so that a person who plows the roads does not have to pass over any street twice. If an Euler path or an Euler circuit exists, find one. The intersections of the streets have been labeled for you.

A) Euler path: C-B-A-H-G-I-J-F-E-D-C-F
B) Euler circuit: B-A-H-G-B-C-D-E-F-G-I-J-F-C-B
C) Euler path: B-A-H-G-B-C-D-E-F-G-I-J-F-C
D) neither exists

Answer 3

Euler path: B-A-H-G-B-C-D-E-F-G-I-J-F-C

Question 4

$$\text { Determine whether or not the graph is a tree. If it is not, explain why. }$$

A) The graph is not a tree because it contains a circuit.
B) The graph is not a tree because two edges overlap.
C) The graph is not a tree because it is disconnected.
D) The graph is a tree.

Question 5

State whether the graph has an Euler path, an Euler circuit, or neither. If it has an Euler path or an Euler circuit, find one.

A) Euler path: A, B, C, D, E, F, G, H, C, A, H
B) Euler circuit: A, B, C, D, E, F, G, H, A
C) Euler path: A, B, C, D, E, F, G, H, A
D) neither

Question 6

Based on the information in the table, use the brute force method to find the shortest routefrom Angleton to all the other cities and back to Angleton.

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\text { Distance (in miles) between Cities }$
$\begin{array}{l|cccc} & \text { Angleton } & \text { Benton } & \text { Coppell } & \text { Doran } \\\hline \text { Angleton } & - & 60 & 66 & 61 \\\text { Benton } & 60 & - & 48 & 74 \\\text { Coppell } & 66 & 48 & - & 55 \\\text { Doran } & 61 & 74 & 55 & -\end{array}$

A) 255 miles
B) 249 miles
C) 215 miles
D) 224 miles

Question 7

$$\text { Use the nearest neighbor method to approximate the optimal solution. Start at vertex A. }$$

A) 304
B) 238
C) 213
D) 303

Question 8

Decide whether the connected graph has an Euler path, an Euler circuit, an Euler circuit butnot an Euler path, or neither an Euler circuit nor an Euler path. The graph has 2 odd vertices and 2 even vertices.

A) Euler circuit but not an Euler path
B) Euler path
C) neither an Euler circuit nor an Euler path
D) Euler circuit

Question 9

Decide whether the connected graph has an Euler path, an Euler circuit, an Euler circuit butnot an Euler path, or neither an Euler circuit nor an Euler path. The graph has 4 odd vertices and 5 even vertices.

A) Euler circuit
B) Euler circuit but not an Euler path
C) neither an Euler circuit nor an Euler path
D) Euler path

Question 10

Question 11

$$\text { List the odd vertices of the graph. }$$

A) B, C
B) A, B, C, D, E, F
C) A, D, E, F
D) A, D

Question 12

Question 13

Find the number of Hamilton circuits if a complete graph has five vertices.

A) 24
B) 32
C) 720
D) 120

Question 14

$$\text { How many edges does the graph have? }$$

A) 4
B) 6
C) 7
D) 1

Question 15

Based on the information in the table, use the nearest neighbor method to find an approximation to the shortest route from Angleton to all the other cities and back to Angleton.

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\text { Distance (in miles) between Cities }$
$\begin{array}{l|cccc} & \text { Angleton } & \text { Benton } & \text { Coppell } & \text { Doran } \\\hline \text { Angleton } & - & 60 & 69 & 65 \\\text { Benton } & 60 & - & 50 & 74 \\\text { Coppell } & 69 & 50 & - & 52 \\\text { Doran } & 65 & 74 & 52 & -\end{array}$

A) 243 miles
B) 227 miles
C) 255 miles
D) 258 miles

Question 16

$$\text { Use the brute force method to find the optimal solution for the weighted graph. }$$

A) 246
B) 209
C) 221
D) 249

Question 17

$$\text { Determine whether or not the graph is a tree. If it is not, explain why. }$$

A) The graph is not a tree because it contains a circuit.
B) The graph is a tree.
C) The graph is not a tree because two edges overlap.
D) The graph is not a tree because it is disconnected.

Question 18

$$\text { Find a circuit that includes vertex } \mathrm { C } \text {. }$$

A) C, D, A, B, C
B) C, D, F, C
C) C, D, A, B
D) C, D, F, D, C

Question 19

Question 20

Edges may be removed from the graph that follows so that is becomes a spanning tree. Identify a set of edges that can be removed to accomplish this.

A) EF and EH
B) GH and FG
C) GH and HI
D) HI and FI

Question 21

State whether the graph has an Euler path, an Euler circuit, or neither. If it has an Euler path or an Euler circuit, find one.

A) neither
B) Euler circuit: A, B, C, D, E, F, D, G, H, C, A
C) Euler path: H, C, A, B, C, D, E, F, D, G
D) Euler path: H, C, A, B, C, D, E, F, D, G, H, G

Question 22

Question 23

$$\text { Find a Hamiltonian path. }$$

A) F, D, C, B, A, E
B) D, E, A, B, C, D, F
C) F, D, A, B, C, E
D) E, A, D, C, B, A, D, F

Question 24

At a concert, the production manager needs to run electricity to several lights. The distances in feet are shown. Use a minimum spanning tree to determine the shortest amount of wire that will be needed.

A) 172 feet
B) 176 feet
C) 181 feet
D) 192 feet

Question 25

$$\text { List the edges that are bridges. }$$

A) AE, BC, DF
B) A, D
C) AE, DF
D) E, F

Question 26

$$\text { List the vertices of the graph. }$$

A) A, F
B) A, B, C, D
C) B, C, D, E
D) A, B, C, D, E, F

Question 27