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)^[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 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é).

Un graphe avec six sommets et sept arêtes.
Le même graphe, pivoté et avec les arêtes étiquetées.
Un graphe orienté à sept sommets.
Graphe contenant des milliers de sommets.

Le mot « graph » a été utilisé pour la première fois dans ce sens par James Joseph Sylvester en 1878^[2]^,^[3].

Définition et vocables associés

Article connexe : Lexique de la théorie des graphes.

Un graphe avec trois sommets et trois arêtes.

Un graphe orienté avec trois sommets et quatre arcs.

Un graphe est un couple $G = (V, E)$ comprenant deux ensembles :

$V$ : sommets ;
$E$ : arêtes, chacune étant associée à un couple $(u, v)$ ou une paire ${u, v}$ de sommets ( $u, v \in V$ ).

Des définitions plus restreintes pour $E$ sont souvent employées :

$E \subseteq {{u, v} | (u, v) \in V 2 \land u \neq v}$ : chaque arête est une paire de sommets distincte des autres. $G$ est alors un graphe simple non orienté^[4]^,^[5].
$ϕ : E \to {{u, v} | (u, v) \in V 2}$ : chaque arête est associée par la fonction d'incidence $ϕ$ à une paire de sommets (ou à un singleton si $u = v$ ). $G$ est alors un multigraphe non orienté. Ce n'est plus un couple mais un triplet $G = (V, E, ϕ)$ ^[6]^,^[7].
$E \subseteq {(u, v) | (u, v) \in V 2 \land u \neq v}$ : chaque arête est un couple distinct des autres, de deux sommets distincts l'un de l'autre. $G$ est alors un graphe simple orienté. Les arêtes sont plus souvent appelées arcs, et leur ensemble $A$ plutôt que $E$ .
$ϕ : E \to {(u, v) | (u, v) \in V 2}$ , avec $G = (V, E, ϕ)$ : chaque arc est associé par la fonction d'incidence $ϕ$ à un couple de sommets. $G$ est alors un multigraphe orienté (ou carquois).
$G = (V, E, A)$ , avec $E \subseteq {{u, v} | (u, v) \in V 2 \land u \neq v}$ et $A \subseteq {(u, v) | (u, v) \in V 2 \land u \neq v}$ : $G$ est un graphe mixte simple.
Finalement, la définition la plus générale : $G = (V, E, A, ϕ E, ϕ A)$ , avec $ϕ E : E \to {{u, v} | (u, v) \in V 2}$ et $ϕ A : A \to {(u, v) | (u, v) \in V 2}$ . $G$ est alors un multigraphe mixte.

Plus vulgairement :

Un graphe simple ne comporte ni boucles (arêtes ${u}$ ou arcs $(u, u)$ , c.-à.-d. joignant un sommet à lui-même) ni arêtes multiples (arêtes étant associées au même duo de sommets). Pour expliciter le fait qu'un graphe peut comporter des boucles et des arêtes multiples, on peut employer le terme multigraphe.
Un graphe orienté est un graphe dans lequel toutes les arêtes possèdent une orientation et sont alors qualifiées d'arcs. Un graphe mixte comporte à la fois des arêtes non orientées et des arcs.

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

Les arêtes et arcs sont des objets abstraits reliant deux sommets. Ils peuvent comporter d'autres propriétés. Très souvent, il s'agit d'un nombre, auquel cas le graphe est dit pondéré ou valué. Ce nombre, appelé poids, peut représenter par exemple des coûts, des longueurs ou des capacités. De nombreux problèmes et algorithmes sont associés aux graphes pondérés, entre autres le problème du plus court chemin et le problème du voyageur de commerce.

Pour une arête ${u, v}$ ou un arc $(u, v)$ , $u$ et $v$ sont les extrémités de l'arête. L'arête joint $u$ et $v$ et est incidente à $u$ ainsi qu'à $v$ . $u$ et $v$ sont dits liés, connectés, adjacents ou encore voisins. L'arête est adjacente aux autres arêtes incidentes à $u$ ou à $v$ . Dans le cas d'un arc, il sort de $u$ et entre dans $v$ , et $v$ est consécutif à $u$ . L'arc est consécutif aux arcs entrant dans $u$ . Les arêtes induisent une relation binaire (symétrique pour une arête non orientée, asymétrique pour un arc) $~$ sur $V$ appelée relation d'adjacence de $G$ : $u ~ v$ signifie « $u$ est adjacent à $v$ ».

L'ordre d'un graphe est son nombre de sommets ( $| V |$ ). La taille d'un graphe est son nombre d'arêtes ( $| E |$ ). Le degré (ou la valence) d'un sommet est le nombre d'arêtes incidentes à ce sommet, où une boucle compte double. On peut distinguer le degré sortant et le degré entrant, qui dénombrent seulement soit les arcs sortants soit les arcs entrants. 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$ .

$V$ et $E$ sont en général supposés finis. De nombreux résultats cessent d'être vrais (ou ont des énoncés différents) pour les graphes infinis car certains arguments de preuve ne se transposent pas au cas infini. $V$ et $E$ peuvent être vides (graphe nul, et bien entendu $V = \emptyset \Rightarrow E = \emptyset$ ), bien que $V$ soit généralement conçu comme non vide. Si $| V | = 1$ et $E = \emptyset$ , le graphe est dit trivial.

Un graphe est étiqueté aux sommets si chaque sommet porte une étiquette ; il 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 parfois les arêtes) sont étiquetés par des couleurs est un graphe coloré, qui peut être une réponse à un problème de coloration de graphe.

Classes

De nombreux types de graphes ont été définis.

Graphe asymétrique

Articles détaillés : Graphe asymétrique et Graphe symétrique.

Un graphe asymétrique (en anglais « oriented graph », alors qu'un graphe orienté est appelé « directed graph ») est un graphe orienté où l'un au plus des couples $(u, v)$ et $(v, u)$ 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

Article détaillé : Graphe régulier.

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

Articles connexes : Graphe fortement régulier et Graphe distance-régulier.

Graphe complet

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

Un graphe fini est un graphe ayant un nombre fini de sommets et 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

Articles détaillés : Graphe connexe et Graphe fortement 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 $(u, v)$ de sommets, il y a un chemin de $u$ à $v$ et un chemin de $v$ à $u$ . 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

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

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

Un graphe est une chaîne d'ordre $n \geq 2$ s'il est composé de sommets $n$ qu'on peut numéroter de telle sorte que les arêtes sont ${v i, v i +1}$ pour $i = 1, 2, \dots, 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

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

Article détaillé : Graphe cycle.

Un graphe cycle d'ordre $n\geq 3$ ou n-cycle est un graphe dont les sommets peuvent être numérotés $v_{1},\ldots ,v_{n}$ de sorte que les arêtes sont les paires $[v_{i},v_{i+1}]$ pour $i=1,\ldots ,n-1$ plus l'arête $[v_{n},v_{1}]$ . Un graphe cycle peut être caractérisé comme étant un graphe connexe dont tous les sommets ont degré 2.

Arbre

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

Graphe orienté acyclique
Graphe de Petersen et ses généralisations
Graphe parfait
Cographe
Graphe cordal
En fonction du groupe d'automorphisme : graphe sommet-transitif, graphe symétrique, et graphe distance-transitif

Centralité

Article détaillé : Centralité.

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

la centralité de degré qui utilise le degré ;
la centralité de proximité qui utilise l'inverse de la somme des distances à tous les autres sommets ;
la centralité d'intermédiarité qui utilise le nombre de plus courts chemins passant par le sommet^[8].

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

Opérations sur les graphes

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

opérations unaires, qui créent un nouveau graphe à partir d'un ancien, comme :
- contraction d'arête,
- line graph,
- graphe dual,
- graphe complémentaire,
- réécriture de graphes.
opérations binaires, qui créent un nouveau graphe à partir de deux anciens, comme :
- union disjointe de graphes,
- produit cartésien,
- produit tensoriel,
- produit fort,
- produit lexicographique,
- graphe série-parallèle.

Applications

Le graphe de Cayley du groupe libre sur a et b.

Molécule de saccharine.

En théorie des catégories, une catégorie peut être représentée par un multigraphe orienté dont les sommets représentent les objets et les arêtes les morphismes. Un foncteur entre catégories induit un morphisme de graphes.
En informatique, les graphes orientés sont utilisés pour représenter des notions comme les graphes conceptuels, les automates finis et de nombreuses autres structures discrètes. Il est également possible de modéliser le fonctionnement d'un réseau neuronal artificiel, ou encore le schéma décisionnel d'une intelligence artificielle.
Une relation binaire R sur un ensemble X définit un graphe orienté (et réciproquement). Il y a une flèche de x à y dans le graphe si et seulement si xRy.
Un graphe peut modéliser des informations sur des réseaux sociaux, comme la notion de « follower » dans Twitter^[9]^,^[10].
Des exemples de graphes orientés réguliers sont les graphes de Cayley de groupes finiment engendrés, ou le graphe des cosets de Schreier (en).
En chimie et notamment dans la représentation simplifiée des liaisons entre atomes formant une molécule, des graphes en général non orientés mais avec des arêtes multiples sont largement utilisés.

Extensions

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

Dans un hypergraphe, une arête peut relier plus de deux sommets.
Un graphe non orienté peut être vu comme un complexe simplicial dont les 1-Simplexes sont les arêtes et les 0-simplexes les sommets. Sous cet aspect, les complexes simpliciaux sont des généralisation des graphes à des dimensions plus élevées.
Tout graphe donne aussi un matroïde.
En théorie des modèles, un graphe est juste une structure logique. Dans ce cadre, il n'y a pas de limitation aux nombre d'arêtes qui peut être tout nombre cardinal.
En bio-informatique, l'analyse en graphe de puissance introduit de graphes particuliers (les « power graphs ») comme une alternative pour la représentation de graphes non orientés.
Dans les systèmes d'information géographique, les réseaux géométriques sont des modèles proches des graphes, et empruntent à la théorie des graphes de nombreux concepts pour l'analyse spatiales sur les réseaux routiers ou des repères d'utilisation.

Notes et références

↑ Trudeau 1993, p. 19 : « A graph is an object consisting of two sets called its vertex set and its edge set. »
↑ Dans : J. J. Sylvester, « Chemistry and algebra », Nature, vol. 17,‎ 7 février 1878, 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, n^o 1,‎ 1878, p. 64–90 (DOI 10.2307/2369436, lire en ligne).
↑ Gross et Yellen 2004, p.35.
↑ (en) Edward A. Bender et S. Gill Williamson, Lists, Decisions and Graphs : With an Introduction to Probability, 2010, 251 p. (lire en ligne), p. 148
↑ Par exemple (Iyanaga et Kawada 1977, p. 234) ou (Biggs 1993, p. 4).
↑ (en) Edward A. Bender et S. Gill Williamson, Lists, Decisions and Graphs : With an Introduction to Probability, 2010, 251 p. (lire en ligne), p. 149
↑ Par exemple (Graham et. al. 1995, p. 5).
↑ Xingqin Qi, Eddie Fuller, Qin Wu et Yezhou Wu, « Laplacian centrality: A new centrality measure for weighted networks », Information Sciences, vol. 194,‎ juillet 2012, p. 240–253 (ISSN 0020-0255, DOI 10.1016/j.ins.2011.12.027).
↑ Martin Grandjean, « A social network analysis of Twitter: Mapping the digital humanities community », Cogent Arts & Humanities, vol. 3, n^o 1,‎ 2016, p. 1171458 (DOI 10.1080/23311983.2016.1171458, lire en ligne)
↑ 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.

Annexes

Bibliographie

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., 1991, 781 p. (ISBN 0-534-92373-9)
Ronald L. Graham, Martin Grötschel et László Lovász (direction), Handbook of Combinatorics, MIT Press, 1995 (ISBN 0-262-07169-X)
Shôkichi Iyanaga et Yukiyosi Kawada, Encyclopedic Dictionary of Mathematics, MIT Press, 1977 (ISBN 0-262-09016-3)
Gilbert Strang, Linear Algebra and Its Applications, Brooks Cole, 2005, 4^e éd., 487 p. (ISBN 0-03-010567-6, lire en ligne).
(en) Daniel Zwillinger, CRC Standard Mathematical Tables and Formulae, Boca Raton/London/New York etc., Chapman & Hall/CRC, 27 novembre 2002, 31^e éd., 910 p. (ISBN 1-58488-291-3)

Ouvrages spécifiques

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

R. Balakrishnan et K. Ranganathan, A Textbook of Graph Theory, New York, Springer-Verlag, coll. « Universitext », 2012, xiii+292 (ISBN 978-1-4614-4528-9, DOI 10.1007/978-1-4614-4529-6, lire en ligne)
Claude Berge, Théorie des graphes et ses applications, Paris, Collection Universitaire de Mathématiques, 1963, 2^e éd., viii+267 (SUDOC 007608756)
(en) Norman Biggs, Algebraic Graph Theory, Cambridge, Cambridge University Press, 1993, 2^e éd., 205 p. (ISBN 0-521-45897-8)
(en) Béla Bollobás, Modern Graph Theory, New York/Berlin/Paris, Springer, 12 août 2002, 1^re éd., 394 p. (ISBN 0-387-98488-7)
Alain Bretto, Alain Faisant et François Hennecart, Elements of Graph Theory: From Basic Concepts to Modern Developments, European Mathematical Society Press, 2022 (ISBN 978-3-98547-017-4, lire en ligne)
Jørgen Bang-Jensen et Gregory Z. Gutin, Digraphs : Theory, Algorithms and Applications, Springer-Verlag, 2000 (lire en ligne)
Reinhard Diestel, Graph Theory, Springer, coll. « Graduate Texts in Mathematics » (n^o 173), août 2016 (réimpr. 2010, 2005, 2000, 1997), 5^e éd., 447 p. (ISBN 978-3-662-53621-6 et 978-3-96134-005-7, présentation en ligne, lire en ligne)
(en) Jonathan L. Gross et Jay Yellen, Graph Theory and Its Applications, Boca Raton (Fla.)/London/New York etc., CRC Press, 30 décembre 1998, 585 p. (ISBN 0-8493-3982-0, lire en ligne)
Jonathan L. Gross et Jay Yellen (éditeurs), Handbook of graph theory, CRC Press, 2004, 1192 p. (ISBN 978-1-58488-090-5, lire en ligne).
Frank Harary, Graph Theory, Addison Wesley Publishing Company, janvier 1995 (ISBN 0-201-41033-8)
Richard J. Trudeau, Introduction to Graph Theory, New York, Dover Publications, 1993, 209 p. (ISBN 978-0-486-67870-2, présentation en ligne)

Articles connexes

Liens externes

(en) Eric W. Weisstein, « Graph », sur MathWorld
Notices dans des dictionnaires ou encyclopédies généralistes :

[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,‎ 7 février 1878, 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, n^o 1,‎ 1878, 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, 2010, 251 p. (lire en ligne), p. 148

[5] Par exemple (Iyanaga et Kawada 1977, p. 234) ou (Biggs 1993, p. 4).

[B&W-6] (en) Edward A. Bender et S. Gill Williamson, Lists, Decisions and Graphs : With an Introduction to Probability, 2010, 251 p. (lire en ligne), p. 149

[GGL_p5-7] Par exemple (Graham et. al. 1995, p. 5).

[8] Xingqin Qi, Eddie Fuller, Qin Wu et Yezhou Wu, « Laplacian centrality: A new centrality measure for weighted networks », Information Sciences, vol. 194,‎ juillet 2012, p. 240–253 (ISSN 0020-0255, DOI 10.1016/j.ins.2011.12.027).

[snatwitter-9] Martin Grandjean, « A social network analysis of Twitter: Mapping the digital humanities community », Cogent Arts & Humanities, vol. 3, n^o 1,‎ 2016, p. 1171458 (DOI 10.1080/23311983.2016.1171458, lire en ligne)

[twitterwtf-10] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]