MTH109_Mod 2_Mastery Exercise

Incorrect Question 1 0 / 1 pts Suppose that a town has 7 bridges as pictured below. Determine if the following statement is true or false. There is a path that crosses all bridges exactly once. True False Actually, the graph modeling this scenario, with vertices representing the land masses and edges representing bridges, has exactly two odd vertices. Thus, by Euler’s theorem there is a Euler path in the graph, i.e., there is a path crossing every bridge exactly once. For more information about how to determine if a graph contains a Euler path, review Chapter 6 in the textbook and the Module 2 lecture page “Euler Circuits and the Chinese Postman Problem”. Incorrect Question 2 0 / 1 pts Determine which of the following subgraphs is the minimum cost spanning tree in the graph below.

Actually, the subgraph in option (b) is the minimum cost spanning tree in the given graph. Options (a) and (d) have higher cost and option (c) is not a spanning tree. For more information about how to find the minimum cost spanning tree, review Chapter 6 in the textbook and the Module 2 lecture page “Trees”. Question 3 1 / 1 pts Shown in the table below are the travel times, in minutes, by high-speed train between four European cities. Determine the time it takes to get from Paris to Brussels if you take the fastest route. Paris Amsterdam Brussels London Paris - 200 - 140 Amsterdam 200 - 110 240 Brussels - 110 - 120

London 140 240 120 - 260 minutes 310 minutes 250 minutes 490 minutes That is correct. There are only three paths from Paris to Brussels in the graph modeling this scenario. The path Paris, London, Brussels takes 260 minutes. The path Paris, London, Amsterdam, Brussels takes 490 minutes. The path Paris, Amsterdam, Brussels takes 310 minutes. Thus, it takes 260 minutes to get from Paris and Brussels if you take the fastest route. Question 4 1 / 1 pts Shown in the table below are the one-way airfares between five cities. Determine which of the following graphs best models this data. Honolulu London Moscow Cairo Seattle $159 $370 $654 $684 Honolulu - $830 $854 $801 London $830 - $245 $323 Moscow $854 $245 - $329

That is correct. Option (c) is the graph that best models the given data by using a vertex to represent each city and a weighted edge to represent the cost of the flight between each pair of cities. Question 5 1 / 1 pts A tourist wants to visit seven cities in Israel, starting from Jerusalem. The table below shows the driving distances, in kilometers, between the cities. Use the Nearest neighbor algorithm to find a route for the person to follow, returning to Jerusalem.   Jerusalem Tel Aviv Haifa Tiberias Beer Sheba Eilat Jerusalem - 58 151 152 81 309 Tel Aviv 58 - 95 134 105 346 Haifa 151 95 - 69 197 438 Tiberias 152 134 69 - 233 405 Beer Sheba 81 105 197 233 - 241 Eilat 309 346 438 405 241 -

Nazareth 131 102 35 29 207 488 J, T, N, H, TA, E, BS, J J , TA , H , N , T , BS , E , J J , TA , H , N , T , E , BS , J J , BS , E , T , N , H , TA , J That is correct. Using the Nearest neighbor algorithm starting from Jerusalem, the route the person should follow is J , TA , H , N , T , BS , E , J. Question 6 1 / 1 pts Determine a set of possible steps to take while applying Kruskal’s algorithm to find the minimum cost spanning tree in the following graph.

Determine which of the following statements about the graph below is true. Vertices A and C are adjacent. Vertex H has degree 1. Vertices G and H are adjacent. Vertex G has degree 2. That is correct. Vertices A and C are adjacent because they are connected by an edge. Vertices G and H are not adjacent because they are not connected by an edge, vertex H has degree 2 because the loop meets this vertex twice and vertex G has degree 1 because it only has an edge connected to it. Question 8 1 / 1 pts Determine which of the subgraphs highlighted below is a spanning tree.

highlighted has a circuit and thus, is not a tree. Option (d) is not a spanning tree because it does not contain all vertices in the original graph. Question 9 1 / 1 pts Determine which of the following sets is the set of vertices in the graph below. A , B , C , D , E , F , G AB , AC , AF , BC , CD , DE , DF , EF , FG , HH A , B , C , D , E , F , G , H AB , AC , AF , BC , CD , DE , DF , EF , FG , GH , HH That is correct. The set of vertices in the given graph is A , B , C , D , E , F , G , H . The set A , B , C , D , E , F , G is missing vertex H , and the other two sets contain edges. Question 10 1 / 1 pts Determine which of the following graphs best models the layout of the city pictured below.

That is correct. Option (a) is the graph that best models the layout of the given city because it has three vertices, one for each land mass, and three edges representing the bridges connecting the land masses. Note that land masses B and C are connected by two bridges and land masses A and B are connected by one bridge. Question 11 1 / 1 pts Find an optimal Hamiltonian circuit in the following graph.

A , C , B , D , A A , B , C , D , A A , D , B , C , A A , B , D , C , A That is correct. Using the Brute force algorithm, we get that an optimal Hamiltonian circuit in the given graph is A , B , D , C , A with a total length of 108. Options (a) and (c) have length 126, and option (b) has length 112. Question 12 1 / 1 pts Determine which of the following statements about the graph below is false.

A , B , C , F , C , D , E , F , G , H , A A , H , I , J , G , F , E , D , C , B , A A , B , C , F , C , D , E , F , G , H , I , J , G , H , A A , H , I , J , G , H , G , F , C , F , E , D , C , B , A Question 14 1 / 1 pts The table below shows the distance driving between five cities in the Dallas area. Determine which of the following statements is true.   Plano Mesquite Arlington Fort Worth 50 46 16 Plano - 25 40 Mesquite 25 - 41

Arlington 40 41 - The Nearest neighbor algorithm results in an optimal Hamiltonian circuit. The Repeated nearest neighbor algorithm does not result in an optimal Hamiltonian circuit. The Brute force algorithm results in an optimal Hamiltonian circuit, but the Nearest neighbor algorithm does not. The Repeated nearest neighbor algorithm results in an optimal Hamiltonian circuit, but the Nearest neighbor algorithm does not. That is correct. The Nearest neighbor algorithm results in an optimal Hamiltonian circuit. In fact, so do the Brute force algorithm and the Repeated nearest neighbor algorithm. Question 15 1 / 1 pts Determine a set of possible steps to take while applying Fleury’s algorithm to find a Euler path in the following graph.