Description
Question 1
A shortest path between two nodes is a path of the minimum possible length. We say that a node X is pivotal for a pair of distinct nodes Y and Z if X lies on every shortest path between Y and Z (and X is not equal to either Y or Z).
According to the above figure, which of the following statement(s) are correct?
- Node B is pivotal for node pair of D – E
- Node B is pivotal for node pairs of A – C and A – D
- There is no pivotal for node pair D – E
- Node D is not a pivotal for any pairs of distinct nodes
Question 2
Recall the definition of shortest path and pivotal stated in Question 1. Consider the following polygons where each vertex is a node. Which polygon satisfies that every node in this polygon is a pivotal of at least one node pair?
Question 3
Recall the definition of shortest path and pivotal stated in Question 1. Consider the following polygons where each vertex is a node. Which polygon satisfies that every node in this polygon is a pivotal of at least two node pairs?
The following definitions are useful for question 4 and 5.
A node X is called a gatekeeper if for some other two nodes Y and Z, every path from Y to Z passes through X. A node X is called a local gatekeeper if there are two neighbors of X, say Y and Z, that are not connected by an edge. (That is, for X to be a local gatekeeper, there should be two nodes Y and Z so that Y and Z each have edges to X, but not to each other.)
Question 4
Based on the definition of “Gatekeeper” and “Local Gatekeeper”, please consider the following statements and select the correct one(s) w.r.t the graph below.
- The number of local gatekeeper remains unchanged when an edge between node B and E is added
- Node D is gatekeeper
- Node A is local gatekeeper
- There are 2 local gatekeepers in the above graph
Question 5
Based on the definition of “Gatekeeper” and “Local Gatekeeper”, please consider the following statements and select the correct one(s) w.r.t the graph below.
- If the edge between node A and B is removed, node C will be gatekeeper.
- Over half of the number of nodes are local gatekeepers
- If the edge between node B and C is removed, all of the nodes will be local gatekeepers.
- If the edge between node C and D is removed, node B will be gatekeeper.