# 14 - Graphs

1. A graph is a ___________ representation of a set of objects where some pairs of objects are connected by _______. The interconnected objects are represented by points termed as __________, and the links that connect the vertices are called ________.

pictorial / links / vertices / edges

simplistic / nodes / edges / vertices

pictorial / edges / vertices / edges

computerised / edges / nodes / vertices

2. In the example below a vertex represents a ________and an edge represents a f___________

friendship / edge

edge / friendship

edge / vertex

3. In the question showing the facebook representation of a graph above, what type of relationship is modelled?

a EDGED relationship (edgy)

a VERTICAL relationship (each one inherits from the other)

an UNDIRECTED relationship (symmetric)

a DIRECTED relationship (asymmetric)

4. This example shows the relationship between certain webpages. The numbers represent the number of clicks from one site to the other. What type of graph does the following depict?

a UNDIRECTED UNWEIGHTED graph

an UNDIRECTED WEIGHTED graph

a DIRECTED WEIGHTED graph

a DIRECTED UNWEIGHTED graph

5. The following example shows the distance in miles from different places. What sort of graph is this?

Directed, Weighted

Undirected, Weighted

Undirected, Unweighted

Directed, Unweighted

6. In a graph, each node is called a VERTEX. The paths that connect them are called EDGES. Which of the following statements is correct?

More edges = VERTEXED GRAPH; Less edges = EDGED GRAPH

More edges = DENSE GRAPH; Less edges = SPARSE GRAPH

More edges = WEIGHTED GRAPH; Less edges = UNWEIGHTED GRAPH

More edges = SPARSE GRAPH; Less edges = DENSE GRAPH

7. Remember, a graph is a set of vertices and edges. Edges listed as a pair of vertices. They can be listed in the following way:

EDGES { (A, 10, B), (A,3,7), (B,3,E) etcÃ¢â‚¬Â¦

EDGES { (A, B, 7), (A,C,10), (B,E,3) etcÃ¢â‚¬Â¦

EDGES { (A, B, 10), (A,C,7), (B,E,3) etcÃ¢â‚¬Â¦

EDGES { (AB = 10), (C = 7), (B = 3) etcÃ¢â‚¬Â¦

8. One of the 'T's in the adjacency matrix shown is in the wrong place, and everything else has been entered correctly. Which one is incorrect?

The one in 0,0 should be in 0,1

The one in 4,5 should be in 4,3

The one in 3,1 should be deleted

The one in 2,0 should be in 0,0

9. What numbers should go where the "?" marks are in the matrix below?

9 and 9

0 and 0

3 and 3

8 and 8

10. It is possible to traverse graphs. Depth first traversal uses a ____ to store the visited nodes. Breadth first traversal uses a ______ to store the visited nodes.

binary tree / stack

queue / stack

stack / queue