ℂ Option Mathématiques expertes Terminale Générale · Chapitre 8

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.

ABCDdegrés :A : 2 B : 3C : 3 D : 2somme = 10= 2 × 5 arêtes
Le graphe G : 4 sommets et 5 arêtes. La somme des degrés vaut deux fois le nombre d'arêtes.

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

page 1page 2page 3M³ = I
Graphe orienté : la page 1 cite la page 2, qui cite la 3, qui cite la 1. Sa matrice n'est pas symétrique.

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).

⚠️ Une erreur dans ce cours ? Signalez-la

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.

1

Ordre et degrés

★☆☆

Donner l'ordre du graphe $G$ ci-dessous, le degré de chaque sommet et vérifier le lemme des poignées de main.

ABCD
Le graphe G : sommets A, B, C, D.
🔒 Correction réservée aux membres Créer un compte gratuit →
3

Chaînes de longueur 2

★★☆

On note $M$ la matrice d'adjacence du graphe $G$ ci-dessous (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}$. Calculer $M^2$ et interpréter son coefficient $(A, D)$ et ses coefficients diagonaux.

ABCD
Le graphe G : sommets A, B, C, D.
🔒 Correction réservée aux membres Créer un compte gratuit →
17

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.

🔒 Correction réservée aux membres Créer un compte gratuit →
18

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.

🔒 Correction réservée aux membres Créer un compte gratuit →

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.