T rue or F alse (1 through 20) 1point each: 1. _______________In a directed grap
ID: 3612488 • Letter: T
Question
True or False (1 through 20) 1point each:
1. _______________In a directed graph edge(v, w) != (w, v) .
2. _______________There is a shortest pathbetween two vertices if the path between
them uses a negative cycle.
3. _______________ The depth first searchwill visit every node in an undirected graph
only if the graph is not connected.
4. ______________ The depth-first searchis a traversal which visits a source vertex s,
then visits the vertices one edge away from s, then those twoedges away from s, and so on.
5. ______________ If a spanning tree ofa graph has n vertices, the graph must have
n-1 vertices.
6. ______________ The adjacency matrixfor a simple graph will never have 1’s along
the diagonal.
7. ______________ A shortest-path treeis the set of shortest paths from a source
vertex.
8. ______________ An edge in a directedgraph is represented by an ordered pair.
9. ______________ An adjacency matrixis a two-dimensional arrayimplementation for a graph.
10. ______________ In a undirected graph edge (v, w) = (w,v).
11. ______________ The breadth-first search can be used ona tree.
12. ______________ A spanning graph need not have all ofthe vertices of theoriginal graph.
13. ______________ A spanning tree is also a spanninggraph.
14. ______________ Prim's Algorithm will always maintainone tree at every stage of
development.
15. ______________ A biconnected graph is a connected graphwith an articulation
point.
16. ______________ Sollin's algorithm is an algorithm forbuilding a minimum
spanning tree.
17. ______________ A spanning tree with 10 vertices willhave exactly 5 edges.
18. ______________ An undirected complete graph with 10vertices will have 45 edges.
19. ______________ A spanning tree is a spanning graph withno cycles.
20. ______________ The depth-first search implementationuses a queue to keep up
with neighbors.
Explanation / Answer
hey i tried answering your questions. Few of them m not sureof.. here you go!!! T-TRUE F-FALSE 1. T 3. F 4. F 5. F 6. T 8. T 9. T 10. T 11. T 12. T 14. T 15. F A biconnected graph is a connected graph with noarticulation point. 16. T 18. T using formula for complete graph N(N-1) / 2 where N isnumber of vertices. 19. T 20. F it uses stackRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.