Comment construire la matrice… : En numérotant les sommets et en plaçant… — ECG1 appliquées | MetMat

Comment construire la matrice d'adjacence d'un graphe (orienté ou non) ?

En numérotant les sommets et en plaçant $1$ lorsqu'une arête (ou un arc) existe, $0$ sinon

Représenter un graphe fini par sa matrice d'adjacence pour en permettre l'exploitation calculatoire.

Maîtriser

Reconnaître

Résoudre

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

Donner la matrice d'adjacence du graphe non orienté à $4$ sommets $\{1,2,3,4\}$ dont les arêtes sont $\{1,2\}$ , $\{2,3\}$ , $\{3,4\}$ et $\{1,4\}$ .

L'objectif

Représenter un graphe fini par sa matrice d'adjacence pour en permettre l'exploitation calculatoire.

Le principe

Pour un graphe $G=(S,A)$ dont les sommets sont numérotés $1,\dots,n$ , la matrice d'adjacence est $A=(a_{i,j})\in\mathcal{M}_n(\mathbb{R})$ définie par $a_{i,j}=1$ s'il existe une arête (cas non orienté) ou un arc de $i$ vers $j$ (cas orienté), et $a_{i,j}=0$ sinon ; dans le cas non orienté, $A$ est symétrique.

La méthode

1
Je numérote les sommets de $1$ à $n$ et je détermine si le graphe est orienté (arcs $i\to j$ ) ou non orienté (arêtes $\{i,j\}$ ).
2
Je construis une matrice $n\times n$ en inscrivant $a_{i,j}=1$ si l'arête $\{i,j\}$ (ou l'arc $i\to j$ ) existe, et $a_{i,j}=0$ sinon.
3
Je vérifie la cohérence : dans le cas non orienté, je contrôle que $A$ est symétrique ; dans le cas orienté, je note que $A$ n'a aucune raison d'être symétrique.

Pour comprendre, fais des exercices !

Exercice d'exemple

Donner la matrice d'adjacence du graphe non orienté à $4$ sommets $\{1,2,3,4\}$ dont les arêtes sont $\{1,2\}$ , $\{2,3\}$ , $\{3,4\}$ et $\{1,4\}$ .

Étape 1 —

Je numérote les sommets de

1

n

et je détermine si le graphe est orienté (arcs

i\to j

) ou non orienté (arêtes

\{i,j\}

Les sommets sont numérotés $1,2,3,4$ et le graphe est non orienté : la matrice sera symétrique.

Étape 2 —

Je construis une matrice

n\times n

en inscrivant

a_{i,j}=1

si l'arête

\{i,j\}

(ou l'arc

i\to j

) existe, et

a_{i,j}=0

sinon.

Je remplis $A$ avec $a_{1,2}=a_{2,1}=1$ , $a_{2,3}=a_{3,2}=1$ , $a_{3,4}=a_{4,3}=1$ , $a_{1,4}=a_{4,1}=1$ , et $0$ partout ailleurs : $A=\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$ .

Étape 3 —

Je vérifie la cohérence : dans le cas non orienté, je contrôle que

A

est symétrique ; dans le cas orienté, je note que

A

n'a aucune raison d'être symétrique.

Je vérifie que $A$ est bien symétrique ( $A^\top=A$ ) et que la diagonale est nulle (pas de boucle).

$A=\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 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 construire la matrice d'adjacence d'un graphe (orienté ou non) ?

En numérotant les sommets et en plaçant 111 lorsqu'une arête (ou un arc) existe, 000 sinon

Pour comprendre, fais des exercices !

En numérotant les sommets et en plaçant $1$ lorsqu'une arête (ou un arc) existe, $0$ sinon