Concept

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. Les graphes sont couramment représentés graphiquement à l'aide de cercles pour les sommets et de lignes (éventuellement courbées) pour les arêtes, ces dernières étant munies de flèches s'il y a une orientation. Lorsque les graphes sont très grands, la taille des sommets est souvent fonction du nombre de leurs relations (le degré). Fichier:6n-graf.svg|Un graphe avec six sommets et sept arêtes. Fichier:6n-graph3.svg|Le même graphe, pivoté et avec les arêtes étiquetées. Fichier:Dominance drawing.svg|Un graphe orienté à sept sommets. Fichier:Social Network Analysis Visualization.png|Graphe contenant des milliers de sommets. Le mot a été utilisé pour la première fois dans ce sens par James Joseph Sylvester en 1878. vignette|Un graphe avec trois sommets et trois arêtes.|150x150px vignette|Un graphe orienté avec trois sommets et quatre arêtes.|150x150px 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). Des définitions plus restreintes pour sont souvent employées : chaque arête est une paire de sommets distincte des autres. est alors un graphe simple non orienté. chaque arête est associée par la fonction d'incidence à une paire de sommets (ou à un singleton si ). est alors un multigraphe non orienté. Ce n'est plus un couple mais un triplet . chaque arête est un couple distinct des autres, de deux sommets distincts l'un de l'autre. est alors un graphe simple orienté. Les arêtes sont plus souvent appelées arcs, et leur ensemble plutôt que .

Source officielle

https://fr.wikipedia.org/wiki/Graphe_(mathématiques_discrètes)

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Cours associés (32)

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

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

CS-401: Applied data analysis

This course teaches the basic techniques, methodologies, and practical skills required to draw meaningful insights from a variety of data, with the help of the most acclaimed software tools in the data science world (pandas, scikit-learn, Spark, etc.) ...

Afficher plus

MOOCs associés (1)

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.

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.

Source officielle

https://fr.wikipedia.org/wiki/Graphe_(mathématiques_discrètes)

À propos de ce résultat

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Cours associés (32)

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

PHYS-467: Machine learning for physicists

CS-401: Applied data analysis

Afficher plus

Séances de cours associées (32)

Points fixes dans la théorie des graphiques

Se concentre sur les points fixes dans la théorie des graphiques et leurs implications dans les algorithmes et l'analyse.

Propagation de la croyance

Explore la propagation de la croyance dans les modèles graphiques, les graphiques de facteurs, les exemples de verre de spin, les distributions de Boltzmann et les propriétés de coloration des graphiques.

Systèmes de contrôle en réseau : Matrix laplacien et consensus en continu

Explore les propriétés de la matrice laplacienne et le consensus en temps continu.

Afficher plus

Publications associées (32)

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

Personnes associées (32)

Vittorio Erba

Enseignement et PhD Cours Statistical physics of computation PHYS-512 Les étudiants comprennent les outils de la physique statistique des systèmes désordonnés et les appliquent pour étudier des problèmes d'informatique et de statistiques en théorie des graphes, en optimisation discrète, ainsi qu'en inférence et en apprentissage automatique.

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.

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

Simon Guilloud

Expertise I am a PhD student at EPFL working in the Laboratory of Automated Reasoning and Analysis with Prof. Viktor KunÄak.My main domains of research are proof assistants and algorithms for logic-related problems. Expertise I am a PhD student at EPFL working in the Laboratory of Automated Reasoning and Analysis with Prof. Viktor KunÄak.My main domains of research are proof assistants and algorithms for logic-related problems.

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

Pascal Fua

Pascal Fua received an engineering degree from Ecole Polytechnique, Paris, in 1984 and the Ph.D. degree in Computer Science from the University of Orsay in 1989. He then worked at SRI International and INRIA Sophia-Antipolis as a Computer Scientist. He joined EPFL in 1996 where he is now a Professor in the School of Computer and Communication Science and heads the Computer Vision Laboratory. His research interests include shape modeling and motion recovery from images, analysis of microscopy images, and Augmented Reality. His research interests include shape modeling and motion recovery from images, analysis of microscopy images, and machine learning. He has (co)authored over 300 publications in refereed journals and conferences. He is an IEEE Fellow and has been an Associate Editor of IEEE journal Transactions for Pattern Analysis and Machine Intelligence. He often serves as program committee member, area chair, and program chair of major vision conferences and has cofounded three spinoff companies (Pix4D, PlayfulVision, and NeuralConcept).

Katrin Beyer

Since 2017 Associate Professor, School of Architecture, Civil and Environmental Engineering (ENAC), EPFL. Head of the Earthquake Engineering and Structural Dynamics (EESD) Laboratory 2010-2017 Assistant Professor, EPFL. 2008-2010 Post-doctoral researcher, ETH Zürich. 2003-2007 Ph.D., Roseschool / Università di Pavia, Italy. 2001-2003 Ove Arup & Partners, Advanced Technology and Research Group, London. 2001 Diploma, Civil engineering, ETH Zürich.

Sacha Varone

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.

Thomas Mountford

D'origine britannique, né en 1961. Il a reçu la bourse présidentielle des jeunes investisseurs (Presidential Young Investigator Grant) en 1990 et le prix de la Fraternité Sloan (Sloan Fellowship) en 1991. Son travail montre que les valeurs critiques d'une classe large de de systèmes de particules proches sont égales à 1, et que, suite à plusieurs travaux sur la trajectoire du mouvement brownien, incluant une simulation numérique, le nombre d'îlots browniens en 2 dimensions tend vers l'infini quand leurs tailles tendent vers 0. Il reçoit le prix Rosenbaum en 1993 lui ouvrant ainsi les portes du Isaac Newton Institute à Cambridge. Il est également décoré par le prix Rollo Davidson en 1995 et nommé membre honoraire de l'Institute of Mathematical Statistics en 2001. Assistant Profeseur de Mathematique a UCLA 1987- 1991 Associate Professeur de Mathematique a UCLA 1991-1993 Professeur de Mathematique a UCLA 1993-2001 Professeur Departement de mathématiques, EPFL dès 2001

Afficher plus

Unités associées (27)

Laboratoire transport et mobilité

Laboratoire de traitement des signaux 4

SNAI - Gestion

Afficher plus

Concepts associés (32)

Graphe orienté

thumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.

Graphe complet

En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note .

Matrice d'adjacence

En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à n sommets est une matrice de dimension n × n dont l'élément non diagonal a est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal a est le nombre de boucles au sommet i (pour des graphes simples, ce nombre est donc toujours égal à 0 ou 1). Cet outil mathématique est très utilisé comme structure de données en informatique (tout comme la représentation par liste d'adjacence), mais intervient aussi naturellement dans les chaînes de Markov.

Afficher plus

MOOCs associés (1)

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

Exercices associés (2)

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

Notebooks associés (5)

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

Publications associées (32)

Ordered Ramsey numbers of graphs with 𝑚 edges

American Mathematical Society (AMS)2026

Spectral Clustering with Side Information

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

Personnes associées (32)

Notebooks associés (5)

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

Powder X-Ray Diffraction Analysis: Exploring Crystal Structures.

\theta

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

Ewald Sphere

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

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