1. A graph is a ______________ representation of a set of objects where some pairs of objects are connected by links.
2. A graph is often referred to as an abstract data type or structure and there are two types: ____________________
3. The image below shows a ____________ graph with three vertices (blue circles) and three edges (black arrows).
4. The interconnected objects are represented by points known as __________, and the links that connect the_____________ are called edges.
5. You could also think of a graph as a pair of sets (V,E) where V is the set of vertices and E is the set of edges
6. Analyse the graph in the image. See if you can fill in the blanks for E:
In the graph shown in the image:
V = {a, b, c, d, e}
E = _________________________?
7. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a ______________________-
8. The following excerpt describes the various operations. Can you fill in the blanks?
The basic operations provided by a graph data structure G usually include:[1]
adjacent(G, x, y): tests whether there is an edge from the vertex x to the vertex y;
neighbors(G, x): lists all vertices y such that there is an edge from the vertex x to the vertex y;
add_vertex(G, x): adds the vertex x, if it is not there;
remove_vertex(G, x): removes the vertex x, if it is there;
add_edge(G, x, y): adds the edge from the vertex x to the vertex y, if it is not there;
remove_edge(G, x, y): _____________________________________________________?
get_vertex_value(G, x): returns the value associated with the vertex x;
set_vertex_value(G, x, v): sets the value associated with the vertex x to v.
9. A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. This is called an __________________
10. The following OOP python representation of a graph uses a dictionary. What is the output?
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = []
self.gdict = gdict
# Get the keys of the dictionary
def getVertices(self):
return list(self.gdict.keys())
# Create the dictionary with graph elements
graph_elements = { "andrew" : ["bob","carla"],
"bob" : ["andrew", "dan"],
"carla" : ["andrew", "dan"],
"dan" : ["elma"],
"elma" : ["dan"]
}
g = graph(graph_elements)
print(g.getVertices())
11. In a graph, when you have more edges than vertices, the graph is called SPARSE
12. Analyse the image below and see if you can fill in the blanks for the question mark(s). What number would go in both boxes?
13. For the image below, which of the following statements is correct?
14. In the image below, can you fill in the blanks (for the red box and question mark)?
15. There are two main methods for traversing a graph. _________________ traversal typically uses a stack to store the visited nodes.
16. _________________ traversal uses a queueto store the visited nodes. Visit all the nodes attached directly to a starting node first.
17. Which of the following options best describes this graph?
18. What letter will fill in the blanks for this graph and adjacency matrix?
19. Graph traversal is different from tree traversal, because:
20. For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is
