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

  pictorial / links / vertices / edges

  pictorial / edges / vertices / edges

  simplistic / nodes / edges / vertices

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

  edge / friendship

  friendship / edge

  edge / vertex

  node / linked node

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

  a DIRECTED relationship (asymmetric)

  a VERTICAL relationship (each one inherits from the other)

  an UNDIRECTED relationship (symmetric)

  a EDGED relationship (edgy)

 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 DIRECTED UNWEIGHTED graph

  an UNDIRECTED WEIGHTED 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

  Undirected, Weighted

  Directed, 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 = WEIGHTED GRAPH; Less edges = UNWEIGHTED GRAPH

  More edges = VERTEXED GRAPH; Less edges = EDGED GRAPH

  More edges = SPARSE GRAPH; Less edges = DENSE 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 { (AB = 10), (C = 7), (B = 3) etc…

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

  EDGES { (A, 10, B), (A,3,7), (B,3,E) 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 2,0 should be in 0,0

  The one in 3,1 should be deleted

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

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

  3 and 3

  0 and 0

  9 and 9

  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.

  stack / queue

  linked list / stack

  binary tree / stack

  queue / stack


Report an error