Preview

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).
directedgraphblue.png

  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

  linked lists

 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 = _________________________?
graph_andrew_bob_carla_dan_elma.png

  {aa, bb, cc, dd, ee}

  {ab, bc, bc, ab, de}

  {aa, ab, ac, ad, ae}

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

  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 __________________

  adjacency matrix

  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?
graphsadjacentmatrix1.png

  2

  7

  4

  3

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

  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)?
orderedpairs_graph_matrix_q1.png

  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

  breadth 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

  breadth first

  node first

  first node last

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

  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?
adjacentverticesforudgraph.png

  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