Graphes et matrices d'adjacence
Graphes non orientés et orientés : sommets, arêtes, degrés, chaînes, cycles, connexité, graphes complets ; matrice d'adjacence et dénombrement des chaînes de longueur n par les puissances de la matrice.
1. Vocabulaire des graphes
Définition · Graphe
Un graphe (non orienté) est formé de sommets reliés par des arêtes. L'ordre est le nombre de sommets ; le degré d'un sommet est le nombre d'arêtes qui en partent. Deux sommets reliés sont dits adjacents.
Propriété · Lemme des poignées de main
La somme des degrés de tous les sommets est égale au double du nombre d'arêtes. Conséquence : le nombre de sommets de degré impair est toujours pair.
Définition · Chaîne, cycle, connexité
Une chaîne est une suite de sommets dont deux consécutifs sont adjacents ; sa longueur est son nombre d'arêtes. Un cycle est une chaîne fermée dont les arêtes sont distinctes. Un graphe est connexe si deux sommets quelconques sont reliés par une chaîne. Un graphe est complet si tous ses sommets sont adjacents deux à deux.
2. Matrice d'adjacence
Définition · Matrice d'adjacence
Pour un graphe d'ordre $n$ dont les sommets sont numérotés, la matrice d'adjacence $M$ est la matrice $n \times n$ dont le coefficient $m_{ij}$ vaut $1$ si les sommets $i$ et $j$ sont reliés, $0$ sinon. Pour un graphe non orienté, $M$ est symétrique.
Exemple · Le graphe G (ordre A, B, C, D)
$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$ et $M^2 = \begin{pmatrix} 2 & 1 & 1 & 2 \\ 1 & 3 & 2 & 1 \\ 1 & 2 & 3 & 1 \\ 2 & 1 & 1 & 2 \end{pmatrix}$.
Propriété · Nombre de chaînes
Le coefficient $(i, j)$ de $M^n$ est le nombre de chaînes (ou de chemins, pour un graphe orienté) de longueur $n$ allant du sommet $i$ au sommet $j$.
Dans $G$, le coefficient $(A, D)$ de $M^2$ vaut $2$ : il y a deux chaînes de longueur $2$ de $A$ à $D$, à savoir $A - B - D$ et $A - C - D$.
3. Graphes orientés
Méthode · Chaîne eulérienne
Une chaîne qui emprunte chaque arête exactement une fois est dite eulérienne. Un graphe connexe en possède une si et seulement s'il a $0$ ou $2$ sommets de degré impair (théorème d'Euler).
S'entraîner
Exercices corrigés
🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.
Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.
Ordre et degrés
★☆☆Donner l'ordre du graphe $G$ du cours, le degré de chaque sommet et vérifier le lemme des poignées de main.
Matrice d'adjacence
★☆☆Écrire la matrice d'adjacence de $G$ (ordre $A, B, C, D$).
Chaînes de longueur 2
★★☆Calculer $M^2$ et interpréter son coefficient $(A, D)$ et ses coefficients diagonaux.
Chaînes de longueur 3
★★★Combien de chaînes de longueur $3$ relient $A$ à $D$ dans $G$ ? Les écrire.
Graphe complet
★☆☆Combien d'arêtes possède le graphe complet à $5$ sommets ?
Poignées de main
★☆☆Six personnes se serrent la main deux à deux, une fois chacune. Combien de poignées de main ?
Graphe impossible
★★☆Peut-il exister un graphe à $5$ sommets tous de degré $3$ ?
Connexité
★☆☆Le graphe $G$ est-il connexe ?
Chaîne eulérienne
★★☆Le graphe $G$ admet-il une chaîne eulérienne ? Si oui, en donner une.
Cycle
★☆☆Donner un cycle de longueur $3$ dans $G$.
Distance
★☆☆Quelle est la distance entre $A$ et $D$ (longueur de la plus courte chaîne) ?
Graphe orienté en cycle
★★☆Écrire la matrice $M$ du graphe orienté des trois pages ($1 \to 2$, $2 \to 3$, $3 \to 1$), puis calculer $M^3$ et l'interpréter.
Lire une matrice
★★☆Un graphe non orienté a pour matrice $\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$. Le décrire.
Nombre de sommets impairs
★★★Démontrer que, dans tout graphe, le nombre de sommets de degré impair est pair.
Graphe complet K4
★★☆Écrire la matrice $M$ du graphe complet à $4$ sommets et donner les coefficients diagonaux de $M^2$.
Degrés en Python
★★☆Avec une matrice d'adjacence M (liste de listes), écrire une instruction Python donnant la liste des degrés.
Réseau social
★★☆Dans un réseau, Ali est ami avec Bea et Chloé, Bea avec Chloé et Dan, Chloé avec Dan. Modéliser par un graphe et dire combien d'amitiés il y a.
Chemins orientés de longueur 2
★★☆Un graphe orienté a pour matrice $M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$. Calculer $M^2$ et l'interpréter.
Ordre et taille
★☆☆Un graphe a $7$ sommets de degré $2$. Combien a-t-il d'arêtes ?
Symétrie
★☆☆Pourquoi la matrice d'adjacence d'un graphe non orienté est-elle symétrique ?
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.