Graphes : modèles et parcours

Sommets, arêtes et degrés

Un graphe possède un ensemble fini de sommets et des arêtes. Ici, il est simple et non orienté : une arête n'a pas de sens, il n'y a ni boucle ni plusieurs arêtes entre deux sommets.

Déplacer les sommets ou courber les arêtes ne change pas le graphe. Un croisement sans sommet marqué n'ajoute pas de sommet.

L'ordre est le nombre de sommets. Deux sommets sont adjacents si une arête les relie. Le degré d'un sommet est le nombre d'arêtes qui le touchent ; dans ce cadre simple, c'est aussi son nombre de voisins.

Ce graphe est d'ordre $5$. Le sommet $C$ a pour voisins $A,B,D$, donc son degré est $3$. $A$ et $D$ ne sont pas adjacents.

Graphe complet

Un graphe simple non orienté est complet si toute paire de sommets distincts est reliée par une arête.

Ce graphe complet a quatre sommets et six arêtes. Le croisement central n'est pas un sommet.

Chaînes et connexité

Une chaîne est une suite de sommets dont chaque paire consécutive est adjacente. Sa longueur compte les arêtes parcourues. Les répétitions sont autorisées et chaque traversée compte ; une chaîne réduite à un sommet a longueur zéro.

Dans le premier graphe, $A-B-C-D-E$ est une chaîne de longueur $4$, et $A-C-A-B$ de longueur $3$. En revanche, $A-D-E$ n'en est pas une, car $AD$ n'est pas une arête.

Un graphe est connexe si toute paire de sommets peut être reliée par une chaîne. Le premier graphe est connexe sans être complet.

Dans ce dernier graphe, les groupes $\{A,B,C\}$ et $\{D,E\}$ ne communiquent pas : aucune chaîne ne relie $A$ à $E$, donc le graphe n'est pas connexe.