Graphe (mathématiques discrètes)

ensemble de sommets reliés par des arê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é).

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

modifier
 
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, vV).

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

  • E ⊆ {{u, v} | (u, v) ∈ V2uv} : chaque arête est une paire de sommets distincte des autres. G est alors un graphe simple non orienté[4],[5].
  • ϕ : E → {{u, v} | (u, v) ∈ V2} : 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 ⊆ {(u, v) | (u, v) ∈ V2uv} : 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 → {(u, v) | (u, v) ∈ V2}, 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 ⊆ {{u, v} | (u, v) ∈ V2uv} et A ⊆ {(u, v) | (u, v) ∈ V2uv} : G est un graphe mixte simple.
  • Finalement, la définition la plus générale : G = (V, E, A, ϕE, ϕA), avec ϕE : E → {{u, v} | (u, v) ∈ V2} et ϕA : A → {(u, v) | (u, v) ∈ V2}. 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 = ∅ ⇒ E = ∅), bien que V soit généralement conçu comme non vide. Si |V| = 1 et E = ∅, 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

modifier

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

Graphe asymétrique

modifier

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

modifier

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.

Graphe complet

modifier
 
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

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

modifier

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

modifier
 
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

Un 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

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

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.

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.

Centralité

modifier

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

modifier

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

Applications

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

Extensions

modifier

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

Notes et références

modifier
  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. (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. 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,‎ , p. 240–253 (ISSN 0020-0255, DOI 10.1016/j.ins.2011.12.027).
  9. 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)
  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.

Annexes

modifier

Bibliographie

modifier

Ouvrages généraux

modifier

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., , 781 p. (ISBN 0-534-92373-9)
  • Ronald L. Graham, Martin Grötschel et László 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., 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, , 31e éd., 910 p. (ISBN 1-58488-291-3)

Ouvrages spécifiques

modifier

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

Articles connexes

modifier

Liens externes

modifier