Suppose we have a community of n people. We can create a directed graph from this community as follows: the vertices are people, and there is a directed edge from person A to person B if A would forward a rumor to B. Assume that if there is an edge from A to B, then A will always forward any rumor they hear to B. Notice that this relationship isn’t symmetric: A might gossip to B but not vice versa. Suppose there are m directed edges total, so G = (V, E) is a graph with n vertices and m edges. Define a person P to be influential if for all other people A in the community, there is a directed path from P to A in G. Thus, if you tell a rumor to an influential person P , eventually the rumor will reach everybody. You have a rumor that you’d like to spread, but you don’t have time to tell more than one person, so you’d like to find an influential person to tell the rumor to. In the following questions, assume that G is the directed graph representing the community, and that you have access to G as an array of adjacency lists: for each vertex v, in O(1) time you can get a pointer to the head of the linked lists v.outgoing neighbors and v.incoming_neighbors. Notice that G is not necessarily acyclic. (a) Show that all influential people in G are in the same strongly connected component, and that everyone in this strongly connected component is influential. [Hint: You need to refer the definition of strongly connected component, and you can prove using either induction or contradiction.] (b) Suppose that an influential person exists. Give an algorithm that, given G, finds an influential person. [We are expecting a description or pseudocode of the algorithm and a short argument about the runtime.]
Suppose we have a community of n people. We can create a directed graph from this community as follows: the vertices are people, and there is a directed edge from person A to person B if A would forward a rumor to B. Assume that if there is an edge from A to B, then A will always forward any rumor they hear to B. Notice that this relationship isn’t symmetric: A might gossip to B but not vice versa. Suppose there are m directed edges total, so G = (V, E) is a graph with n vertices and m edges.
Define a person P to be influential if for all other people A in the community, there is a directed path from P to A in G. Thus, if you tell a rumor to an influential person P , eventually the rumor will reach everybody. You have a rumor that you’d like to spread, but you don’t have time to tell more than one person, so you’d like to find an influential person to tell the rumor to. In the following questions, assume that G is the directed graph representing the community, and that you have access to G as an array of adjacency lists: for each vertex v, in O(1) time you can get a pointer to the head of the linked lists v.outgoing neighbors and v.incoming_neighbors. Notice that G is not necessarily acyclic.
(a) Show that all influential people in G are in the same strongly connected component, and that everyone in this strongly connected component is influential. [Hint: You need to refer the definition of strongly connected component, and you can prove using either induction or contradiction.]
(b) Suppose that an influential person exists. Give an
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
