Graphe (mathématiques discrètes)

Modèle:Voir homonymes Modèle:Confusion 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.
Un graphe contenant des centaines de sommets.

Le mot Modèle:Citation étrangère a été utilisé pour la première fois dans ce sens par James Joseph Sylvester en 1878^[2]Modèle:,^[3].

Définition et vocables associés

Modèle:Article connexe

Un graphe avec trois sommets et trois arêtes.

Un graphe orienté avec trois sommets et quatre arcs.

Un graphe est un couple Modèle:Math comprenant deux ensembles :

Modèle:Math : sommets ;
Modèle:Math : arêtes, chacune étant associée à un couple Modèle:Math ou une paire Modèle:Math de sommets (Modèle:Math).

Des définitions plus restreintes pour Modèle:Math sont souvent employées :

Modèle:Math : chaque arête est une paire de sommets distincte des autres. Modèle:Math est alors un graphe simple non orienté^[4]Modèle:,^[5].
Modèle:Math : chaque arête est associée par la fonction d'incidence Modèle:Math à une paire de sommets (ou à un singleton si Modèle:Math). Modèle:Math est alors un multigraphe non orienté. Ce n'est plus un couple mais un triplet Modèle:Math^[6]Modèle:,^[7].
Modèle:Math : chaque arête est un couple distinct des autres, de deux sommets distincts l'un de l'autre. Modèle:Math est alors un graphe simple orienté. Les arêtes sont plus souvent appelées arcs, et leur ensemble Modèle:Math plutôt que Modèle:Math.
Modèle:Math, avec Modèle:Math : chaque arc est associé par la fonction d'incidence Modèle:Math à un couple de sommets. Modèle:Math est alors un multigraphe orienté (ou carquois).
Modèle:Math, avec Modèle:Math et Modèle:Math : Modèle:Math est un graphe mixte simple.
Finalement, la définition la plus générale : Modèle:Math, avec Modèle:Math et Modèle:Math. Modèle:Math est alors un multigraphe mixte.

Plus vulgairement :

Un graphe simple ne comporte ni boucles (arêtes Modèle:Math ou arcs Modèle:Math, 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.

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 de plus court chemin et le problème du voyageur de commerce.

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

L'ordre d'un graphe est son nombre de sommets (Modèle:Math). La taille d'un graphe est son nombre d'arêtes (Modèle:Math). 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 Modèle:Math, le degré maximum d'un sommet est Modèle:Math et la taille maximale du graphe est Modèle:Math.

Modèle:Math et Modèle:Math 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. Modèle:Math et Modèle:Math peuvent être vides (graphe nul, et bien entendu Modèle:Math), bien que Modèle:Math soit généralement conçu comme non vide. Si Modèle:Math et Modèle:Math, 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

Modèle:Article détaillé Un graphe asymétrique (en anglais Modèle:Citation étrangère, alors qu'un graphe orienté est appelé Modèle:Citation étrangère) est un graphe orienté où l'un au plus des couples Modèle:Math et Modèle:Math 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

Modèle:Article détaillé 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.

Modèle:Article connexe

Graphe complet

Modèle:Article détaillé

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

Modèle:Article détaillé 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 Modèle:Math de sommets, il y a un chemin de Modèle:Math à Modèle:Math et un chemin de Modèle:Math à Modèle:Math. 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

Modèle:Article détaillé

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

Modèle:Article détaillé Un graphe est une chaîne d'ordre Modèle:Math s'il est composé de sommets Modèle:Math qu'on peut numéroter de telle sorte que les arêtes sont Modèle:Math pour Modèle:Math. 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

Modèle:Article détaillé 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

Modèle:Article détaillé Un graphe cycle d'ordre $n \geq 3$ ou n-cycle est un graphe dont les sommets peuvent être numérotés $v_{1}, \dots, v_{n}$ de sorte que les arêtes sont les paires $[v_{i}, v_{i + 1}]$ pour $i = 1, \dots, 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

Modèle:Article détaillé 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é

Modèle:Article détaillé 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

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]Modèle:,^[10].
Des exemples de graphes orientés réguliers sont les graphes de Cayley de groupes finiment engendrés, ou le Modèle:Lien.
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 Modèle:Citation étrangère) 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

Modèle:Références

Annexes

Bibliographie

Ouvrages généraux

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

Ouvrages spécifiques

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

Articles connexes

Modèle:Colonnes

Liens externes

Modèle:Portail

↑ Modèle:Harvsp : Modèle:Citation étrangère
↑ Dans : Modèle:Article. Et : Modèle:Article.
↑ Modèle:Harvsp.
↑ Modèle:Ouvrage
↑ Par exemple Modèle:Harv ou Modèle:Harv.
↑ Modèle:Ouvrage
↑ Par exemple Modèle:Harv.
↑ Modèle:Article.
↑ Modèle:Article
↑ 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. Modèle:Doi.

[1] Modèle:Harvsp : Modèle:Citation étrangère

[2] Dans : Modèle:Article. Et : Modèle:Article.

[3] Modèle:Harvsp.

[4] Modèle:Ouvrage

[5] Par exemple Modèle:Harv ou Modèle:Harv.

[B&W-6] Modèle:Ouvrage

[GGL_p5-7] Par exemple Modèle:Harv.

[8] Modèle:Article.

[snatwitter-9] Modèle:Article

[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. Modèle:Doi.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Graphe (mathématiques discrètes)

Sommaire

Définition et vocables associés