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

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

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, passons aux 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\}$ .

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

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

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, passons aux exercices.

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