COMP 3121 Homework 1

COMP 3121 Homework 1Question 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?
1. Node B is pivotal for node pair of D - E
2. Node B is pivotal for node pairs of A - C and A – D
3. There is no pivotal for node pair D – E
4. 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.
1. The number of local gatekeeper remains unchanged when an edge between node B and E is
added
2. Node D is gatekeeper
3. Node A is local gatekeeper
4. 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.
1. If the edge between node A and B is removed, node C will be gatekeeper.
2. Over half of the number of nodes are local gatekeepers
3. If the edge between node B and C is removed, all of the nodes will be local gatekeepers.
4. If the edge between node C and D is removed, node B will be gatekeeper.