Comment construire la matrice d'adjacence d'un graphe (orienté ou non) ? | 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.

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 !

0/5 validés

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}$ .

Application guidée

Donner la matrice d'adjacence du graphe orienté à $3$ sommets dont les arcs sont $1\to 2$ , $2\to 3$ et $3\to 1$ (triangle orienté).

Application autonome 1

Soit le graphe non orienté à $5$ sommets dont les arêtes sont $\{1,2\}$ , $\{2,3\}$ , $\{3,4\}$ , $\{4,5\}$ , $\{5,1\}$ et $\{1,3\}$ (graphe eulérien : on cherchera plus loin à le parcourir). Donner sa matrice d'adjacence.

Application autonome 2

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

Application autonome 3

Donner la matrice d'adjacence du graphe orienté à $4$ sommets dont les arcs sont $1\to 2$ , $2\to 3$ , $2\to 4$ , $4\to 1$ , $4\to 3$ .

Crée ton compte pour accéder à la fiche et aux exercices

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