Thursday, May 31, 2018

[Multi Agent Systems] Introduction to Graph Theory

  No comments
Definition
A Graph is an (un)ordered pair comprised of a set of vertices (or nodes), and a set of edges (or links).

Example 1
An undirected graph

Example 2
Using graphs to model social interactions
Example 3
A directed graph (digraph)






Edges are ordered pairs with a head (initial) and a tail (terminal)
Edges are said to have an orientation


Path
A (simple) Path is a sequence of distinct vertices such that consecutive vertices are adjacent.
• Path length is number of edges traversed 
• There can be multiple paths between 2 nodes 
• Shortest Path

Connection
Undirected Graphs
Connected: for every pair of vertices, there exists a path connecting them.

Directed Graphs 
Strongly connected: for every pair of vertices, there exists a directed path connecting them. 
Weakly connected: if the graph obtained by replacing each directed edge with an undirected edge is connected

Degree
Undirected Graphs 
Node Degree: 
Directed Graphs
In-Node Degree: Number of edges entering a node Out-Node Degree: Number of edges leaving a node 

Induced Subgraphs

Trees and Cycles


Special Graphs
Example 4
All square matrices have a graph representation



Example 5

Structured Linear System


A structured linear system is a description of a dynamic system that considers only the interaction and influence between system states, control, and outputs independent of any realization of parameter values.

Algebraic Graph

The Combinatorial Laplacian Matrix

References:
IST - Analysis and Control of Multi-Agent Systems - SS2011

No comments :

Post a Comment