*A social network is a set of P persons and V friendship relations. Each friendship relation consists of a pair of two persons p1 and p2 and we say p1 and p2 are friends. If p1 is a friend of p2 then p2 is also of p1. For instance, {Alex, Jim, James, Jake , Finn} and {(Alex, Jim), (James, Jake), (Jim, James), (Alex, James), (Finn, Jake)} are a social network with 5 persons and 5 friendship relations.*

**2.1** Briefly describe how a social network can be modeled as graph.

**2.2** Draw the graph corresponding to the social network in the example.

**2.3** A group X of k persons are called a close friendship if all persons in X are friends with all other persons in X. Give an algorithm that given a social network and a set X of k persons determines if X is a close friendship or not. Analyze the running time of your algorithm in the relevant parameters of the problem.

**2.4** A friendship chain of length j is a sequence of persons p1, . . . , pj such that pi is friends with pi+1 for all i, 1 ≤ i < j. Given a person p and an integer t ≥ 0 then p’s t-friends are all persons that have a friendship chain to p of length at most t (we define 0-friends of p to be p self). Specify all 2-friends of Alex in the example.

**2.5** Give an algorithm that given a social network, a person p and an integer t ≥ 0, computes all t-friends of p. Analyze the running time of your algorithm in the relevant parameters of the problem.

Please login or Register to submit your answer