1. (a) Consider the directed graph shown below, in which the vertices have been numbered according to a certain labelling A. i. [5] Give its adjacency matrix M and use it to calculate the number of purtles of length four which start and end at vortex-2. ii. [15] Let a be a labelling of the same graph such that (1) = (2), (2) = p(3), and (3) = x(1). Give a representation of the graph with labelling , and give the adjacency matrix M". Find the similarity transformation which relates M" and M and show how Mis obtained from M (b) (10) Let M be the adjacency matrix of a directed graph. If AP is the identity matrix, what can be deduced about the graph? If the graph were connected, how many vertices would it have? 2. Let G be the weighted graph shown below. (a) (5) Give its transition matrix W and find its stationary states (b) (15) Find the Jordans form of W and decide if its integer powers converge as the power increases without bound. (c) (10) Use your result to decide whether all states defined on G con- verge to a stationary state as they evolve forwards in time. If yes, give the state to which any initial state will converge. 12 12