Teoria ed Esercizi, Sistemi Ibridi

Graph Notation

GG: oriented version of graph

V(G): vertex set; when necessary, also denoted by ∂

S: Sboundary of vertex set (with respect to an underlying graph)

S: Sclosure of vertex set (with respect to an underlying graph)

cl , i = 1, . . . , n: i; ithv vertex also used for denoting the entry ofi vvector

E: E(G) E(D)edge set; when necessary, also denoted by {v }

e = , v v v ijedge in a graph; also denoted by orij i j i j}

∼ {v , vi j: is present in the graphedge i jj): v vthe length of the shortest path between vertices and

dist(i, i je = (v , v ): edge in a digraphij i j

G\e: G egraph with edge removed

G G+ e: egraph with edge added

N (i): iset of agents adjacent to

N (i, t): i tset of agents adjacent to at time

xvi d(v): vdegree of vertex(v): vd in-degree of vertexin Gd (G): minimum vertex degree inmin Gd (G): maximum vertex degree inmax¯ Dd (D): maximum (weighted) in-degree inin Gdiam(G): diameter of GA(G): adjacency matrix of DA(D): in-degree adjacency matrix ofG∆(G):

degree matrix of D∆(D):

in-degree matrix of D

GL(G):

graph Laplacian of G

L:

edge Laplacian of G

DL(D):

in-degree Laplacian of D

DL (D):

out-degree Laplacian of D

GL(G):

line graph of G

DD(D):

incidence matrix of D

nC:

cycle graph on vertices n

nP:

path graph on vertices n

nK:

complete graph on vertices n

nS:

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 threshold distance

G:

Cartesian product of two graphs 1 and 2

xvii

Linear Algebra

nR:

Euclidean space of dimension n

nR:

nonnegative orthant in n-dimensional space

R m n:

space of real matrices m x n

S n n:

space of symmetric matrices over reals

S n n:

space of (symmetric) positive semidefinite matrices

+ ×I n n:

identity matrix; also denoted as I if the dimension is clear from the context

×m n 00:

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

−1 †M , M M:

respectively,

inverse and pseudo-inverse of -TT , M MM : 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
rank of rank M M
trace of traceM M
e : matrix exponential of square matrix
⊗ M M MM : Kronecker product of two matrices
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 nk
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
ρ(M ): M
spectral radius of , that is,

set−p: a = b p) a b pmod (mod if is an integer multiple ofV V2 (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)!) Acard(A): cardinality of setarg min f f: argument of the function that minimizes it over its do-main or constraint setarg 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 indeterminants1 nx , . . . , x1 nO(f O(f(n)): g(n) = (n)) g(n)if is bounded from above by somef (n) nconstant multiple of for large enoughΩ(f (n)): g(n) = Ω(f (n)) g(n)if is bounded from below by somef (n) nconstant multiple of for large enough 39GRAPH THEORYEXERCISES Show that the number of edges in any graph is half the sum ofExercise 2.1. L(G)the degrees of its nodes. Conclude that the trace of is always an evennumber and that the number of odd degree nodes in any graph has to be even.The degree

Exercise 2.2. K has the degree sequence 2, 2, 2. Is there a graph with 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) 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 n carbon atoms assumes the chemical formula C_2n+2H_2n+2, indicating that for any alkane with n carbon atoms there are 2n + 2 hydrogen atoms. Show that the graph of an alkane is a tree. Draw two realizations of C₄H₁₀.

Exercise 2.4. A graph is k-regular if the degree of every vertex is k. K is 2-regular. What is the relationship between k and n in a graph with 3 ≤ -k ≤ n - 1?

Exercise 2.5. Let G be a graph on n vertices with connected components. Show that rank(G) = n - c.

Exercise 2.6. Show that any graph on n vertices with more than (n-1)(n-2)/2 edges is connected.

Exercise 2.7. The complement of a graph G = (V, E), denoted by G', is a graph where uv is an edge if and only if uv is not an edge in G.

Exercise 2.8. The list adjacency of a graph is an array, each row of which is 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.

Recall that Cheeger's inequality states that 2φ(G) ≥ λ2(G), where φ(G) is the isoperimetric number of G that can be used as a robustness measure of G to edge deletions.

Construct a maximally robust graph G consisting of n vertices and n-1 edges. Explain how would you do this φ(G) and, in particular, give the value of φ for this maximally robust graph.

The line graph of G is a graph whose vertex set is the set of edges of G, and there is an edge between these vertices if the corresponding edges in G are incident on a common vertex. What is the relationship between the automorphism groups of a graph and its complement and its line graphs?

Show that any graph on n vertices that has more than n-1 edges contains a cycle.

Show that the graph G and its complement cannot both be disconnected.

Show that for a graph G, T = ∆(G) - A(G). D(G) = D(G)

Show that for a graph G, T = ∆(G) - A(G). D(G) = D(G)

Conclude that the graph Laplacian is independent of the orientation given to G for constructing TD(G). D(G) = D(G). Is the edge Laplacian independent of the orientation given to G?

Show that for any graph G, λ(G) ≥ d(G).

maxnG ∈= (V, E) uv ELet be a graph, and let for someExercise 2.15.∈u, v V . Show that ≤ ≤(G) λ (G + e) λ (G) + 2,λ2 2 2G ∪ {e}).+ e (V, Ewhere is the graphWhat are the eigenvalues and eigenvectors of the Lapla-Exercise 2.16. PK , the path graph , and the completecian matrix for the complete graph n nK ?bipartite graph n,nWhat is the automorphism group of the Peterson graph?Exercise 2.17. 41GRAPH THEORY πA nontrivial equitable partition of a graph is said to beExercise 2.18.maximal if any other nontrivial, equitable partition of the graph contains noπ.fewer cells than Find the maximal, nontrivial equitable partition for thegraph below. Prove Theorem 2.7.Exercise 2.19.Preface “I don’t want to achieve immortalitythrough my work ... I want to achieveit through not dying.” — Woody AllenThe emergence of (relatively) cheap sensing and actuation nodes, capable ofshort-range communications and local decision-making, has