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

  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___________
uploads/facebook_graph.png

  friendship / edge

  edge / friendship

  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

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

  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:
uploads/edges_v.png

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

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

  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

  linked list / stack