Catégorie

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, télécommunications, etc.) et dans bien d'autres domaines (par exemple génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d'une fonction), est général. De grands théorèmes difficiles, comme le théorème des quatre couleurs, le théorème des graphes parfaits, ou encore le théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la conjecture de Hadwiger, en font une branche vivace des mathématiques discrètes. Lexique de la théorie des graphes vignette|Un graphe orienté avec trois sommets et quatre arcs. Un graphe est un couple comprenant deux ensembles : sommets ; arêtes, chacune étant associée à un couple ou une paire de sommets (u, v ∈ V). Il y a plusieurs principaux types de graphes : Dans un graphe non orienté, les arêtes n'ont pas d'orientation et sont donc associées à une paire . Dans un graphe orienté, les arêtes sont appelées arcs et ont une orientation de vers ; elles sont ainsi associées au couple . Un graphe mixte comporte à la fois des arêtes et des arcs, on le définit alors plutôt comme le triplet . Un graphe simple est un graphe ne comportant ni boucles ni multi-arêtes, c'est-à-dire qu'aucun sommet n'est connecté à lui-même, et entre deux sommets il n'existe qu'une seule arête.

Ontologie

Source officielle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Ontologie

Source officielle

Catégories associées (31)

Algèbre linéaire

vignette|R3 est un espace vectoriel de dimension 3. Droites et plans qui passent par l'origine sont des sous-espaces vectoriels. L’algèbre linéaire est la branche des mathématiques qui s'intéresse aux espaces vectoriels et aux transformations linéaires, formalisation générale des théories des systèmes d'équations linéaires. L'algèbre linéaire est initiée dans son principe par le mathématicien perse Al-Khwârizmî qui s'est inspiré des textes de mathématiques indiens et qui a complété les travaux de l'école grecque, laquelle continuera de se développer des siècles durant.

Recherche de chemin

La recherche de chemin, couramment appelée pathfinding par anglicisme, est un problème de l'intelligence artificielle qui se rattache plus généralement au domaine de la planification et de la recherche de solution. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes. Initialement, un problème de pathfinding peut se ramener à un problème de recherche du meilleur chemin entre deux nœuds dans un graphe.

Combinatoire

En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements. La combinatoire est en fait présente dans toute l'antiquité en Inde et en Chine. Donald Knuth, dans le volume 4A « Combinatorial Algorithms » de The Art of Computer Programming parle de la génération de n-uplets ; il dit que la génération de motifs combinatoires «a commencé alors que la civilisation elle-même prenait forme» (« began as civilization itself was taking shape»).

Afficher plus

Concepts associés (32)

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.

Graphe (mathématiques discrètes)

Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.

Afficher plus

Cours associés (32)

NX-421: Neural signals and signal processing

Understanding, processing, and analysis of signals and images obtained from the central and peripheral nervous system ...

MATH-106(f): Analyse II

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

MATH-101(g): Analyse I

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

Afficher plus

Séances de cours associées (14)

Bounded Network Flow: Problème Solvable Minult-Maxcret

Couvre la résolution des problèmes de flux de réseau borné en ajustant les capacités de flux et les contraintes, y compris les programmes binaires.

Programmation dynamique : le triangle de Pascal et l'algorithme de Floyd

Explore la programmation dynamique à travers le Triangle de Pascal et l'Algorithme de Floyd.

TrackMate: Analyse d'images et suivi des données

Présente TrackMate pour l'analyse d'image et le suivi des données, en mettant l'accent sur les caractéristiques, les défis et les conseils pratiques.

Afficher plus

MOOCs associés (2)

Fonctions Trigonométriques, Logarithmiques et Exponentielles

Ce cours dispense les connaissances fondamentales liées à ces fonctions. Il est articulé autour de 9 chapitres s'étendant sur 12 semaines: L'angle et sa mesure Les fonctions trigonométriques sinus et cosinus et leurs inverses Les fonctions trigonométriques tangente et cotangente et leurs inverses Les formules trigonométriques (addition, bissection, etc) Les oscillations harmoniques Les équations trigonométriques Les relations dans le triangle (théorèmes du sinus et du cosinus) Continuité et dérivabilité de

Information, Calcul, Communication: Introduction à la pensée informatique

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions de l’informatique théorique moderne. La seconde partie du cours sera quant à elle consacrée à l’information est la communication : nous passerons en revue plusieurs sujets, comme la représentation de l'information, le traitement des signaux, la compression de données, la communication et la cryptographie.

Personnes associées (30)

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

Patrick Thiran

Patrick Thiran is a full professor in network and systems theory at the School of Computer and Communication Sciences at EPFL. He holds an electrical engineering degree from the Université Catholique de Louvain, Louvain-la-Neuve, Belgium, an M.Sc. degree in electrical engineering from the University of California at Berkeley, USA, and he received the PhD degree from EPFL, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002, an associate professor in 2006 and a full professor in 2011. He was with Sprint Advanced Technology Labs in Burlingame, California, in 2000-01. His research interests are in communication and social networks, performance analysis and stochastic models. He is currently active in the analysis and design of wireless and PLC networks (scaling laws, medium access control), in network monitoring (network tomography, multi-layer networks), and data-driven network science. He also contributed to network calculus and to the theory of locally coupled neural networks and self-organizing maps. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99 and for the IEEE/ACM Transactions on Networking in 2006-10. He is currently on the editorial board of the IEEE Journal on Selected Areas in Communication. He is/was on the program committee of different conferences in networking, including ACM Sigcomm, Sigmetrics, IMC, CoNext and IEEE Infocom. He was TPC chair of AMC IMC 2011 and CoNext 2012. He is a Fellow of the Belgian American Educational Foundation and of the IEEE. He received the 1996 EPFL Doctoral Prize and the 2008 Crédit Suisse Teaching Award.

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.

Andreas Krause

Ola Nils Anders Svensson

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.

Sofia Charlotta Olhede

Sofia Olhede is a professor of Statistics at EPFL in Switzerland. She joined UCL prior to this in 2007, before which she was a senior lecturer of statistics (associate professor) at Imperial College London (2006-2007), a lecturer of statistics (assistant professor) (2002-2006), where she also completed her PhD in 2003 and MSci in 2000. She has held three research fellowships while at UCL: UK Engineering and Physical Sciences Springboard fellowship as well as a five-year Leadership fellowship, and now holds a European Research Council Consolidator fellowship. Sofia has contributed to the study of stochastic processes; time series, random fields and networks. Sofia was part of the multi-institutional team that set up the UK national data science institute, the Alan Turing Institute. She organised and served as chair of the science committee that developed the initial 500 000 pounds scientific programme of the institute; peer-reviewing over 100 workshop proposals and hosting over 30. She also chaired the first recruitment wave of the institute hiring 13 data scientists as a multi-university recruitment drive. Sofia was a member of the Royal Society and British Academy Data Governance Working Group, and the Royal Society working group on machine learning. Most recently she was one of 3 commissioners on a law society commission on the usage of algorithms in the justice system.

Maria Colombo

Enseignement et PhD Doctorant·es actuel·les Roberto Colombo, Antonio Tirotta, Carl Johan Peter Johansson, Giulia Mescolini A dirigé les thèses EPFL de Luigi De Rosa, Silja Noëmi Aline Haffter, Massimo Sorella Cours Analysis IV - Lebesgue measure, Fourier analysis MATH-205 Apprendre les bases de l'intégrale de Lebesgue et l'analyse de Fourier. Topics on the Euler and Navier-Stokes equations MATH-647

Giovanni De Micheli

Expertise Technologies de conception pour les systèmes intégrés, tels que la synthèse, le codesign de HW/SW et la conception de basse puissance. Technologies de conception des systèmes sur les plateformes hétérogènes comprenant les composants électriques, et biologiques. En savoir plus Consulter svp http://si2.epfl.ch/~demichel/ Enseignement et PhD A dirigé les thèses EPFL de Abhishek Garg, Mohamed Haykel Ben Jamaa, Francesco Zanini, Ciprian Seiculescu, Cristina Boero, Hu Xu, Andrea Cavallini, Shashi Kanth

Oliver Janzer

Enseignement et PhD Doctorant·es actuel·les Rik Sarkar Cours Algebraic methods in combinatorics MATH-526 Dans ce cours, nous étudions comment les méthodes algébriques peuvent être utilisées pour résoudre des problèmes de combinatoire. Les principaux outils utilisés proviennent de l'algèbre linéaire et de la théorie des polynômes. Graph theory MATH-360 Le cours introduit les concepts de base et certains résultats de la théorie moderne des graphes.

Afficher plus

Publications associées (30)

Ordered Ramsey numbers of graphs with 𝑚 edges

Given a vertex-ordered graph G G , the ordered Ramsey number r > ( G ) r_>(G) is the minimum integer N N such that every 2 2 -coloring of the edges of the complete ordered graph K N K_N contains a monochromatic ordered copy of G G . Motivated by a similar question posed by Erdős and Graham [ On partition theorems for finite graphs , Infinite and finite sets (Colloq., Keszthely, 1973), North-Holland, Amsterdam-London, pp. 515–527] in the unordered setting, we study the problem of bounding the ordered Ramsey

American Mathematical Society (AMS)2026

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

Clique density vs blowups

A well-known theorem of Nikiforov asserts that any graph with a positive

K_{r}

-density contains a logarithmic blowup of

K_r

. In this paper, we explore variants of Nikiforov’s result in the following form. Given

r,t\in \mathbb{N}

, when a positive

K_{r}

-density implies the existence of a significantly larger (with almost linear size) blowup of

K_t

? Our results include: • For an

n

-vertex ordered graph

G

with no induced monotone path

P_{6}

, if its complement

\overline {G}

has positive t

Cambridge University Press (CUP)2026

Afficher plus

Exercices associés (22)

Graphiques

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

Courant induit par une autre boucle de courant

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

Aller-Retour

A vehicle is in linear motion. The scalar velocity as a function of time is given by v(t)u2004=u2004b₀t²−u2006a₀txa0, where b₀ and a₀ are positive constants.

Determine the position x(t) of the vehicle as a function of time knowing that it is initially at the origin, i.e. x(0)u2004=u20040.
For b₀u2004=u20041 and a₀u2004=u20041, draw the graphs of the position x(t) and of the velocity v(t).
For b₀u2004=u20041 and a₀u2004=u20041, what happens at times tu2004=u20041 and $t=\frac{3}{2}

Problème à deux corps, centre de masse

We consider a square plate with side of length a and uniform density. We pierce a circular hole of radius R in the plate such that the distances between the hole’s edge and two adjacent edges of the plate are b and c, with b,u2006cu2004

Coquille sphérique

Calculate, in any point of space, the electrostatic potential

V(\bf{r})

and the field

\bf{E}(\bf{r})

created by a spherical shell uniformly charged with an internal radius a, external b, and of total charge u2005+u2005Q, centered at the origin O of the cartesian axes. Graphically represent the functions

V(\bf{r})

and

E_r(\bf{r})

(the radial component of

\bf{E}(\bf{r})

) Replace now the charged shell by an ideal conductor of similar shape. The conductor is neutral and isolated. A charge u2005+u2005

Afficher plus

Notebooks associés (25)

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

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

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

Estimation of Electron Density and Mean Free Time for Transparent Conductors

Chapter 1: Transparent Conductors[1]¶ Instruction: The purpose of this notebook is to try and find values of electron density and mean free time for a material suitable to be used as a transparent conductors. The final estimate should be the order of the two parameters to be used[2]¶ In [1]: import numpy as np from bokeh.io import push_notebook, output_notebook, show from bokeh.layouts import row, column from bokeh.plotting import figure output_notebook() from ipywidgets import interact from collect

Exercices associés (22)

Graphiques

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

Courant induit par une autre boucle de courant

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

Aller-Retour

A vehicle is in linear motion. The scalar velocity as a function of time is given by v(t)u2004=u2004b₀t²−u2006a₀txa0, where b₀ and a₀ are positive constants.

Determine the position x(t) of the vehicle as a function of time knowing that it is initially at the origin, i.e. x(0)u2004=u20040.
For b₀u2004=u20041 and a₀u2004=u20041, draw the graphs of the position x(t) and of the velocity v(t).
For b₀u2004=u20041 and a₀u2004=u20041, what happens at times tu2004=u20041 and $t=\frac{3}{2}

Problème à deux corps, centre de masse

Coquille sphérique

Calculate, in any point of space, the electrostatic potential

V(\bf{r})

and the field

\bf{E}(\bf{r})

V(\bf{r})

and

E_r(\bf{r})

(the radial component of

\bf{E}(\bf{r})

) Replace now the charged shell by an ideal conductor of similar shape. The conductor is neutral and isolated. A charge u2005+u2005

Afficher plus

Publications associées (30)

K_{r}

-density contains a logarithmic blowup of

K_r

. In this paper, we explore variants of Nikiforov’s result in the following form. Given

r,t\in \mathbb{N}

, when a positive

K_{r}

-density implies the existence of a significantly larger (with almost linear size) blowup of

K_t

? Our results include: • For an

n

-vertex ordered graph

G

with no induced monotone path

P_{6}

, if its complement

\overline {G}

has positive t

Cambridge University Press (CUP)2026

Afficher plus