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) : . 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 a été utilisé pour la première fois dans ce sens par James Joseph Sylvester en 1878Dans : . Et : ...

Définition et vocables associés

vignette|Un graphe avec trois sommets et trois arêtes.|150x150px vignette|Un graphe orienté avec trois sommets et quatre arcs.|150x150px Un graphe est un couple comprenant deux ensembles : : sommets ; : arêtes, chacune étant associée à un couple ou une paire de sommets ().

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

: chaque arête est une paire de sommets distincte des autres. est alors un graphe simple non orientéPar exemple ou .. : chaque arête est associée par la fonction d'incidence à une paire de sommets (ou à un singleton si ). est alors un multigraphe non orienté. Ce n'est plus un couple mais un triplet Par exemple .. : chaque arête est un couple distinct des autres, de deux sommets distincts l'un de l'autre. est alors un graphe simple orienté. Les arêtes sont plus souvent appelées arcs, et leur ensemble plutôt que . , avec : chaque arc est associé par la fonction d'incidence à un couple de sommets. est alors un multigraphe orienté (ou carquois). , avec et : est un graphe mixte simple. Finalement, la définition la plus générale : , avec et . est alors un multigraphe mixte. Plus vulgairement : Un graphe simple ne comporte ni boucles (arêtes ou arcs , 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.

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

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

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

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

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

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

vignette|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

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 de sommets, il y a un chemin de à et un chemin de à . 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

vignette|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

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

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

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

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é

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..

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 vignette|upright=1.2|Le graphe de Cayley du groupe libre sur a et b. thumb|upright=0.8|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. En traitement des informations géospatiales, les graphes constituent le fondement des algorithmes de suggestion d’itinéraires, notamment à travers des méthodes comme l’algorithme de Dijkstra ou l'algorithme A*. 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 TwitterPankaj 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. .. Des exemples de graphes orientés réguliers sont les graphes de Cayley de groupes finiment engendrés, ou le . 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 ) 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.