Théorie des graphes
Graphes non orientés
Vocabulaire : graphe non orienté, sommet et arêtes
- Un graphe non orienté est un ensemble fini de points, appelés sommets, et de segments, appelés arêtes, reliant certains de ces points.
- On dit que deux sommets d’un graphe non orienté sont adjacents lorsqu’ils sont reliés par une arête.
- On dit qu’un sommet est isolé lorsqu’il n’est relié à aucun autre (y compris à lui-même). Une boucle est une arête reliant un point à lui-même.
- On dit qu’un graphe non orienté est simple s’il ne possède aucune boucle et si deux sommets quelconques sont reliés par au plus une arête.
- Si \(G\) est un graphe non orienté, on appelle sous-graphe de \(G\) tout graphe non orienté dont les sommets sont des sommets de \(G\) et dont les arêtes sont des arêtes de \(G\).
A priori seuls les graphes simples sont envisagés par le programme, donc dans la suite les graphes envisagés sont tous simples.
Graphe complet
On dit qu’un graphe non orienté simple est complet si ses sommets sont tous deux à deux adjacents.
Ordre et degré d’un graphe non orienté
Définitions
a
- On appelle ordre d’un graphe le nombre total de sommets qu’il comporte.
- On appelle degré d’un sommet \(S\) le nombre total d’arêtes ayant \(S\) pour extrémité (les boucles étant comptées deux fois); le degré d’un sommet \(S\) est noté \(\operatorname{deg}(S)\).
Formule d’Euler (dite des poignées de main)
La somme des degrés des sommets d’un graphe non orienté est égale au double du nombre d’arêtes : si un graphe comporte \(n\) sommets \(A_1, \ldots, A_n\) et \(p\) arêtes alors: \[ \sum_{i=1}^n \operatorname{deg}\left(A_i\right)=2 p \]
Chaînes et cycles d’un graphe
Définitions
- Dans un graphe non orienté, une chaîne est une liste ordonnée de sommets pour laquelle chaque sommet de la liste est adjacent au sommet suivant.
- Le nombre d’arêtes composant une chaîne est appelé longueur de la chaîne.
- On dit qu’une chaîne est fermée lorsque son premier et son dernier sommets sont identiques.
- On dit qu’une chaîne est un cycle si elle est fermée et si ses arêtes sont deux à deux distinctes.
Chaînes et cycles eulériens
- On appelle chaîne eulérienne d’un graphe toute chaîne contenant toutes les arêtes du graphe exactement une fois.
- On appelle cycle eulérien toute chaîne eulérienne fermée.
- On dit qu’un graphe est eulérien s’il comporte au moins un cycle eulérien.
Graphe connexe
Définition
On dit qu’un graphe non orienté est connexe si deux sommets distincts quelconques sont toujours reliés par au moins une chaîne.
Théorème d’Euler
- Un graphe connexe est eulérien si et seulement si tous ses sommets sont de degré pair.
- Un graphe connexe possède une chaîne eulérienne si et seulement si exactement deux de ses sommets sont de degré impair ; le cas échéant, ces deux points sont le point de départ et le point d’origine de la chaîne).
Matrice d’adjacence
Définition
Soit \(G\) un graphe non orienté possédant \(n\) sommets \(S_1, \ldots, S_n\).
On appelle matrice d’adjacence de \(G\) la matrice \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant n}\) de \(\mathcal{M}_n(\mathbb{R})\) telle que \(a_{i, j}\) est égal au nombre d’arêtes joignant les sommets \(S_i\) et \(S_j\).
Propriété
La matrice d’adjacence d’un graphe non orienté est toujours une matrice symétrique.
Graphes orientés
Vocabulaire : graphe orienté, sommet, arcs
- Un graphe orienté est un ensemble fini de points, appelés sommets, et de segments, appelés arcs, reliant certains de ces points et ne pouvant être parcourus que dans un sens.
- On dit qu’un sommet \(B\) est adjacent au sommet \(A\) lorsqu’il est relié à \(A\) par un arc orienté de \(A\) vers \(B\).
- On dit qu’un sommet est isolé lorsqu’il n’est relié à aucun autre. Une boucle est un arc reliant un point à lui-même.
Degré d’un graphe orienté
Définition
- On appelle degré d’un sommet \(S\) d’un graphe orienté le nombre total d’arcs ayant \(S\) pour extrémité initiale ou finale; le degré d’un sommet \(S\) est noté \(\operatorname{deg}(S)\).
- Dans le cas d’un sommet d’un graphe orienté, on parle aussi de degré entrant, noté \(\mathrm{deg}^-(S)\), (respectivement de degré sortant, noté \(\operatorname{deg}^{+}(S)\) ) du sommet \(S\) pour parler du nombre d’arcs dirigés vers \(S\) (respectivement partant de \(S\) ); on a donc : \[ \operatorname{deg}(S)=\operatorname{deg}^-(S)+\operatorname{deg}^{+}(S) \]
Formule d’Euler (dite des poignées de main)
La somme des degrés des sommets d’un graphe orienté est égale au double du nombre d’arêtes : si un graphe comporte \(n\) sommets \(A_1, \ldots, A_n\) et \(p\) arêtes alors : \[ \sum_{i=1}^n \operatorname{deg}\left(A_i\right)=2 p \] Plus précisément, on a : \[ \sum_{i=1}^n \operatorname{deg}^{+}\left(A_i\right)=\sum_{i=1}^n \operatorname{deg}^{-}\left(A_i\right)=p \]
Chemin, chemin eulérien
- On appelle chemin eulérien d’un graphe tout chemin contenant tous les arcs du graphe exactement une fois.
- On appelle circuit (ou cycle) eulérien d’un graphe orienté tout chemin eulérien fermé.
- On dit qu’un graphe orienté est eulérien s’il comporte au moins un circuit eulérien.
Connexité d’un graphe
Soit \(G\) un graphe orienté.
- On dit que \(G\) est faiblement connexe (ou plus simplement connexe) si, pour tous sommets \(S_1\) et \(S_2\), il existe une chaine (en ne considérant pas l’orientation des arcs) allant du sommet \(S_1\) au sommet \(S_2\).
- On dit que \(G\) est fortement connexe (ou plus simplement connexe) si deux sommets distincts quelconques sont toujours reliés par au moins un chemin.