Lecture

Graph Theory: Connectivity and Properties

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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 properties of undirected and directed graphs, including basic definitions, neighbors of a node, subgraphs, connectivity, paths, cycles, trees, and digraphs. It explains the concepts of connectivity, completeness, sources, sinks, directed trees, weak/strong connectivity, global reachable nodes, and directed spanning trees. The instructor emphasizes the importance of graph theory in modeling control network topology and discusses open problems related to graph connectivity and achieving consensus.

Instructor

Giancarlo Ferrari Trecate

Expertise Automatic control, Dependable control, Neural-network Control, Machine learning, Microgrids, Hybrid systems Mission See the webpage of the DECODE (Dependable Control and Decision) group. Teaching & PhD PhD Students Laura Meroi, Julien Pallage, Nicolas Léo Pierre Kirsch, Simone Baratto, Daniele Martinelli, Riccardo Cescon, Jakob Nylöf, Sabri El Amrani Past EPFL PhD Students Pulkit Nahata, Mustafa Sahin Turan, Baiwei Guo, Jean-Sébastien Brouillon, Clara Galimberti, Andrea Martin, Muhammad Zakwan,

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

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.

Related lectures (64)

Networked Control Systems: Coordination Among Agents

Explores coordination among agents in networked control systems through graph theory and real-world examples.

Connectivity in Graph Theory

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

Graph Theory and Network Flows

Introduces graph theory, network flows, and flow conservation laws with practical examples and theorems.

Graph Algorithms: Modeling and Traversal

Covers graph algorithms, modeling relationships between objects, and traversal techniques like BFS and DFS.

Bellman-Ford Algorithm: Shortest Path Estimation

Explains the Bellman-Ford algorithm for finding the shortest path in a directed graph with edge weights.