Comment modéliser une situation… : En construisant la matrice d'adjacence A… — maths expertes | MetMat

Comment modéliser une situation par un graphe et en extraire des informations ?

En construisant la matrice d'adjacence $A$ : $A_{ij} = 1$ si les sommets $i$ et $j$ sont reliés, $0$ sinon

Traduire un graphe en matrice d'adjacence et exploiter cette représentation.

Maîtriser

Reconnaître

Résoudre

Que ferais-tu face à un exercice de ce type ?

Graphe à 3 sommets avec arêtes $\{1,2\}$ et $\{2,3\}$ . Écrire la matrice d'adjacence.

L'objectif

Traduire un graphe en matrice d'adjacence et exploiter cette représentation.

Le principe

La matrice d'adjacence $A$ d'un graphe à $n$ sommets est une matrice $n \times n$ telle que $A_{ij}=1$ si $\{i,j\}$ est une arête et $A_{ij}=0$ sinon ; le coefficient $(A^k)_{ij}$ compte le nombre de chemins de longueur $k$ de $i$ à $j$ .

La méthode

1
Numéroter les sommets de $1$ à $n$ et créer une matrice $n \times n$ initialisée à $0$ .
2
Pour chaque arête $\{i,j\}$ , poser $A_{ij} = 1$ et $A_{ji} = 1$ (matrice symétrique pour un graphe non orienté).
3
Vérifier que la somme de chaque ligne $i$ est égale à $d(i)$ , le degré du sommet $i$ .

Pour comprendre, fais des exercices !

Exercice d'exemple

Graphe à 3 sommets avec arêtes $\{1,2\}$ et $\{2,3\}$ . Écrire la matrice d'adjacence.

Étape 1 —

Numéroter les sommets de

1

n

et créer une matrice

n \times n

initialisée à

0

Sommets $1, 2, 3$ ; matrice $3 \times 3$ initialisée à $0$ .

Étape 2 —

Pour chaque arête

\{i,j\}

, poser

A_{ij} = 1

A_{ji} = 1

(matrice symétrique pour un graphe non orienté).

Arête $\{1,2\}$ : $A_{12}=A_{21}=1$ . Arête $\{2,3\}$ : $A_{23}=A_{32}=1$ .

Étape 3 —

Vérifier que la somme de chaque ligne

i

est égale à

d(i)

, le degré du sommet

i

Somme ligne 1 : $1$ ; ligne 2 : $2$ ; ligne 3 : $1$ . On a bien $d(1)=1$ , $d(2)=2$ , $d(3)=1$ . ✓

$A = \begin{pmatrix}0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0\end{pmatrix}$

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

Comment modéliser une situation par un graphe et en extraire des informations ?

En construisant la matrice d'adjacence AAA : Aij=1A_{ij} = 1Aij​=1 si les sommets iii et jjj sont reliés, 000 sinon

Pour comprendre, fais des exercices !

En construisant la matrice d'adjacence $A$ : $A_{ij} = 1$ si les sommets $i$ et $j$ sont reliés, $0$ sinon