- 1. How many spanning trees does the following graph have?
A) Not here
B) 8
C) 5
D) 4
E) 3
- 2. Using Kruskal’s algorithm which edge should we choose first?
A) BD
B) AC
C) EB
D) BA
E) BC
- 3. Using Kruskal’s algorithm which edge should we choose second?
A) BA
B) BC
C) BD
D) EB
E) AC
- 4. Using Kruskal’s algorithm which edge should we choose third?
A) AC
B) EB
C) BC
D) BD
E) AB
- 5. Which of the following edges of the given graph are not part of the minimum spanning tree?
A) BD
B) EB
C) AC
D) AB
E) BC
- 6. The total weight of the minimum spanning tree is
A) 49
B) 39
C) 34
D) 37
E) 60
- 7. Which of the following statements is true about Kruskal’s algorithm?
A) It is an efficient algorithm and it always gives the minimum spanning tree.
B) It is an efficient algorithm and it always gives the minimum spanning tree.
C) It is an inefficient algorithm and it never gives the minimum spanning tree.
D) It is an efficient algorithm but it doesn’t always give the minimum spanning tree.
E) Not here
A) both
B) an Euler circuit
C) an Euler path
D) neither
- 9. Does the existence of an Euler path imply that an Euler circuit exists?
A) No
B) Yes
- 10. Does the existence of an Euler circuit imply that an Euler path exists?
A) No
B) Yes
- 11. Does the existence of a Hamilton circuit imply that a Hamilton path exists?
A) Yes
B) No
- 12. Does Graph H have a circuit
A) No
B) Yes
- 13. Give the circuit for Graph H
A) H :: b.a.c.d.e.f.g.h.i.j.k.m.n.p.o.l.a
B) H :: b.a.c.d.e.f.g.h.i.j.k.m.n.p.o.l.b
C) H :: c.b.a.d.e.f.g.h.i.j.k.m.n.p.o.l.c
D) H :: a.b.c.d.e.f.g.h.i.j.k.m.n.p.o.l.a
- 14. The degree of Vertex D is:
A) odd
B) Not here
C) 3
D) even
- 15. Which of the following is not a path from vertex D to vertex A?
A) D, E, C, D, A
B) D, C, A
C) D, E, D, C, C, A
D) D, C, C, A
- 16. Which of the following [A), B), C), or D)] is not a circuit in the graph?
A) All of the above are circuits in the graph.
B) A, D, C, D, E, D, A
C) C, A, D, C
D) E, D, C, C, E
E) A, D, E, C, A
- 17. Which of the graphs has an Euler circuit?
A) Graph 3 only
B) Graph 1 only
C) Graph 2 and 3
D) Graph 2 only
E) Graph 1 and 3
- 18. 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.
A) 22
B) 18
C) 24
D) 20
- 19. Suppose that it takes the officer 5 minutes to walk a block. In an optimal trip, the officer will cover the entire neighborhood in
A) 4 hours and 50 minutes
B) 5 hours and 10 minutes.
C) 4 hours and 45 minutes.
D) 5 hours
- 20. A graph has an Euler circuit if
A) every vertex has even degree.
B) it is connected and every vertex has even degree.
C) 2 vertices of odd degree and 9 vertices of even degree.
D) it is connected and has an even number of edges.
A) Euler trail
B) Both path and circuit
C) Euler Circuit
D) Euler Path
- 22. Which of the following graphs below have Euler Circuits?
A) Neither I or II
B) Both I and II
C) II
D) I
- 23. Which of the following statements is/are true? I. A tree is a connected graph that does not contain a circuit. II. An Euler circuit must visit each vertex once and only once. III. The minimum completion time for an order requirement digraph is the length of the shortest path.
A) I
B) I and III
C) I and II
D) III
- 24. Which of the following statements is/are true? I. The chromatic number of a graph is the minimum number of colors required to produce a vertex coloring of the graph. II. Eulerization of a graph is the process of finding an Euler circuit for that graph. III. Kruskal’s algorithm is used for finding a minimum cost spanning tree.
A) I,II, and III
B) III
C) II and III
D) I and II
- 25. For the graph show below, use the nearest neighbor algorithm to find a Hamiltonian circuit. Use B as the starting point.
A) BCEDAB
B) BCDAEB
C) BECADB
D) BEDBCA
|