Home

Chapter5:

Quiz #1

Quiz #1


This activity contains 15 questions.

	Vertex A is adjacent to   every other vertex. vertex C and vertex D only. vertex D only. vertex B and vertex E only. None of the above

	The degree of vertex D is   5 4 3 None of the above

	The degree of vertex C is   4 3 2 5 None of the above

	Which of the following is not a path from vertex D to vertex A?   D, C, C, A D, E, D, C, C, A D, C, A D, E, C, D, A All of the above are paths from D to A.

	Which of the following [A), B), C), or D)] is not a circuit in the graph?   E, D, C, C, E A, D, E, C, A A, D, C, D, E, D, A C, A, D, C All of the above are circuits in the graph.

	Which of the following is a bridge of the graph?   AD BD CC EC None of the above

	Which of the graphs has an Euler circuit?   Graph 2 only Graphs 1 and 3 Graph 3 only Graph 1 only None of the above

	Which of the graphs has an Euler path but no Euler circuit?   Graph 2 only Graph 1 only Graph 3 only Graphs 1 and 2 None of the above

	Questions 9 to 11 refer to the following situation: An undercover police officer is assigned the job of walking once a night each of the 48 blocks of a certain section of town described by the street grid shown below. The walk starts and ends at A. The officer wants to minimize the total number of blocks he has to walk each night. How many vertices of odd degree are there in the graph representing this problem?   24 20 18 22 None of the above

	An optimal eulerization of the graph representing this problem can be obtained by adding   9 edges. 10 edges. 11 edges. 12 edges. None of the above

	Suppose that it takes the officer 5 minutes to walk a block. In an optimal trip, the officer will cover the entire neighborhood in   5 hours. 4 hours and 45 minutes. 5 hours and 10 minutes. 4 hours and 50 minutes. None of the above

	A graph has an Euler circuit if   it is connected and has an even number of vertices. every vertex has even degree. it is connected and has an even number of edges. it is connected and every vertex has even degree. None of the above

	A graph with 11 vertices has an Euler path but no Euler circuit. The graph must have   11 vertices of odd degree. 2 vertices of odd degree and 9 vertices of even degree. 11 vertices of even degree. 2 vertices of even degree and 9 vertices of odd degree None of the above

	A graph has six vertices—two vertices of degree 4, two vertices of degree 3, and two vertices of degree 2. The number of edges in the graph is   8 9 5 6 None of the above

	The basic rule in Fleury’s algorithm is   never travel across a bridge of the original graph. never travel across a bridge of the untraveled part of the graph. only travel across a bridge of the original graph if there is no other alternative. only travel across a bridge of the untraveled part of the graph if there is no other alternative. None of the above

Answer choices in this exercise appear in a different order each time the page is loaded.

Copyright © 1995-2008, Pearson Education, Inc., publishing as Pearson Prentice Hall Legal and Privacy Terms