When an adjacency matrix representation is used, most graph algorithms require time O(n

2

)

(where n is the number of vertices), but there are some exceptions. Heres one.

Students in ECE 345 are trying to elect a class president. Each candidate has a few prefer-

ences (people who the person would be willing to accept as president). Of course, the set of

preferences for a person includes him/her self all the time.

What we are looking for is a perfect president who is in the set of preferences of every person

and who does not prefer anyone but him/her self (wouldnt that make a good president?). In

fact, all we want to know is whether such a person exists or not. Otherwise, were willing

to live in anarchy. Define a directed graph with the set of candidates as the vertices and a

directed edge from vertex a to vertex b if and only if b is in the set of preferences of a.

Suppose that the number of people (also the number of candidates) is n. Give an algorithm

which executes in O(n) time and determines if such a perfect presidential candidate exists or

not. Assume that you are given the graph described above in the form of an n n adjacency

matrix.

3. [Graph Algorithms, 20 points] When an adjacency matrix representation is used, most graph algorithms require ime O(n2) where n is the number of vertices), but there are some exceptions. Here's one Students in ECE 345 are trying to elect a class presiden. Each candidate has a few prefer- ences (people who the person would be willing to accept as presidn) Of course, the set of preferences for a person includes him/her self all the time What we are looking for is a "perfect" president who is in the set of preferences of every person and who does not prefer anyone but him/her self (wouldn't that make a good president?). In fact, all we want to know is whether such a person exists or not Otherwise, we're willing to live in anarchy. Define a directed graph with the set of candidates as the vertices and a directed edge from vertex a to vertex b if and only if b is in the set of preferences of a. Suppose that the number of people (also the number of candidates) is n. Give an algorithm which executes in O(n) time and determines if such a perfect presidential candidate exists or not. Assume that you are given the graph described above in the form of an nx n adjacency matrix