Homework 4 - Solution Sketch
(1)
(a) Since the graph is strongly connected, average consensus is possible in this graph.
(c) The graph is not strongly connected, so average consensus is not possible.
(2)
(a) A doubley stochastic matrix with element Mij non-zero whenever
directed link (j,i) is present (with other elements being 0)
will suffice. Note that A bidirection link between 1 and 2 is
equivalent to a pair of directed links (1,2) and (2,1).
Also, for the current purpose, each node should be viewed as
having a link to itsef.
(b) For this case, use a row stochastic matrix with non-zero elements
in same positions as part (a), but in this case, the matrix should
not be column stochastic.
(3) Consider a complete graph consisting of 3 nodes. This graph does not
satisfy the necessary condition in the paper. However, under the weaker
model, consensus is achieved after just one iteration.
(4) No, it is not possible. If the 4-node graph is not complete, then
at least one node has only 2 incoming links from the other nodes.
Suppose that node 1 has only two incoming links, say, from nodes 2 and 3.
Then choose L = {1}, R = {3,4}, C = {} and F = {2}.
This partition does not satisfy the necessary condition,
since node 1 has only 1 link from R+C, and L+C contains only one node,
so each node in R has only 1 link from L+C.