PhD Seminar Course on

Graph Theoretical Approaches in Distributed Multi-Agent Networks

Cagliari, Feb. 15 – Feb. 24, 2011

This activity was made possible by the "Visiting Professors 2010" program of the University of Cagliari, sponsored by the Autonomous Region of Sardinia


Zhiyun Lin     (
Zhejiang University, China


18 hours, Feb. 15 – Feb. 24, 2011


Lecture 1 (3 hours):    Tuesday,      10:00 --- 13:00,     February 15

Lecture 2 (3 hours):    Thursday,     10:00 --- 13:00,     February 17

Lecture 3 (3 hours):    Friday,         10:00 --- 13:00,     February 18

Lecture 4 (3 hours):    Monday,      10:00 --- 13:00,     February 21

Lecture 5 (3 hours):    Tuesday,      16:00 --- 19:00,     February 22

Lecture 6 (3 hours):    Thursday,     10:00 --- 13:00,     February 24


Mocci Classroom


If you are interested in taking this course, you must register by sending an email to Zhiyun Lin ( at earliest convenience.

Course Description:

The course is an advanced research seminar for graduate students who are interested in distributed algorithms, cooperative control, sensor and robotic networks. The course is mainly motivated by the emergence of large scale networks, characterized by the lack of a centralized coordinator and time-varying local interactions. The purpose is to provide an introduction into such systems with graph theoretical approaches. The topics to be covered include stochastic matrices and distributed consensus algorithms in discrete-time setting; graph Laplacian and distributed consensus algorithms in continuous-time setting; complex Laplacian and pattern formations; reachability in graph and controllability of leader-follower networks; graph rigidity and rigid formations.

There is no textbook for this course. Lecture notes and reading papers will be distributed in the class. The course is going to be instructed in English.

Lecture topics:  

Lecture 1: Introduction to multi-agent networks and graph theory (3 hours)

    • Motivation and a bit of history

    • Research problems in multi-agent networks

    • Digraphs

    • Connectivity notions and results

Lecture 2: Stochastic matrices and distributed consensus in discrete-time (3 hours)

    • Adjacency matrices and digraphs

    • Irreducible matrices and primitive matrices

    • Stochastic matrices and SIA matrices

    • Wolfowitz Theorem

    • Distributed consensus in discrete-time

Lecture 3: Graph Laplacian and distributed consensus in continuous-time (3 hours)

    • Metzler matrices and M-matrices

    • Generator matrices, Laplacian, and digraphs

    • Algebraic properties of generator matrices

    • Distributed consensus in continuous-time

Lecture 4: Complex Laplacian and pattern formations (3 hours)

    • Cycle graph and circular formations

    • Directed acyclic graphs and pattern formation

    • Rank conditions of complex Laplacian and pattern formations

Lecture 5: Reachability in graph and controllability in leader-follower networks (3 hours)

    • Structural controllability in leader-follower networks

    • Reachability in the presence of link failures

    • Controllability irrelevant to parameters and reachability in graphs

Lecture 6: Graph rigidity and rigid formations (3 hours)

    • Rigid-body transformations

    • Frameworks

    • Infinitesimal rigidity

    • Polygon formations


The course is worth 2 credits. Grades (pass/fail) will be based on 3 weekly homework assignments.


Alessandro Giua
Dep. of Electrical and Electronic Engineering
University of Cagliari, Italy