Graphe (mathématiques discrètes)

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Cet article concerne les ensembles de sommets liés par des arêtes ou des arcs. Pour d'autres significations, voir graphe d'une fonction et graphe.
Un graphe avec six sommets et sept arêtes.

En mathématiques, et plus précisément en théorie des graphes, un graphe est une structure composée d'objets dans laquelle certaines paires d'objets sont en relation. Les objets correspondent à des abstractions mathématiques et sont appelés sommets (ou nœuds ou points), et les relations entre sommets sont des arêtes (ou liens ou lignes)[1]. 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 flèches, relient deux sommets de manière asymétrique.

Un graphe est fréquemment représenté par un diagramme sous la forme d'un ensemble de points pour les sommets, joints entre eux par des lignes droites ou courbes pour les arêtes, éventuellement munies de flèches pour le cas de graphes orientés. Les graphes sont l'un des objets d'étude du champ des mathématiques discrètes.

Les graphes constituent l'objet de base de la théorie des graphes. Le mot « graph » a été utilisé pour la première fois dans ce sens par James Joseph Sylvester en 1878[2],[3].

Définitions[modifier | modifier le code]

Article détaillé : Lexique de la théorie des graphes.

Il existe plusieurs variantes dans la définition des graphes en théorie des graphes. Les définitions les plus usuelles sont les suivantes.

Graphe[modifier | modifier le code]

Un graphe avec trois sommets et trois arêtes.

Dans un sens restreint mais très répandu du terme[4],[5], un graphe est un couple G = (V, E) comprenant

  • V un ensemble de sommets (aussi appelés nœuds ou points) ;
  • E ⊆ {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} un ensemble d'arêtes (aussi appelées liens or lignes), qui sont des paires de sommets (c.-à-d. qu'une arête est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un graphe simple non orienté.

Dans l'arête {x, y}, les sommets x et y sont appelés les extrémités ou les sommets extrêmes de l'arête. On dit que l'arête joint x et y et est incidente sur x et sur y. Un sommet peut exister dans un graphe sans arête incidente. Une boucle est une arête qui joint un sommet à lui-même. Les arêtes multiples sont deux arêtes ou plus qui joignent les mêmes deux sommets.

Dans un sens plus général du terme autorisant les arêtes multiples[6],[7], un graphe est un triplet G = (V, E, ϕ) comprenant

  • V un ensemble de sommets (aussi appelés nœuds ou points) ;
  • E un ensemble d'arêtes (aussi appelés liens ou lignes) ;
  • ϕ: E → {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} une fonction d'incidence associant à chaque arête une paire de sommets (c.-à-d. qu'une arête est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un multigraphe non orienté.

Les graphes tels que définis dans les deux définitions précédentes ne peuvent pas avoir de boucles, car une boucle joignant un sommet x est l'arête (pour un graphe simple non orienté) ou est incidente sur (pour un multigraphe non orienté) {x, x} = {x} qui n'est pas dans {{x, y} | (x, y) ∈ V2 ∧ x ≠ y}. Ainsi pour autoriser les boucles les définitions doivent être étendues. Pour les graphes simples non orientés, E ⊆ {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} doit devenir E ⊆ {{x, y} | (x, y) ∈ V2}. Pour les multigraphes non orientés, ϕ: E → {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} doit devenir ϕ: E → {{x, y} | (x, y) ∈ V2}. Pour lever toute ambiguïté, ces types d'objets peuvent être appelés précisément un graphe simple non orienté avec boucles et un multigraphe non orienté avec boucles respectivement.

V et E sont en général supposés finis, et de nombreux résultats cessent d'être vrais (ou ont des énoncés différents) pour des graphes infinis parce que certains arguments de preuve ne se transposent pas au cas infini. De plus, V est souvent supposé non vide, mais E peut être l'ensemble vide.

L'ordre d'un graphe |V| est son nombre de sommets. La taille d'un graphe est |E|, son nombre d'arêtes. Le degré ou la valence d'un sommet est le nombre d'arêtes incidentes à ce sommet, où une boucle compte double.

Dans un graphe simple non orienté d'ordre n, le degré maximum d'un sommet est n − 1 et la taille maximale du graphe est n(n − 1)/2.

Les arêtes E d'un graphe non orienté G induisent une relation binaire symétrique ~ sur V appelée le relation d'adjacence de G. Spécifiquement, pour chaque arête {x, y}, ses sommets extrêmes x et y sont dits adjacents l'un l'autre, ce qui est noté x ~ y.

Graphe orienté[modifier | modifier le code]

Article détaillé : Graphe orienté.
Un graphe orienté avec trois sommets et quatre arêtes.

Un graphe orienté est un graphe dans lequel les arêtes possèdent une orientation.

Dans un sens restreint mais très répandu du terme[8], un graphe orienté est un couple G = (V, A) (parfois G = (V, E)) comprenant

  • V un ensemble de sommets (aussi appelés nœuds ou points) ;
  • A ⊆ {(x, y) | (x, y) ∈ V2xy} un ensemble de flèches (aussi appelées arêtes orientées — parfois simplement arêtes avec l'ensemble correspondant nommé E au lieu de A —, liens orientés ou lignes orientées), qui sont des couples de sommets distincts (c.-à-d. une flèche est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un graphe simple orienté.

Dans la flèche (x, y) orientée de x vers y, x est appelé la queue de la flèche et y la tête de la flèche. La flèche (y, x) est appelée la flèche inverse de (x, y).

Dans un sens plus général du terme autorisant les flèches multiples[6],[7], un graphe orienté est un triplet G = (V, A, ϕ) (parfois G = (V, E, ϕ)) comprenant

  • V un ensemble de sommets (aussi appelés nœuds ou points) ;
  • A un ensemble de flèches (aussi appelées arêtes orientées — parfois simplement arêtes avec l'ensemble correspondant nommé E au lieu de A —, liens orientés ou lignes orientées);
  • ϕ: A → {(x, y) | (x, y) ∈ V2 ∧ x ≠ y} une fonction d'incidence associant à chaque flèche un couple de sommets distincts (c.-à-d. une flèche est associée à deux sommets distincts).

Pour lever toute ambiguïté, ce type d'objet peut être appelé précisément un multigraphe orienté.

Les graphes orientés tels que définis dans les deux définitions précédentes ne peuvent pas avoir de boucles, car une boucle joignant un sommet x est la flèche (pour un graphe simple orienté) ou est incidente sur (pour un multigraphe orienté) (x, x) qui n'est pas dans {(x, y) | (x, y) ∈ V2 ∧ x ≠ y}. Ainsi pour autoriser les boucles les définitions doivent être étendues. Pour les graphes simples orientés, A ⊆ {(x, y) | (x, y) ∈ V2 ∧ x ≠ y} doit devenir AV2. Pour les multigraphes orientés, ϕ: A → {(x, y) | (x, y) ∈ V2 ∧ x ≠ y} doit devenir ϕ: AV2. Pour lever toute ambiguïté, ces types d'objets peuvent être appelés précisément un graphe simple orienté avec boucles et un multigraphe orienté avec boucles (ou un carquois) respectivement.

Un graphe simple orienté avec boucles est une relation homogène (une relation binaire entre un ensemble et lui-même). Un graphe simple orienté avec boucles G = (V, A) est dit symétrique si, pour chaque flèche de A, la flèche inverse correspondante appartient aussi à A.

Graphe mixte[modifier | modifier le code]

Un graphe mixte est un graphe composé d'arêtes non orientées et d'arêtes orientées. C'est un triplet G = (V, E, A) pour un graphe mixte simple et G = (V, E, A, ϕE, ϕA) pour un multigraphe mixte avec V, E, A, ϕE et ϕA définis comme précédemment. Les graphes orientés et non orientés en sont des cas particuliers.

Graphe pondéré[modifier | modifier le code]

Un graphe pondéré avec dix sommets et douze arêtes.

Un graphe pondéré ou un réseau[9] est un graphe où chaque arête porte un nombre (son poids)[10]. Ces poids peuvent représenter par exemple des coûts, des longueurs ou des capacités, en fonction du problème traité. Ces graphes sont fréquents dans divers contextes, comme le problème de plus court chemin ou le problème du voyageur de commerce.

Types de graphes[modifier | modifier le code]

Graphe asymétrique[modifier | modifier le code]

Un graphe asymétrique (en anglais « oriented graph ») est un graphe orienté où l'un au plus des couples (x, y) et (y, x) est une flèche du graphe. Un tel graphe est sans boucle. On peut le voir comme résultant du choix d'une orientation pour chaque arête d'un graphe non orienté sans boucle.

Graphe régulier[modifier | modifier le code]

Article détaillé : Graphe régulier.

Un graphe régulier est un graphe (non orienté) où tous les sommets ont même degré. Si ce degré est k, on parle aussi de graphe k-régulier.

Graphe complet[modifier | modifier le code]

Article détaillé : Graphe complet.
Le graphe complet à 7 sommets.

Un graphe complet est un graphe simple dont les sommets sont tous adjacents les uns aux autres, c'est-à-dire tel que tout couple de sommets distincts 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 flèches (une dans chaque sens).

Graphe fini[modifier | modifier le code]

Un graphe fini est un graphe dont l'ensemble de sommets est fini (et donc aussi l'ensemble d'arêtes). Dans le cas contraire, c'est un graphe infini. Le plus souvent, les graphes considérés sont tacitement supposés finis ; s'ils sont infinis, ceci est spécifié explicitement.

Graphe connexe[modifier | modifier le code]

Article détaillé : Graphe connexe.

Un graphe connexe est un graphe non orienté où toute paire de sommets est reliée par une chaîne. Un graphe orienté, est connexe si le graphe non orienté obtenu en oubliant les orientations des arêtes est connexe. Il est fortement connexe si tout couple de sommets est relié par un chemin, donc si pour tout couple (x, y) de sommets, il y a un chemin de x à y et un chemin de y à x. Un graphe k-sommet-connexe est un graphe qui possède au moins k+1 sommets et qui reste encore connexe après en avoir ôté k–1 ; de même, un graphe k-arête-connexe est un graphe qui reste connexe quand on lui enlève k–1 arêtes.

Graphe biparti[modifier | modifier le code]

Article détaillé : Graphe biparti.
Un graphe biparti complet.

Un graphe biparti est un graphe dont l'ensemble des sommets peut être partitionné en deux ensembles X et Y de telle sorte qu'il n'y a pas d'arête entre deux sommets de X ni entre deux sommets de Y. De manière équivalente, un graphe biparti est un graphe dont le nombre chromatique est 2.

Un graphe biparti complet est un graphe biparti où tous les sommets de X sont reliés à tous les sommets de Y et vice-versa.

Chaîne[modifier | modifier le code]

Article détaillé : Chaîne (théorie des graphes).

Une graphe est une chaîne d'ordre n ≥ 2 s'il est composé de sommets n qu'on peut numéroter de telle sorte que les arêtes sont {vi, vi+1} pour i = 1, 2, …, n − 1. Une chaîne est, de manière équivalente, un graphe connexe dont tous les sommets sont de degré 2 sauf deux qui sont de degré 1. Une chaîne dans un graphe est un sous-graphe partiel de ce graphe.

Graphe planaire[modifier | modifier le code]

Article détaillé : Graphe planaire.

Un graphe planaire est un graphe que l'on peut dessiner dans le plan (ou sur une sphère) sans que deux arêtes ne se croisent.

Graphe cycle[modifier | modifier le code]

Article détaillé : Graphe cycle.

Un graphe cycle d'ordre ou n-cycle est un graphe dont les sommets peuvent être numérotés de sorte que les arêtes sont les paires pour plus l'arête . Un graphe cycle peut être caractérisé comme étant un graphe connexe dont tous les sommets ont degré 2.

Arbre[modifier | modifier le code]

Article détaillé : Arbre (théorie des graphes).

Un arbre est un graphe connexe acyclique.

Une forêt est un graphe acyclique, c'est-à-dire une union disjointe d'un ou plusieurs arbres.

Autres classes[modifier | modifier le code]

D'autres classes de graphes comprennent:

Propriétés de graphes[modifier | modifier le code]

Deux arêtes d'un graphe sont adjacentes si elles ont un sommet en commun. Deux arcs d'un graphe orienté sont consécutifs si la fin du premier arc est le début du deuxième. De même, deux sommets sont adjacents s'il sont extrémités d'une même arête (d'un même arc). Une arête et un sommet adjacent sont dits incidents l'un à l'autre.

Le graphe formé d'un seul sommet et sans arêtes est souvent appelé trivial ; le graphe sans sommet ni arête est aussi appelé parfois le graphe nul.

Un graphe est étiqueté aux sommets si chaque sommet porte une étiquette. Un graphe est étiqueté aux arêtes si chaque arête porte une étiquette. On peut considérer, dans les problèmes d'énumération ou de bijection, des graphes étiquetés ou non étiquetés. Un graphe dont les sommets (ou les arêtes) sont étiquetés par des couleurs est un graphe coloré.

Propriétés de centralités d'un graphe[modifier | modifier le code]

Article détaillé : centralité.

Dans l'analyse de graphes, la centralité mesure la pertinence et l'importance d'un sommet. On distingue :

D'autres mesures sont l'excentricité d'un sommet qui est la distance maximale à tout autre sommet, le diamètre d’un graphe ou le rayon .

Opérations sur les graphes[modifier | modifier le code]

Les diverses opérations qui produisent de nouveaux graphes à partir de graphes donnés peuvent être regroupées en :

Applications[modifier | modifier le code]

Le graphe de Cayley du groupe libre sur a et b.
Molécule de saccharine.

Extensions[modifier | modifier le code]

Les graphes se généralisent dans plusieurs directions :

Articles liés[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Trudeau 1993, p. 19 : « A graph is an object consisting of two sets called its vertex set and its edge set ».
  2. Dans :J. J. Sylvester, « Chemistry and algebra », Nature, vol. 17,‎ , p. 284 : "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph." (DOI 10.1038/017284a0, lire en ligne). et J. J. Sylvester, « On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, — with three appendices », American Journal of Mathematics, Pure and Applied’, vol. 1, no 1,‎ , p. 64–90 (DOI 10.2307/2369436, lire en ligne)}.
  3. Gross et Yellen 2004, p.35.
  4. (en) Edward A. Bender et S. Gill Williamson, Lists, Decisions and Graphs : With an Introduction to Probability, , 251 p. (lire en ligne), p. 148
  5. Par exemple (Iyanaga et Kawada 1977, p. 234) ou (Biggs 1993, p. 4).
  6. a et b (en) Edward A. Bender et S. Gill Williamson, Lists, Decisions and Graphs : With an Introduction to Probability, , 251 p. (lire en ligne), p. 149
  7. a et b Par exemple (Graham et. al. 1995, p. 5).
  8. (en) Edward A. Bender et S. Gill Williamson, Lists, Decisions and Graphs : With an Introduction to Probability, , 251 p. (lire en ligne), p. 161
  9. Strang 2005.
  10. Fletcher, Hoyle et Patty 1991, p. 463 : A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.
  11. Xingqin Qi, Eddie Fuller, Qin Wu et Yezhou Wu, « Laplacian centrality: A new centrality measure for weighted networks », Information Sciences, vol. 194,‎ , p. 240–253 (ISSN 0020-0255, DOI 10.1016/j.ins.2011.12.027).
  12. Martin Grandjean, « A social network analysis of Twitter: Mapping the digital humanities community », Cogent Arts & Humanities, vol. 3, no 1,‎ , p. 1171458 (DOI 10.1080/23311983.2016.1171458, lire en ligne)
  13. Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web. DOI:10.1145/2488388.2488433.

Références[modifier | modifier le code]

Ouvrages généraux

Tous les manuels de mathématiques discrètes contiennent un traitement des graphes :

  • Peter Fletcher, Hughes Hoyle et C. Wayne Patty, Foundations of Discrete Mathematics, Boston, PWS-KENT Pub. Co., (ISBN 0-53492-373-9)
  • Ronald L. Graham, Martin Grötschel et Lovász Lovász (direction), Handbook of Combinatorics, MIT Press, (ISBN 0-262-07169-X)
  • Shôkichi Iyanaga et Yukiyosi Kawada, Encyclopedic Dictionary of Mathematics, MIT Press, (ISBN 0-262-09016-3)
  • Gilbert Strang, Linear Algebra and Its Applications, Brooks Cole, , 4e éd. (ISBN 0-03-010567-6, lire en ligne).
  • Daniel Zwillinger, CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC, , 31e éd. (ISBN 1-58488-291-3)
Ouvrages spécifiques

De nombreux livres sont centrés sur la théorie des graphes :

Lien externe[modifier | modifier le code]