# [Multi Agent Systems] Introduction to Graph Theory

**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

**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__

__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