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

Concept

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.

Official source

https://en.wikipedia.org/wiki/Glossary_of_graph_theory

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (18)

PHYS-512: Statistical physics of computation

The students understand tools from the statistical physics of disordered systems, and apply them to study computational and statistical problems in graph theory, discrete optimisation, inference and machine learning. ...

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

PHYS-642: Statistical physics for optimization & learning

This course covers the statistical physics approach to computer science problems, with an emphasis on heuristic & rigorous mathematical technics, ranging from graph theory and constraint satisfaction to inference to machine learning, neural networks and st ...

Related lectures (32)

Belief Propagation

Explores Belief Propagation in graphical models, factor graphs, spin glass examples, Boltzmann distributions, and graph coloring properties.

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Related publications (27)

Towards an Understanding of Hydraulic Sensitivity: Graph Theory Contributions to Water Distribution Analysis

Jérôme Chenal

Water distribution systems (WDSs) are complex networks with numerous interconnected junctions and pipes. The robustness and reliability of these systems are critically dependent on their network structure, necessitating detailed analysis for proactive leak ...

MDPI2024

Molecular hypergraph neural networks

Philippe Schwaller, Junwu Chen

Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...

Aip Publishing2024

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Assoc Computing Machinery2023

Related units (2)

Chair of Discrete Optimization

Distributed Intelligent Systems and Algorithms Laboratory

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.

Official source

https://en.wikipedia.org/wiki/Glossary_of_graph_theory

About this result

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related courses (18)

PHYS-512: Statistical physics of computation

ME-427: Networked control systems

PHYS-642: Statistical physics for optimization & learning

Related lectures (32)

Belief Propagation

Explores Belief Propagation in graphical models, factor graphs, spin glass examples, Boltzmann distributions, and graph coloring properties.

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Related publications (27)

Towards an Understanding of Hydraulic Sensitivity: Graph Theory Contributions to Water Distribution Analysis

Jérôme Chenal

MDPI2024

Molecular hypergraph neural networks

Philippe Schwaller, Junwu Chen

Aip Publishing2024

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

Assoc Computing Machinery2023

Related units (2)

Chair of Discrete Optimization

Distributed Intelligent Systems and Algorithms Laboratory

Related concepts (32)

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.

Cycle (graph theory)

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree. A circuit is a non-empty trail in which the first and last vertices are equal (closed trail).

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by .