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

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

Exemple corrigé

Difficulté croissante de 1 à 3

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

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

Exemple corrigé

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