NEW
Font size
WorksheetsGraphs
Total questions: 27
Worksheet time: 14mins
In the graph shown, D is an example of a(n) ________ .
Edge
Vertex
Path
Sling
In the graph shown, (A, F) is an example of a(n) ________ .
Edge
Vertex
Path
Sling
In the graph shown, A, B, E is an example of a(n) ________ .
Edge
Vertex
Path
Sling
Which of the following is a cycle shown in the graph?
B, F, A, B
A, B, E
A, E, D, A
A, C, B, D, A
Which of the following is not an edge in this graph?
(A, D)
(D, A)
(F, A)
(A, E)
Vertices are considered adjacent if ________ .
An edge connects them
There is a path from one vertex to the other
Both vertices are contained in a cycle
The length of the path between them is less than 5
A complete graph is a graph _________ .
where every vertex has a degree >= 1
that has the maximum number of edges connecting vertices
that for any two vertices, the graph has a path
that has at least one edge to every vertex
The formula for finding the number of edges in a complete graph is ________ where V is the number of vertices.
V (V+1) / 2
2 (V+1) / V
V (V-1) / 2
(V+2) / 2
The number of edges needed in a complete graph with 5 vertices is ________ .
10
15
5
25
What is the length of the path F, A, C, B, D?
3
4
5
6
A strongly connected graph is a graph _________ .
where every vertex has a degree >= 1
that has the maximum number of edges connecting vertices
that for any two vertices, the graph has a path
that has at least one edge to every vertex
T/F: the graph is strongly connected.
True
False
T/F: the graph is strongly connected.
True
False
A network is a graph with _______ .
No cycles
Weights associated with each edge
At least one cycle
The maximum number of possible edges
T/F: Networks can be directed or undirected
True
False
Which data structure is used to perform a traversal in breadth first search?
Stack
Queue
Linked List
Heap
Which data structure is used to perform a traversal in depth first search?
Stack
Queue
Linked List
Heap
T/F: A minimum spanning tree never has any cycles
True
False
When building a minimum spanning tree starting from vertex A, the first edge to be added would be _________ .
(A, C)
(A, B)
(A, F)
(C, D)
When building a minimum spanning tree starting from vertex A, the second edge to be added would be _________ .
(A, C)
(A, B)
(C, G)
(C, D)
T/F: You will always get the same minimum spanning tree no matter which vertex you start at.
True
False
T/F: The weight of a graph's minimum spanning tree will always be the same no matter which vertex you start at.
True
False
T/F: It is possible to get multiple shortest paths when running Dijkstra's shortest path algorithm.
True
False
After completing Dijkstras algorithm to find the shortest path from A to G, which vertex has the value "A, C" in its path column?
F
E
D
G
After completing Dijkstras algorithm to find the shortest path from A to G, which vertex has the value "5" in its cost column?
F
E
D
G
After completing Dijkstras algorithm to find the shortest path from A to G, we discover the cost of this path is ______ .
4
5
6
7
The weight of the minimum spanning tree for this graph is _____ .
12
15
17
18
