# 05 - Graphs

1. A graph is a ______________ representation of a set of objects where some pairs of objects are connected by links.
`Note: You may find it useful to go through this power point from www.teachingcomputing.com`

pictorial

text based

python based

binary

2. A graph is often referred to as an abstract data type or structure and there are two types: ____________________

edged and non-edged

dense and thin

undirected and directed

coarse and smooth

3. The image below shows a ____________ graph with three vertices (blue circles) and three edges (black arrows).

edged

triangular

undirected

directed

4. The interconnected objects are represented by points known as __________, and the links that connect the_____________ are called edges.

connectors

dots

vertices

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

FALSE

TRUE

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 = _________________________?```

{aa, bb, cc, dd, ee}

{ab, bc, bc, ab, de}

{ab, ac, bd, cd, de}

7. A graph data structure may also associate to each edge some edge value, such as a symbolic label or a ______________________-

paragraph of information that describes each edge

numeric attribute such as cost, length or capacity

colour, that uniquely identifies the properties of the edge.

text-based attribute held as a single string

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;
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.```

removes the edge from the vertex x to the vertex y, if it is there

removes all edges

removes the edge y, even if it is not there

removes the edge from the vertex y to the vertex x, if it is there

9. A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. This is called an __________________

mellow matrix

erroneous matrix

edged matrix

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())```

Error - it is not possible to get the Vertices of this graph

['dan', 'bob', 'elma', 'carla', 'andrew']

['bob', dan', 'carla', 'andrew', 'elma']

['carla', dan', 'bob', 'andrew', 'elma']

11. In a graph, when you have more edges than vertices, the graph is called SPARSE

FALSE

TRUE

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?

2

7

4

3

13. For the image below, which of the following statements is correct?

There are five vertices and therefor a 5 x 1 matrix would need to be set up

There are six vertices so a 6 x 1 array could be used

There are six edges and just three vertices so a 6 x 3 matrix would be needed

There are six vertices so a 6 x 6 matrix would need to be set up

14. In the image below, can you fill in the blanks (for the red box and question mark)?

9

7

8

3

15. There are two main methods for traversing a graph. _________________ traversal typically uses a stack to store the visited nodes.

node first

depth first

first node last

16. _________________ traversal uses a queueto store the visited nodes. Visit all the nodes attached directly to a starting node first.

depth first

node first

first node last

17. Which of the following options best describes this graph?

weighted, undirected, graph

unweighted, directed graph

unweighted, undirected graph

weighted, directed, graph

18. What letter will fill in the blanks for this graph and adjacency matrix?

D

A

B

C

19. Graph traversal is different from tree traversal, because:

graph traversal involves loops

graphs have nodes with values so require recursive traversal

trees are not connected and have isolated nodes

trees have a root node

20. For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is

ne

2e

2n

2en