Comment modéliser une situation par un graphe et en extraire des informations ? | 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.

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 !

0/5 validés

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

Application guidée

Graphe complet $K_3$ à 3 sommets (tous reliés entre eux). Écrire $A$ .

Application autonome 1

Graphe à 4 sommets avec arêtes $\{1,2\}$ , $\{1,3\}$ , $\{2,4\}$ , $\{3,4\}$ . Écrire $A$ et vérifier les degrés.

Application autonome 2

Graphe à 5 sommets avec arêtes $\{1,2\}$ , $\{2,3\}$ , $\{3,4\}$ , $\{4,5\}$ (chaîne). Écrire la matrice d'adjacence $A$ .

Application autonome 3

Graphe biparti $K_{2,3}$ : sommets $\{1,2\}$ reliés à chacun des sommets $\{3,4,5\}$ (aucune arête à l'intérieur des deux classes). Écrire $A$ .

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

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