Les définitions en théorie des graphes varient. Voici quelques-unes des manières les plus fondamentales de définir les graphes et les structures mathématiques associées.
GraphEdit
Un graphe (parfois appelé graphe non dirigé pour le distinguer d’un graphe dirigé, ou graphe simple pour le distinguer d’un multigraphe) est un couple G = (V, E), où V est un ensemble dont les éléments sont appelés sommets (singulier : vertex), et E est un ensemble de sommets appariés, dont les éléments sont appelés arêtes (parfois liens ou lignes).
Les sommets x et y d’une arête {x, y} sont appelés les points d’extrémité de l’arête. On dit que l’arête joint x et y et qu’elle est incidente sur x et y. Un sommet peut n’appartenir à aucune arête, auquel cas il n’est joint à aucun autre sommet.
Un multigraphe est une généralisation qui permet à plusieurs arêtes d’avoir la même paire de points d’extrémité. Dans certains textes, les multigraphes sont simplement appelés graphes.
Parfois, les graphes sont autorisés à contenir des boucles, qui sont des arêtes qui joignent un sommet à lui-même. Pour autoriser les boucles, la définition ci-dessus doit être modifiée en définissant les arêtes comme des multisets de deux sommets au lieu de deux ensembles. De tels graphes généralisés sont appelés graphes avec boucles ou simplement graphes lorsqu’il est clair d’après le contexte que les boucles sont autorisées.
Généralement, l’ensemble des sommets V est supposé être fini ; cela implique que l’ensemble des arêtes est également fini. Les graphes infinis sont parfois considérés, mais sont plus souvent vus comme un type spécial de relation binaire, car la plupart des résultats sur les graphes finis ne s’étendent pas au cas infini, ou nécessitent une preuve assez différente.
Un graphe vide est un graphe qui a un ensemble vide de sommets (et donc un ensemble vide d’arêtes). L’ordre d’un graphe est son nombre de sommets |V|. La taille d’un graphe est son nombre d’arêtes |E|. Cependant, dans certains contextes, comme pour exprimer la complexité computationnelle des algorithmes, la taille est |V| + |E| (sinon, un graphe non vide pourrait avoir une taille 0). Le degré ou la valence d’un sommet est le nombre d’arêtes qui lui sont incidentes ; pour les graphes avec boucles, une boucle est comptée deux fois.
Dans un graphe d’ordre n, le degré maximal de chaque sommet est n – 1 (ou n si les boucles sont autorisées), et le nombre maximal d’arêtes est n(n – 1)/2 (ou n(n + 1)/2 si les boucles sont autorisées).
Les arêtes d’un graphe définissent une relation symétrique sur les sommets, appelée relation d’adjacence. Plus précisément, deux sommets x et y sont adjacents si {x, y} est une arête. Un graphe peut être entièrement spécifié par sa matrice d’adjacence A, qui est une matrice n × n {\displaystyle n\times n}.
matrice carrée, avec Aij spécifiant le nombre de connexions du sommet i au sommet j. Pour un graphe simple, A i j ∈ { 0 , 1 } {\displaystyle A_{ij}\in \{0,1\}.
, indiquant respectivement la déconnexion ou la connexion, tandis que A i i = 0 {\displaystyle A_{ii}=0}
(c’est-à-dire qu’une arête ne peut pas commencer et finir au même vertice). Les graphes avec auto-boucles seront caractérisés par certains ou tous les A i i {\displaystyle A_{ii}}.
étant égal à un entier positif, et les multigraphes (avec plusieurs arêtes entre les sommets) seront caractérisés par certains ou tous les A i j {\displaystyle A_{ij}}.
étant égal à un nombre entier positif. Les graphes non orientés auront une matrice d’adjacence symétrique ( A i j = A j i {\displaystyle A_{ij}}=A_{ji}}.
).
Graphes dirigés
Un graphe dirigé ou digraphe est un graphe dans lequel les arêtes ont des orientations.
Dans un sens restreint mais très courant du terme, un graphe dirigé est une paire G = ( V , E ) {\displaystyle G=(V,E)}.
comprenant :
- V {\displaystyle V}
, un ensemble de sommets (également appelés nœuds ou points) ;
- E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 et x ≠ y }. {\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {et}\;x\neq y\}}
, un ensemble d’arêtes (aussi appelées arêtes dirigées, liens dirigés, lignes dirigées, flèches ou arcs) qui sont des paires ordonnées de sommets (c’est-à-dire qu’une arête est associée à deux sommets distincts).
Pour éviter toute ambiguïté, ce type d’objet peut être appelé précisément un graphe simple dirigé.
Dans l’arête ( x , y ) {\displaystyle (x,y)}
dirigée de x {\displaystyle x}
à y {\displaystyle y}.
, les sommets x {\displaystyle x}
et y {\displaystyle y}
sont appelés les extrémités de l’arête, x {\displaystyle x}
la queue de l’arête et y {\displaystyle y}.
la tête de l’arête. On dit que l’arête joint x {\displaystyle x}
et y {\displaystyle y}.
et être incident sur x {\displaystyle x}
et sur y {\displaystyle y}
. Un sommet peut exister dans un graphe et ne pas appartenir à une arête. L’arête ( y , x ) {\displaystyle (y,x)}
est appelée l’arête inversée de ( x , y ) {\displaystyle (x,y)}.
. Les arêtes multiples, non autorisées par la définition ci-dessus, sont deux ou plusieurs arêtes ayant à la fois la même queue et la même tête.
Dans un sens plus général du terme permettant les arêtes multiples, un graphe dirigé est un triplet ordonné G = ( V , E , ϕ ) {\displaystyle G=(V,E,\phi )}.
comprenant :
- V {\displaystyle V}
, un ensemble de sommets (également appelés nœuds ou points) ;
- E {\displaystyle E}
, un ensemble d’arêtes (aussi appelées arêtes dirigées, liens dirigés, lignes dirigées, flèches ou arcs);
- ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 et x ≠ y }. {\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {et}};x\neq y\}}
, une fonction d’incidence faisant correspondre chaque arête à une paire ordonnée de sommets (c’est-à-dire qu’une arête est associée à deux sommets distincts).
Pour éviter toute ambiguïté, ce type d’objet peut être appelé précisément un multigraphe dirigé.
Une boucle est une arête qui joint un sommet à elle-même. Les graphes dirigés tels que définis dans les deux définitions ci-dessus ne peuvent pas avoir de boucles, car une boucle joignant un sommet x {\displaystyle x}
à elle-même est l’arête (pour un graphe simple dirigé) ou est incidente sur (pour un multigraphe dirigé) ( x , x ) {\displaystyle (x,x)}.
qui n’est pas dans ( ( x , y ) ∣ ( x , y ) ∈ V 2 et x ≠ y }. {\displaystyle \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {et}};x\neq y\}}
. Ainsi, pour permettre les boucles, les définitions doivent être étendues. Pour les graphes simples dirigés, la définition de E {\displaystyle E}
doit être modifiée en E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 }. {\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}}
. Pour les multigraphes dirigés, la définition de ϕ {\displaystyle \phi }.
doit être modifiée en ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 }. {\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}}
. Pour éviter toute ambiguïté, ces types d’objets peuvent être appelés précisément respectivement un graphe simple dirigé permettant des boucles et un multigraphe dirigé permettant des boucles (ou un carquois).
Les arêtes d’un graphe simple dirigé permettant des boucles G {\displaystyle G}.
est une relation homogène ~ sur les sommets de G {\displaystyle G}.
que l’on appelle la relation d’adjacence de G {\displaystyle G}.
. Plus précisément, pour chaque arête ( x , y ) {\displaystyle (x,y)}
, ses points d’extrémité x {\displaystyle x}
et y {\displaystyle y}.
sont dits adjacents l’un à l’autre, ce qui est noté x {\displaystyle x}
~ y {\displaystyle y}.
.
Graphe mixte
Un graphe mixte est un graphe dans lequel certaines arêtes peuvent être dirigées et d’autres non dirigées. C’est un triplet ordonné G = (V, E, A) pour un graphe simple mixte et G = (V, E, A, ϕE, ϕA) pour un multigraphe mixte avec V, E (les arêtes non dirigées), A (les arêtes dirigées), ϕE et ϕA définis comme ci-dessus. Les graphes dirigés et non dirigés sont des cas particuliers.
Graphes pondérésEdit
Un graphe pondéré ou un réseau est un graphe dans lequel un nombre (le poids) est attribué à chaque arête. Ces poids peuvent représenter par exemple des coûts, des longueurs ou des capacités, en fonction du problème à résoudre. De tels graphes apparaissent dans de nombreux contextes, par exemple dans les problèmes de plus court chemin comme le problème du voyageur de commerce.