Théorie des graphes — sommets, arêtes et notions de base

La théorie des graphes est l’étude des graphes, c’est-à-dire des structures formées de sommets et d’arêtes. Un sommet est un objet, et une arête représente une relation entre deux objets.

Si vous cherchez les bases de la théorie des graphes, partez de cette idée : un graphe est une manière simple de modéliser des connexions. Des personnes dans un réseau social, des villes reliées par des routes et des pages web liées entre elles peuvent toutes être représentées par des graphes.

Ce que signifie un graphe en mathématiques

Dans un graphe non orienté, une arête indique que deux sommets sont reliés, et cette relation n’a pas de direction. Si $A$ est relié à $B$, alors $B$ est aussi relié à $A$.

Dans un graphe orienté, les arêtes ont une direction, donc $A \to B$ et $B \to A$ sont deux affirmations différentes. Beaucoup d’exemples d’introduction utilisent des graphes simples non orientés, c’est-à-dire sans boucle et sans arêtes répétées entre les mêmes deux sommets.

Cette condition est importante, car les définitions sont souvent introduites d’abord dans le cadre simple et non orienté. Si le type de graphe change, le sens des termes peut changer lui aussi.

Les termes de base en théorie des graphes à connaître d’abord

Sommets et arêtes

Un sommet est l’objet que vous voulez suivre. Une arête est la connexion que vous voulez suivre.

Si un graphe modélise des villes et des routes, les villes sont les sommets et les routes sont les arêtes.

Degré

Dans un graphe non orienté, le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes.

Si une ville a des routes vers trois autres villes, son degré est $3$.

Chemin

Un chemin est une suite de sommets dans laquelle chaque paire consécutive est reliée par une arête.

S’il existe un chemin d’un sommet à un autre, on peut aller de l’un à l’autre en suivant les arêtes.

Cycle

Un cycle est un chemin qui commence et se termine au même sommet. Dans la définition de base habituelle, aucun autre sommet n’est répété.

Un cycle montre qu’il existe une boucle fermée dans le graphe.

Graphe connexe et composantes connexes

Un graphe non orienté est connexe si chaque sommet peut être atteint depuis n’importe quel autre par un certain chemin.

Si ce n’est pas le cas, le graphe se décompose en composantes connexes. Chaque composante est une partie connexe du graphe.

Exemple détaillé : un petit graphe

Supposons qu’un graphe ait pour sommets $A$, $B$, $C$, $D$ et $E$, avec les arêtes

$$AB,\ AC,\ BC,\ CD$$

On obtient ainsi un triangle sur $A$, $B$ et $C$, une arête supplémentaire de $C$ à $D$, et un sommet isolé $E$.

Les idées principales deviennent alors faciles à voir.

Les degrés sont

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Il existe un chemin de $A$ à $D$ :

$$A-C-D$$

Il existe un cycle :

$$A-B-C-A$$

Le graphe n’est pas connexe parce que $E$ ne peut pas être atteint depuis les autres sommets. Le graphe a donc deux composantes connexes : l’une contenant $A,B,C,D$ et l’autre contenant seulement $E$.

Cet exemple unique montre comment le degré, le chemin, le cycle, les sommets isolés et les composantes connexes s’articulent.

Vérification rapide : somme des degrés

Pour tout graphe fini non orienté,

$$\sum \deg(v) = 2|E|$$

Cela fonctionne parce que chaque arête touche exactement deux extrémités, donc chaque arête ajoute $1$ à deux comptes de degré.

Dans l’exemple ci-dessus, la somme des degrés vaut

$$2+2+3+1+0=8$$

et le nombre d’arêtes est $4$, donc

$$2|E| = 2 \cdot 4 = 8$$

C’est une vérification utile quand vous comptez les degrés à la main. Si les nombres ne coïncident pas, il y a une erreur.

Erreurs fréquentes en théorie des graphes

Confondre sommets et arêtes

Les sommets sont les objets. Les arêtes sont les relations entre eux.

Oublier quel type de graphe on étudie

Une affirmation vraie pour un graphe simple non orienté peut devoir être modifiée pour un graphe orienté ou pour un graphe qui autorise des boucles.

Prendre un chemin pour un cycle

Un chemin n’a pas besoin de revenir à son point de départ. Un cycle, si.

Ignorer les sommets isolés

Un sommet de degré $0$ fait toujours partie du graphe. Il peut changer le fait que le graphe soit connexe ou non.

Où les bases de la théorie des graphes sont utilisées

Ces idées apparaissent dans les réseaux informatiques, la planification d’itinéraires, l’ordonnancement, les systèmes de recommandation et les réseaux sociaux. Le contexte change, mais les mêmes questions reviennent : qu’est-ce qui est relié, qu’est-ce qui peut être atteint, et où sont les boucles ?

C’est pourquoi la théorie des graphes apparaît tôt à la fois en mathématiques discrètes et en informatique.

Essayez un graphe similaire

Dessinez quatre sommets $P$, $Q$, $R$ et $S$. Ajoutez les arêtes $PQ$, $QR$, $RS$ et $SP$.

Répondez ensuite à trois questions : quel est le degré de chaque sommet, le graphe est-il connexe, et contient-il un cycle ?