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 orienté à 8 sommets, dont les arcs sont colorés.

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 « liés ». Les objets correspondent à des abstractions mathématiques et sont appelés sommets (ou nœuds ou points), et les liens entre sommets sont des arêtes (ou arcs ou lignes)[1]. 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 arêtes peuvent être orientées (on parle alors d'arcs) ou non, selon l'adéquation au modèle qu'elles doivent représenter. Dans le premier cas, on parle de graphes orientés, dans le deuxième de graphes non orientés.

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 de graphes en théorie des graphes. Les définitions les plus usuelles sont les suivantes.

Graphes[modifier | modifier le code]

En toute généralité[4], un graphe est un couple G = (V, E) formé d'un ensemble V de sommets ou nœuds ou points et d'un ensemble E d'arêtes, arcs ou lignes qui sont associés à des sous-ensembles à deux éléments de V. Pour éviter toute ambiguïté, on distingue les graphes non orientés, où les arêtes sont associées à des paires de sommets, et les graphes orientés, où les liens, appelés arcs, sont associés à des couples de sommets.

D'autres significations pour le terme graphe viennent d'une autre interprétation de l'ensemble des arêtes. Dans une acception plus étendue[5], E est un ensemble muni d'une relation d'incidence qui associe à chaque arête deux sommets. Une autre généralisation considère E comme un multiensemble de paires de sommets non nécessairement distincts. Un tel graphe est appelé par de nombreux auteurs multigraphe ou pseudographe.

Toutes ces variantes et d'autres sont décrite plus en détail plus loin.

Les sommets appartenant à une arête sont ses extrémités. Un sommet d'un graphe n'est pas nécessairement extrémité d'une arête : c'est alors un sommet isolé.

Les ensembles 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. La taille d'un graphe est, selon le cas, le nombre de ses sommets ou le nombre de ses arêtes. Le degré ou la valence d'un sommet est le nombre d'arêtes connectées à ce sommet ; une boucle compte deux fois dans ce calcul.

On rencontre, pour une arête {x, y}, l'écriture [x, y] ou l'écriture plus courte xy.

Relation d'adjacence[modifier | modifier le code]

Les arêtes E d'un graphe non orienté G induisent une relation binaire symétrique ~ sur V appelée la relation d'adjacence de G. Plus précisément, les sommets x et y sont dits adjacents si {x, y} est une arête du graphe ; on écrit alors x ~ y.

Types de graphes[modifier | modifier le code]

Comme dit ci-dessus, il peut être utile d'affiner le terme « graphe » dans différents contextes et avec différents degrés de généralité. Le plus souvent, dans les textes modernes de la théorie des graphes, sauf indication contraire, « graphe » signifie « graphe fini simple non orienté » , au sens de définition donnée plus loin.

Un graphe orienté à 3 sommets et 4 arcs.
Un graphe non orienté. Chaque sommet a degré 2 ; le graphe est régulier.

Graphe non orienté[modifier | modifier le code]

Un graphe non orienté est un graphe dont les arêtes n'ont pas d'orientation. Une arête est souvent notée [x, y] et est donc identique à l'arête [y, x]. En d'autres termes, une arête est une paire non ordonnée de sommets, donc un ensemble {x, y} à deux éléments (ou un 2-multiensemble dans le cas d'une boucle). Le nombre maximal d'arêtes dans un graphe non orienté à n sommets est égal à n(n − 1)/2.

Graphe orienté[modifier | modifier le code]

Un graphe orienté (en anglais « digraph ») est un graphe dont les arcs ont des orientations. Un graphe orienté G = (V, A) est donc composé d'un ensemble V de sommets, nœuds ou points, et d'un ensemble A de couples de sommets, appelés arcs, flèches ou lignes orientées.

Un arc (x, y) est considéré comme orienté de x vers y ; x est l'extrémité initiale ou l'origine ou le début de l'arc, et y est son extrémité terminale ou fin. Le sommet y est un successeur de x, et x est un prédécesseur de y. Si un chemin mène de x à y, alors y est un descendant de x et x est un ascendant de y. L'arc (y, x) est l'arc inverse ou retourné ou transposé de (x, y).

Un graphe orienté G est symétrique si, pour tout arc de G, l'arc retourné correspondant est encore un arc de G. Un graphe orienté symétrique sans boucles G = (V, A) est équivalent à un graphe non orienté simple G′ = (V, E), où les paires d'arcs mutuellement inverses de A sont en correspondance bijective avec les arêtes de E.

Graphe asymétrique[modifier | modifier le code]

Un graphe asymétrique et un graphe orienté où l'un au plus des couples (x, y) et (y, x) est un arc du graphes. 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 mixte[modifier | modifier le code]

Un graphe mixte est un graphe composé d'arêtes (donc non orientées) et d'arcs (donc orientés). Un tel graphe est un triple G = (V, E, A) avec V, E, et A comme défini plus haut. Les graphes orienté et non orienté sont des cas particuliers des graphes mixtes.

Multigraphe[modifier | modifier le code]

Article détaillé : Multigraphe.

Dans un multigraphe, orienté ou non, plusieurs arcs respectivement arêtes peuvent connecter une même paire de sommets.Selon les cas, des boucles sont ou non autorisées. Ainsi un multigraphe est la notion opposée à un graphe simple. Dans le cas général un multigraphe peut avoir des arêtes multiples et des boucles[6], même si d'autres auteurs utilisent le terme pseudograph dans ce cas[7], d'autres réservent le terme aux graphes sans boucles[8].

Graphe simple[modifier | modifier le code]

Un graphe simple est un graphe non orienté sans arêtes multiples et sans boucle. Dans un graphe simple, chaque arête est une paire de sommets distincts. On peut donc définir un graphe simple comme composé d'un ensemble V de sommets et d'un ensemble E de sous-ensembles à 2 éléments de V. Le degré d'un sommet, dans un graphe simple à n sommets, est au plus égal à n − 1.

Carquois[modifier | modifier le code]

Un carquois ou multi-digraphe est un multigraphe orienté. Un carquois peut comporter des boucles orientées. Ainsi, un carquois est composé d'un ensemble V de sommets, d'un ensemble E d'arcs, et de deux fonctions , et . La fonction s associe à chaque arc sa source (ou son origine), alors que t associe à chaque arc sa cible (ou son but).

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

Un graphe pondéré.

Un graphe pondéré est un graphe où chaque arc ou arête porte un nombre (qui est son poids)[9]. Un tel poids peut représenter un coût, une longueur ou une capacité, selon les cas. Un graphe pondéré est aussi appelé un réseau[10]. Ces graphes sont fréquents dans divers contextes, comme le problème de plus court chemin ou le problème du voyageur de commerce.

Demi-arêtes, arêtes pendantes[modifier | modifier le code]

Dans certaines situations, il peut être utile de considérer des arêtes qui n'ont qu'une seule extrémité, appelées demi-arêtes, ou arêtes pendantes; cela se produit pour un graphe signé (en) ou pour les graphes biaisés (en).

Classes principales de graphes[modifier | modifier le code]

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 arcs (un 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 arcs est connexe. Il est fortement connexe si tout couple de sommets est relie par un chemine, 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]

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

Un graphe biparti est un graphe dont l'ensemble des sommets peut être partitionné en deux ensemble X et Y de telle sorte qu'il n'y a pas d'arêtes 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 sans cycle. Une forêt est un graphe sans cycle, c'est-à-dire une union disjointe d'un ou de 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 » ; de même un graphe est étiqueté aux arcs ou aux arêtes s'ils portent des étiquettes. 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é.

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

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

Applications[modifier | modifier le code]

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

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. Par exemple (Iyanaga et Kawada 1977, p. 234) ou (Biggs 1993, p. 4).
  5. Par exemple (Graham et. al. 1995, p. 5).
  6. Par exemple : (Bollobás 2002, p. 7) et (Diestel 2005, p. 25).
  7. (Gross 1998, p. 3), (Gross et Yellen 2004, p. 205), (Harary 1995, p. 10), et (Zwillinger 2002, p. 220).
  8. For example, see (Balakrishnan et Ranganathan 2012, p. 1), (Gross et Yellen 2004, p. 4), et (Zwillinger 2002, p. 220).
  9. 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.
  10. Strang 2005.
  11. 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)
  12. 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]