Preview

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 ________.

  computerised / edges / nodes / vertices

  simplistic / nodes / edges / vertices

  pictorial / links / vertices / edges

  pictorial / edges / vertices / edges

 2. In the example below a vertex represents a ________and an edge represents a f___________
uploads/facebook_graph.png

  edge / friendship

  friendship / edge

  node / linked node

  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?
uploads/directed_graph.png

  an UNDIRECTED WEIGHTED graph

  a DIRECTED UNWEIGHTED graph

  a UNDIRECTED UNWEIGHTED graph

  a DIRECTED WEIGHTED graph

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

  Directed, Weighted

  Undirected, Weighted

  Directed, Unweighted

  Undirected, 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 = SPARSE GRAPH; Less edges = DENSE GRAPH

  More edges = VERTEXED GRAPH; Less edges = EDGED GRAPH

  More edges = WEIGHTED GRAPH; Less edges = UNWEIGHTED GRAPH

  More edges = DENSE GRAPH; Less edges = SPARSE 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:
uploads/edges_v.png

  EDGES { (A, B, 7), (A,C,10), (B,E,3) etc…

  EDGES { (A, B, 10), (A,C,7), (B,E,3) etc…

  EDGES { (A, 10, B), (A,3,7), (B,3,E) 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?
uploads/adjacency_matrix.png

  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

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

 9. What numbers should go where the "?" marks are in the matrix below?
uploads/q_matrix_graph.png

  8 and 8

  0 and 0

  3 and 3

  9 and 9

 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.

  stack / queue

  linked list / stack

  queue / stack

  binary tree / stack