Concept

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. Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. In one restricted but very common sense of the term, a graph is an ordered pair comprising: a set of vertices (also called nodes or points); a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with two distinct vertices). To avoid ambiguity, this type of object may be called precisely an undirected simple graph. In the edge , the vertices and are called the endpoints of the edge. The edge is said to join and and to be incident on and on . A vertex may exist in a graph and not belong to an edge. Multiple edges, not allowed under the definition above, are two or more edges that join the same two vertices. In one more general sense of the term allowing multiple edges, a graph is an ordered triple comprising: a set of vertices (also called nodes or points); a set of edges (also called links or lines); an incidence function mapping every edge to an unordered pair of vertices (that is, an edge is associated with two distinct vertices). To avoid ambiguity, this type of object may be called precisely an undirected multigraph. A loop is an edge that joins a vertex to itself. Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex to itself is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph) which is not in . So to allow loops the definitions must be expanded.

Official source

https://en.wikipedia.org/wiki/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.

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related courses (32)

PHYS-467: Machine learning for physicists

Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practised. ...

MATH-101(g): Analysis I

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable. ...

COM-406: Foundations of Data Science

We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas and techniques that come from probability, information the ...

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.

Official source

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

About this result

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related courses (32)

PHYS-467: Machine learning for physicists

MATH-101(g): Analysis I

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable. ...

COM-406: Foundations of Data Science

Related lectures (32)

Fixed Points in Graph Theory

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

Belief Propagation

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

Networks, Flows MOOC: Optimization: principles and algorithms - Network and discrete optimization

Covers the definition of flow in a network and flow calculation.

Related publications (32)

Spectral Clustering with Side Information

In the graph clustering problem with a planted solution, the input is a graph on 𝑛 vertices partitioned into 𝑘 clusters, and the task is to infer the clusters from graph structure. A standard assumption is that clusters induce well-connected subgraphs (i.e. Ω⁡(1)-expanders), and connections between clusters are sparse (i.e. clusters form 𝜖-sparse cuts). Such a graph defines the clustering uniquely up to ≈𝜖 misclassification rate, and efficient algorithms for achieving this rate are known. While this vanill

Society for Industrial and Applied Mathematics2026

Promotion of cooperation in deme-structured populations with growth-merging dynamics

The spatial structure of populations may promote the emergence and maintenance of cooperation. Cooperation in the prisoner's dilemma is favored under specific update rules in evolutionary graph theory models with one individual per node of a graph, but this effect vanishes in models with well-mixed demes connected by migrations under soft selection. In contrast, experiments and models involving cycles of growth, merging and dilution have shown that spatial structure can favor cooperation. Here, we reconcile

bioRxiv2026

A Unified Framework for Modelling Modern Relational Network Data

This thesis concerns the nonparametric estimation of decorated graphons, symmetric measurable functions

W : [0,1]^2 \to \mathcal{P}(\mathcal{K})

that generalize classical graphon models beyond binary edges to networks carrying rich edge attributes such as weights and types. While decorated graphons were introduced as limit objects in graph theory, no estimation theory was available prior to this work. The thesis addresses this gap along three axes: rich edge attributes, temporal dynamics, and computationa

EPFL2026

Related people (32)

Vittorio Erba

Teaching & PhD Courses Statistical physics of computation PHYS-512 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.

Oliver Janzer

Teaching & PhD PhD Students Rik Sarkar Courses Algebraic methods in combinatorics MATH-526 In this course we study how algebraic methods can be used to solve problems in combinatorics. The main tools used are from linear algebra and from the theory of polynomials. Graph theory MATH-360 The course aims to introduce the basic concepts and results of modern Graph Theory. Awards European Prize in Combinatorics 2025 British Combinatorial Committee PhD Prize 2022 Smith-Knight

Pascal Frossard

Teaching & PhD PhD Students Yiming Qin, Alba Carballo Castro, Elisa Messori, Ke Wang, Sevda Ögüt, Tuna Alikasifoglu, William Cappelletti, Manuel Madeira, Mahdi Amiri, Ortal Yona Senouf, Vasiliki Rizou, Cem Bilaloglu, Abdellah Rahmani, Amel Abdelraheem, Jérémy Jean Philippe Baffou, Adam Hazimeh, Vincent Jung, Yike Zhao Past EPFL PhD Students Dan Jurca, Jean-Paul Wagner, Ivana Radulovic, Ivana Tosic, Effrosyni Kokiopoulou, Zafer Arican, Vijayaraghavan Thirumalai, Tamara Tosic, Eirina Bourtsoulatze, Elif Vur

Roger Hersch

Roger D. Hersch is professor of Computer Science and head of the Peripheral Systems Laboratory at EPFL. He received his engineering degree from ETHZ in 1975, worked in industry from 1975 to 1980, and obtained his PhD degree from EPFL in 1985. He directed the widely known Visible Human Web Server project , which offers a number of services for the visualization of human anatomy. His current research focuses on color reproduction, spectral color prediction models, moiré imaging, and visual document security. Recent achievements include the PhotoProtect technology, which incorporates text as chromatic differences in order to protect identity photographs (Swiss driving license), microstructure imaging, which is used by railways companies (SNCF, RENFE) and festival organizers (Paleo) to print tickets at home and the band moire imaging technology for the protection of security documents.

Kirell Maël Benzi

Vassily Hatzimanikatis

Dr. Vassily Hatzimanikatis is currently Associate Professor of Chemical Engineering and Bioengineering at Ecole Polytechnique Federale de Lausanne (EPFL), in Lausanne, Switzerland. Vassily received a PhD and an MS in Chemical Engineering from the California Institute of Technology, and his Diploma in Chemical Engineering from the University of Patras, in Greece. After the completion of his doctoral studies, he held a research group leader position at the Swiss Federal Institute of Technology in Zurich (ETHZ), Switzerland. Prior to joining EPFL, Vassily worked for three years in DuPont, Cargill, and Cargill Dow, and he has been assistant professor at Northwestern University, at Illinois, USA. Vassilys research interests are in the areas of computational systems biology, biotechnology, and complexity. He is associate editor of the journals Biotechnology & Bioengineering, Metabolic Engineering and Integrative Biology, and he serves on the editorial advisory board of the journals Bioprocess and Biosystems Engineering, Journal of Chemical Technology and Biotechnology, and Industrial Biotechnology. He has written over 70 technical publications and he is co-inventor in three patents and patent applications. Vassily is a fellow of the American Institute for Medical and Biological Engineering (2010), he was a DuPont Young Professor (2001-2004), and he has also received the Jay Bailey Young Investigator Award in Metabolic Engineering (2000), and the ACS Elmar Gaden Award (2011).

Xavier Eric Ouvrard

Professionals experiences IT System Specialist IT System Specialist in charge of the Experiment Facility of EcoCloud 2022–2022 EPFLHPC cluster system specialist Working as System specialist for the Radio Protection department: managing HPC cluster for FLUKA simulations for radio-protection.Full-Stack developer for the Radio-Analytical Laboratory of CERN: developed a web application to characterize low radioactive waster 2020–2022 CERNResearch assistant Working in doctoral position at CERN on Collaboration

Pierre Vandergheynst

Pierre Vandergheynst received the M.S. degree in physics and the Ph.D. degree in mathematical physics from the Université catholique de Louvain, Louvain-la-Neuve, Belgium, in 1995 and 1998, respectively. From 1998 to 2001, he was a Postdoctoral Researcher with the Signal Processing Laboratory, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland. He was Assistant Professor at EPFL (2002-2007), where he is now a Full Professor of Electrical Engineering and, by courtesy, of Computer and Communication Sciences. As of 2015, Prof. Vandergheynst serves as EPFL’s Vice-Provost for Education. His research focuses on harmonic analysis, sparse approximations and mathematical data processing in general with applications covering signal, image and high dimensional data processing, computer vision, machine learning, data science and graph-based data processing. He was co-Editor-in-Chief of Signal Processing (2002-2006), Associate Editor of the IEEE Transactions on Signal Processing (2007-2011), the flagship journal of the signal processing community and currently serves as Associate Editor of Computer Vision and Image Understanding and SIAM Imaging Sciences. He has been on the Technical Committee of various conferences, serves on the steering committee of the SPARS workshop and was co-General Chairman of the EUSIPCO 2008 conference. Pierre Vandergheynst is the author or co-author of more than 70 journal papers, one monograph and several book chapters. He has received two IEEE best paper awards. Professor Vandergheynst is a laureate of the Apple 2007 ARTS award and of the 2009-2010 De Boelpaepe prize of the Royal Academy of Sciences of Belgium.

Sacha Varone

Volkan Cevher

Volkan Cevher received the B.Sc. (valedictorian) in electrical engineering from Bilkent University in Ankara, Turkey, in 1999 and the Ph.D. in electrical and computer engineering from the Georgia Institute of Technology in Atlanta, GA in 2005. He was a Research Scientist with the University of Maryland, College Park from 2006-2007 and also with Rice University in Houston, TX, from 2008-2009. Currently, he is an Associate Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the Electrical and Computer Engineering Department at Rice University. His research interests include machine learning, signal processing theory, optimization theory and methods, and information theory. Dr. Cevher is an ELLIS fellow and was the recipient of the Google Faculty Research award in 2018, the IEEE Signal Processing Society Best Paper Award in 2016, a Best Paper Award at CAMSAP in 2015, a Best Paper Award at SPARS in 2009, and an ERC CG in 2016 as well as an ERC StG in 2011.

Related units (32)

Signal Processing Laboratory 4

SNAI - Administration

Transportation and Mobility Laboratory

Related concepts (20)

Four color theorem

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand.

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.

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.

Related exercises (2)

Graphs

The position as a function of time of a car in linear motion is given by

\begin{cases} \displaystyle{\frac{1}{2}a_0t^2} \qquad\quad\ \,\, \text{if} \quad t\leq \displaystyle{\frac{v_0}{a_0}} \\ v_0t - \displaystyle{\frac{v_0^2}{2a_0}} \qquad \text{if} \quad t> \displaystyle{\frac{v_0}{a_0}} \end{cases}$$ where v₀ and a₀ are positive constants. The position of the car is illustrated on the graph below: 1. Draw the graphs of velocity v(t) and acceleration a(t) as a function of time. 1. The po

Current induced by another current loop

The current through the coil on the right in Fig.xa0fig:fig7 varies as shown in Fig.xa0fig:fig7a. Which graph in Fig.xa0fig:fig7b best shows the ammeter reading as a function of time? The field created by the first loop:

first, it constantly grows with time ⟹ should induce a constant current in the second loop;
then it’s constant ⟹ no current in the second loop;
finally, it constantly drops with time ⟹ should induce a constant current in the opposite directi

Related notebooks (7)

Density of States in 1D Systems

This notebook shows density of states in 1D. Note that all graphs are cut off at Fermi Energy Ef, hence if the cut is visible on the graph consider increasing number of electrons in the system."

Temperature Dependence of the Fermi-Dirac Distribution

This notebook serves to show how the Fermi-Dirac distribution and its derivative change with temperature.\n", " \n", "The Fermi-dirac distribution is

f(E)=\\frac{1}{e^{(E-\\mu)/k_bT}+1}

\n", "\n", "For the purpose of simplicity, we will plot the graph of

f(E-\\mu)

. This allows us to avoid complications connected with

\\mu

being a function of temperature (consult the other notebook for this week or section 2.2.3 in the notes for more details)\n", "\n", "We first define the r

Interactive Phonon Band Structure Visualization

In [1]: import numpy as np import matplotlib.pyplot as plt from matplotlib import animation from matplotlib import rc import ipywidgets as ipw from ipywidgets import interact,interactive import ipywidgets as widgets from IPython.display import HTML %matplotlib widget global global_K1 global global_K2 global global_branche global global_selected_k In [2]: def get_closest_point(clic_x,clic_y): # Get the data from the figure ax= plt.gca() # get axis handle acoustic_data = ax.lines[1] op

Powder X-Ray Diffraction Analysis: Exploring Crystal Structures.

XRay Diffraction[1]¶ The purpose of this notebook is to study the powder XRay diffraction spectra of some systems. When the crystal is hit with an XRay wave, the wave is diffracted only for specific case where the Bragg condition is satisfied for one of the lattice planes in the material. For single crystal diffraction, the condition is satisfied only for specific orientation of the crystal, such that the incident ray has the correct

\theta

value for the plane. In powder XRay data, however, any plane ori

Ewald Sphere

::: {role="main"} ::: {.jp-Cell .jp-MarkdownCell .jp-Notebook-cell} ::: {.jp-Cell-inputWrapper tabindex="0"} ::: {.jp-Collapser .jp-InputCollapser .jp-Cell-inputCollapser} ::: ::: {.jp-InputArea .jp-Cell-inputArea} ::: {.jp-InputPrompt .jp-InputArea-prompt} ::: ::: {.jp-RenderedHTMLCommon .jp-RenderedMarkdown .jp-MarkdownOutput mime-type="text/markdown"}

Ewald Sphere¶{.anchor-link} {#Ewald-Sphere}

Play with the Ewald Sphere This schematics represent the Ewald sphere for a typical high