Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Networked Control Systems: Strongly Connected Components and Condensation Digraphs

In course

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportunities offered by communication will be analyzed. ...

Description

This lecture covers the concepts of strongly connected components (SCC) in digraphs, where a subgraph is considered an SCC if it is strongly connected and cannot be strictly included in a larger SC subgraph. The instructor explains the condensation digraph, which simplifies a digraph by collapsing each SCC into a node. The lecture also discusses the properties of condensation digraphs, consensus algorithms, and the evolution of states in digraphs. Examples and proofs are provided to illustrate the theoretical concepts.

Instructor

Giancarlo Ferrari Trecate

Official source

Related concepts (15)

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

Directed acyclic graph

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions.

Industrial control system

An industrial control system (ICS) is an electronic control system and associated instrumentation used for industrial process control. Control systems can range in size from a few modular panel-mounted controllers to large interconnected and interactive distributed control systems (DCSs) with many thousands of field connections. Control systems receive data from remote sensors measuring process variables (PVs), compare the collected data with desired setpoints (SPs), and derive command functions that are used to control a process through the final control elements (FCEs), such as control valves.

Control system

A control system manages, commands, directs, or regulates the behavior of other devices or systems using control loops. It can range from a single home heating controller using a thermostat controlling a domestic boiler to large industrial control systems which are used for controlling processes or machines. The control systems are designed via control engineering process. For continuously modulated control, a feedback controller is used to automatically control a process or operation.

Rooted graph

In mathematics, and, in particular, in graph theory, a rooted graph is a graph in which one vertex has been distinguished as the root. Both directed and undirected versions of rooted graphs have been studied, and there are also variant definitions that allow multiple roots. Rooted graphs may also be known (depending on their application) as pointed graphs or flow graphs. In some of the applications of these graphs, there is an additional requirement that the whole graph be reachable from the root vertex.

Related lectures (28)

DFS Continuation: Topological Sort

Covers topics like DFS output, edge classification, acyclic graphs, correctness, time analysis, SCCs, and the Topological Sort algorithm.

Networked Control Systems: Consensus Algorithms in Digraphs

Explores consensus algorithms in digraphs, focusing on scenarios where the digraph is not strongly connected.

Networked Control Systems: Convergence Rate and Digraphs

Explores convergence rate in networked control systems and consensus in digraphs, emphasizing the challenges of computing Pess(A) and weight assignment.

Connectivity in Graph Theory

Covers the fundamentals of connectivity in graph theory, including paths, cycles, and spanning trees.

Networked Control Systems: Coordination Among Agents