Teoria ed Esercizi, Sistemi Ibridi

68 CHAPTER 3

The factorization lemma comes from Nguyen and Mesbahi [179]; how-

ever, similar points of view have been explored in the theory of random

walks; see the book by Woess [248]. For a detailed convergence analysis

of the agreement problem and repeated averaging, see also Olshevsky and

Tsitsiklis [187]. Graph products is the subject of the book by Imrich and

Klavar [121], where the Cartesian product of graphs and the corresponding

factorization results are discussed. For the extension of the protocol to the

case where the state of each agent is constrained to a convex set, see [173].

We also refer the reader to the notes and references for Chapter 4 for

pointers to various extensions of the agreement protocol, particularly, when

the underlying graph or digraph is allowed to be time-varying.

SUGGESTED READING

The suggested readings for this chapter are Ren and Beard [204] on the

agreement protocol, and Chapter 8 of Meyer [159], which provides a lucid

introduction to the theory of non-negative matrices and Markov chains.

EXERCISES Simulate the agreement protocol (3.2) for a graph on five

Exercise 3.1.

vertices. Compare the rate of convergence of the protocol as the number

of edges increases. Does the convergence of the protocol always improve

when the graph contains more edges? Provide an analysis to support your

observation. D

Consider the digraph and the following symmetric protocol

Exercise 3.2. 1 {L(D) }

T

+ L(D) x(t).

ẋ(t) = 2

Does this protocol correspond to the agreement protocol on a certain graph?

D

What are the conditions on the digraph such that the resulting symmetric

protocol converges to the agreement subspace?

D

The reverse of is a digraph where all directed edges of

Exercise 3.3.

D have been reversed. A disoriented digraph is the graph obtained by re-

placing the directed edges of the digraph with undirected ones. Prove or

disprove: 69

THE AGREEMENT PROTOCOL: PART I THE STATIC CASE

D

1. The digraph is strongly connected if and only if its reverse is strongly

connected.

2. A digraph contains a rooted out-branching if and only if its reverse

digraph contains one. D

3. If the disoriented graph of is connected, then either the digraph or

its reverse contain a rooted out-branching.

4. A digraph is balanced if and only if its reverse is balanced. ∈ n×m

] R

A = [a

The Kronecker product of two matrices

Exercise 3.4. ij

∈ ⊗ ×

p×q

B = [b ] R A B, np mq

and , denoted by is the matrix

ij ⎤

⎡ · · ·

B a B

a

11 1m ⎥

⎢ · · ·

B a B

a ⎥

⎢ 21 2n ⎥

⎢ · · ·

B a B

a ⎥

⎢ 31 3n .

⎥

⎢ .. .. .. ⎦

⎣ . . .

· · ·

B a B

a

n1 nm

Suppose that the state of each vertex in the agreement protocol (3.1) is a

s s > 0. x

R , for some positive integer For example, might be the

vector in i

i s = 1.

position of particle along a line, that is, How would the compact

≥

s 2?

form of the agreement protocol (3.2) be modified for the case when

Hint: use Kronecker products.

How would one modify the agreement protocol (3.1) so that

Exercise 3.5. x̄, x̄ = α1 + d

the agents converge to an equilibrium where for some given

∈

∈ n α R?

d R and i

The second-order dynamics of a unit particle in one di-

Exercise 3.6.

mension is

d p 0 1 p 0

(t) (t)

i i (t),

= + u

i

(t) 0 0 (t) 1

v v

dt i i

v

p and are, respectively, the position and the velocity of the parti-

where i i u is the force and/or control term

cle with respect to an inertial frame, and i

acting on the particle. Use a setup, inspired by the agreement protocol, to

(t)

u for each vertex such that: (1) the control input

propose a a control law i

i

for particle relies only on the relative position and velocity information

with respect to its neighbors; (2) the control input to each particle results in

an asymptotically cohesive behavior for the particle group, that is, the po-

sitions of the particles remain close to each other; and (3) the control input

to each particle results in having a particle group that evolves with the same

velocity. Simulate your proposed control law.

70 CHAPTER 3

n

How would one extend Exercise 3.6 to particles in three

Exercise 3.7.

dimensions? Consider the uniformly delayed agreement dynamics over

Exercise 3.8.

a weighted graph, specified as

− − − · · ·

ẋ (t) = w (x (t τ ) x (t τ )), i = 1, , n,

i ij j i

(i)

j∈N

τ > 0.

for some Show that this delayed protocol is stable if

π ,

τ< 2λ (G)

n

λ (G)

where is the largest eigenvalue of the corresponding weighted Lapla-

n

cian. Conclude that, for the delayed agreement protocol, there is a trade-

off between faster convergence rate and tolerance to uniform delays on the

information-exchange links.

M

A matrix is called essentially non-negative if there ex-

Exercise 3.9. µ M + µI

ists a sufficiently large such that is non-negative, that is, all its

tM

e for an essentially non-negative ma-

entries are non-negative. Show that

≥

M t 0.

trix is non-negative when n x i =

An averaging protocol for agents, with state ,

Exercise 3.10. i

1, 2, . . . , n, is the discrete-time update rule of the form

x(k + 1) = W x(k), k = 0, 1, 2, . . . , (3.23)

T

x(k) = [x (k), x (k), . . . , x (k)] W

where and is a stochastic matrix.

1 2 n

Derive the necessary and sufficient conditions on the spectrum of the matrix

W such that the process (3.23) steers all the agents to the average value of

their initial states. i

Consider vertex in the context of the agreement protocol

Exercise 3.11. i

(3.1). Suppose that vertex (the rebel) decides not to abide by the agreement

protocol, and instead fixes its state to a constant value. Show that all vertices

converge to the state of the rebel vertex when the graph is connected.

A geometric graph on the unit square is generated by placing

Exercise 3.12. ∈ −x ≤

, v ) E(G) x ρ,

n (v when

points on the unit square and having i j i j

x i ρ

where is the coordinate of vertex and is a given threshold distance for

i

the existence of a link between a pair of vertices. Compute the Laplacian

∈

ρ (0, 1).

for such graphs on hundred nodes and various values of What is

71

THE AGREEMENT PROTOCOL: PART I THE STATIC CASE

λ (G) ρ?

your estimate on how grows as a function of

2

Show that a balanced digraph is weakly connected if and

Exercise 3.13.

only if it is strongly connected. G

G and are connected, then their

Show that if graphs

Exercise 3.14. 1 2

Cartesian product is connected.

Prove Lemma 3.22.

Exercise 3.15. n

Consider a network of processors, where each processor

Exercise 3.16.

has been given an initial computational load to process. However, before the

actual processing occurs, the processors go through an initialization phase,

where they exchange certain fractions of their loads with their neighbors in

i load-

the network. Specifically, during this phase, processor adopts the

update protocol

− −

(k + 1) = p (k) w (p (k) p (k)), k = 0, 1, 2 . . . ,

p (3.24)

i i ij i j

(i)

j∈N w of its load imbalance with its neighbors to

that is, it sends a fraction ij

each of them. What is the necessary and sufficient condition on the weights

w in (3.24) such that this initialization phase converges to a balanced load

ij

for all processors when the network is (1) a path graph, (2) a cycle graph, or

(3) a star graph? A B,

Given two square matrices and show that

Exercise 3.17. ⊗

A⊕B A B

= e e ,

e

and use this to provide an alternate (shorter) proof for Lemma 3.26.

Let the disagreement vector be

Exercise 3.18. #

" 1

− T x(t).

11

δ(t) = I n

M δ̇(t) = M δ(t),

Find the matrix such that under the assumption that

−L(G)x(t) G.

ẋ(t) = for some graph xv

Notation

Graph Theory

G: undirected graph; also referred to as graph

D: directed graph; also referred to as digraph

D: graph obtained after removing the orientation of the directed edges

D;

of also referred to as disoriented digraph

G: G

complement of undirected graph

G

G o : oriented version of graph

V V (G) V (D)

: vertex set; when necessary, also denoted by or

∂S: S

boundary of vertex set (with respect to an underlying graph)

S: S

closure of vertex set (with respect to an underlying graph)

cl , i = 1, . . . , n: i; ith

v vertex also used for denoting the entry of

i v

vector

E: E(G) E(D)

edge set; when necessary, also denoted by or

{v }:

e = , v v v ij

edge in a graph; also denoted by or

ij i j i j

}

∼ {v , v

i j: is present in the graph

edge i j

j): v v

the length of the shortest path between vertices and

dist(i, i j

e = (v , v ): edge in a digraph

ij i j

G\e: G e

graph with edge removed

G G

+ e: e

graph with edge added

N (i): i

set of agents adjacent to

N (i, t): i t

set of agents adjacent to at time

xvi d(v): v

degree of vertex

(v): v

d in-degree of vertex

in G

d (G): minimum vertex degree in

min G

d (G): maximum vertex degree in

max

¯ D

d (D): maximum (weighted) in-degree in

in G

diam(G): diameter of G

A(G): adjacency matrix of D

A(D): in-degree adjacency matrix of

G

∆(G): degree matrix of D

∆(D): in-degree matrix of

G

L(G): graph Laplacian of G

(G):

L edge Laplacian of

e D

L(D): in-degree Laplacian of D

L (D): out-degree Laplacian of

o G

L(G): line graph of D

D(D): incidence matrix of

n

C : cycle graph on vertices

n

P n

: path graph on vertices

n

K n

: complete graph on vertices

n n

S : star graph on vertices

n

G(n, p): n p

set of random graphs on vertices, with edge probability

G(n, r): n

set of random geometric graphs on vertices, with edge

r

threshold distance

G G G

G : Cartesian product of two graphs and

1 2 1 2 xvii

Linear Algebra

n

R n

: Euclidean space of dimension

n n

R R

: nonnegative orthant in

+ ×

m×n

R m n

: space of real matrices

×

S n n n

: space of symmetric matrices over reals

S ×

n n n

: space of (symmetric) positive semidefinite matrices

+ ×

I n n I

: identity matrix; also denoted as if the dimension is clear

n

from the context

×

m n 0

0 : zero matrix; also denoted as if the dimension is clear

m×n

from the context

−1 †

M , M M

: respectively, inverse and pseudo-inverse of

−T

T , M M

M : respectively, transpose and inverse transpose of

N (M ): M

null space of

R(M ): M

range space of

A ith jth

[A] : entry of matrix on row and column

ij

det(M ): M

determinant of (square) matrix

M M

: rank of

rank M M

: trace of

trace

M M

e : matrix exponential of square matrix

⊗ M M M

M : Kronecker product of two matrices and

1 2 1 2

L L ith jth

: matrix obtained from by removing its row and column

[i,j]

diag(M ): M

vector comprised of the diagonal elements of

Diag(v): v

diagonal matrix with the vector on its diagonal

· · · · · · T

), k = 1, 2, , n: Diag([v , , v ] )

Diag(v 1 n

k

M > 0 M

(M a symmetric matrix): is positive definite

≥

M 0 M

(M a symmetric matrix): is positive semidefinite

xviii (M ): ith M M

λ eigenvalue of ; is symmetric and its eigenvalues are

i

ordered from least to greatest value

v ith v; i

: entry of the vector also used for denoting vertex in a graph

i

ρ(M ): M M

spectral radius of , that is, the maximum eigenvalue of

in magnitude x,

span of vector that is, the subspace generated by scalar

span{x}: x

multiples of

x, y: x y;

inner product between two vectors and real part of the

∗ y x y

x if and are complex-valued

inner product

vector of all ones

1: ×

n 1

: vector of all ones

1 n

⊥ : subspace orthogonal to span{1}

1 1/2

T

x 2-norm x; x = (x x)

: of vector unless indicated otherwise

Other distance function

dist:

√

−1

j:

|z|: z = α+jβ,

modulus of complex number that is, 2-norm of vector

T

[α, β]

\W

V V W

: elements in set that are not in set

α α

: product of s

i i

i

α α

: sum of s

i i

i

≈: approximately equal to

: much less than

∗ x

x : complex conjugate transpose for complex-valued vector

∈ p

x (t) R i t

: state of agent at time

i

A: agreement set, equal to span{1}

E{x}: x

expected value of random variable xix

var{x}: x

variance of random variable

x x

: estimate of random variable (vector)

{1,

[n] 2, . . . , n}

(n a positive integer): set

−

p: a = b p) a b p

mod (mod if is an integer multiple of

V V

2 (V a finite set): the power set of , that is, the set of its subsets

n m-element [n],

: number of ways to choose subsets of that is,

m −

n!/(m!(n m)!) A

card(A): cardinality of set

arg min f f

: argument of the function that minimizes it over its do-

main or constraint set

arg max f f

: argument of the function that maximizes it over its do-

main or constraint set

, . . . , x ]:

R[x set of polynomials over the reals with indeterminants

1 n

x , . . . , x

1 n

O(f O(f

(n)): g(n) = (n)) g(n)

if is bounded from above by some

f (n) n

constant multiple of for large enough

Ω(f (n)): g(n) = Ω(f (n)) g(n)

if is bounded from below by some

f (n) n

constant multiple of for large enough 39

GRAPH THEORY

EXERCISES Show that the number of edges in any graph is half the sum of

Exercise 2.1. L(G)

the degrees of its nodes. Conclude that the trace of is always an even

number and that the number of odd degree nodes in any graph has to be even.

The degree sequence for a graph is a listing of the degrees

Exercise 2.2. K has the degree sequence 2, 2, 2. Is there a graph with

of its nodes; thus 3

the degree sequence 3, 3, 3, 3, 5, 6, 6, 6, 6, 6, 6? How about with the degree

sequence 1, 1, 3, 3, 3, 3, 5, 6, 8, 9?

Alkanes are chemical compounds that consist of carbon (C)

Exercise 2.3.

and hydrogen (H) atoms, where each carbon atom has four bonds and each

hydrogen atom only one. The graph of the alkane is obtained by denoting

each atom by a vertex and drawing an edge between a pair of vertices if

there is a bond between the corresponding atoms. Show that an alkane with

H

n C , indicating that for

carbon atoms assumes the chemical formula 2n+2

n

n 2n + 2

any alkane with carbon atoms there are hydrogen atoms. Show

C H

that the graph of an alkane is a tree. Draw two realizations of .

4 10

k-regular k;

A graph is if the degree of every vertex is thus

Exercise 2.4. k k-regular

K is 2-regular. What is the relationship between in a graph and

3 ≤ −

k n 1?

the number of nodes in the graph other than

G n c

Let be a graph on vertices with connected compo-

Exercise 2.5. −

L(G) = n c.

nents. Show that rank n (n−1)(n−

Show that any graph on vertices with more than

Exercise 2.6.

2)/2 edges is connected. G,

G = (V, E), is a

The complement of graph denoted by

Exercise 2.7. ∈ ∈

(V, E), uv E uv E.

graph where if and only if Show that

− T

L(G) + L(G) = nI 11 .

≤ ≤

2 j n,

Conclude that for −

(G) = n λ (G).

λ j n+2−j

The list adjacency of a graph is an array, each row of which is

Exercise 2.8.

initiated by a vertex in the graph and lists all vertices adjacent to it. Given

the list adjacency of a graph, write an algorithm (in your favorite language)

that checks whether the graph is connected.

40 CHAPTER 2

Recall that Cheeger’s inequality states that

Exercise 2.9. 2

φ(G)

≥

≥ (G) ,

φ(G) λ

2 2d (G)

max

G

φ(G)

where is the isoperimetric number of that can be used as a robust-

G

ness measure of to edge deletions. Construct a maximally robust graph

−

n n 1

consisting of vertices and edges. Explain how would you do this

φ(G)

and, in particular, give the value of for this maximally robust graph.

G

The line graph of is a graph whose vertex set is the set

Exercise 2.10.

G,

of edges of and there is an edge between these vertices if the correspond-

G

ing edges in are incident on a common vertex. What is the relationship

between the automorphism groups of a graph and its complement and its

line graphs? −

n n 1

Show that any graph on vertices that has more than

Exercise 2.11.

edges contains a cycle.

Show that the graph and its complement cannot both be

Exercise 2.12.

disconnected. −

G, T = ∆(G) A(G).

D(G)D(G)

Show that for a graph

Exercise 2.13. T

D(G)D(G)

Conclude that the graph Laplacian is independent of the orien-

G T

D(G). D(G) D(G)

tation given to for constructing Is the edge Laplacian

G D(G)?