Matrice d'adjacence et nombre de chemins

Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

À propos de cette leçon

Terminale, mathématiques expertes › Graphes et matrices

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits

Matrice d'adjacence et nombre de chemins

Graphes et matrices. graphe, matrice, matrice d'adjacence, inverse, système linéaire

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Combien d'arêtes le graphe complet d'ordre 3 a-t-il ?
  2. Un graphe a 3 arêtes. Quelle est la somme des degrés de ses sommets ?
  3. Dans un graphe complet d'ordre 5, quel est le degré de chaque sommet ?

Découvrir

AA est la matrice d'adjacence d'un graphe. Que signifie aij=1a_{ij} = 1 ?

  1. Il y a une arête de ii vers jj
  2. Le sommet ii a pour degré 1

L'idée clé

Les puissances de AA comptent les chemins.

La matrice d'adjacence AA a pour coefficient aij=1a_{ij} = 1 s'il existe une arête de ii vers jj, 0 sinon.

Le coefficient (i;j)(i ; j) de AnA^n est le nombre de chemins de longueur nn reliant ii à jj.

Exemple corrigé

A=(0111)A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}. Combien de chemins de longueur 2 vont de 2 à 2 ?

A2=(1112)A^2 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}
Calcul de A².
22 chemins
Coefficient (2 ; 2).

À toi, guidé

À toi : avec le même A2A^2, combien de chemins de longueur 2 vont de 1 à 1 ?

11
Coefficient (1 ; 1).

Entraînement ★

  1. Pour un graphe, A3=(5269)A^3 = \begin{pmatrix} 5 & 2 \\ 6 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  2. Pour un graphe, A3=(3511)A^3 = \begin{pmatrix} 3 & 5 \\ 1 & 1 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  3. Pour un graphe, A3=(7259)A^3 = \begin{pmatrix} 7 & 2 \\ 5 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?

Attention !

Entraînement ★★

  1. A=(0110)A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. Que vaut le coefficient (1;1)(1 ; 1) de A2A^2 ?
  2. A=(0120)A = \begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix}. Que vaut le coefficient (1;1)(1 ; 1) de A2A^2 ?
  1. A=(0310)A = \begin{pmatrix} 0 & 3 \\ 1 & 0 \end{pmatrix} compte les arêtes de chaque sommet vers chaque sommet. Combien d'arêtes vont du sommet 1 au sommet 2 ?
  1. La matrice d'adjacence d'un graphe non orienté est toujours :
    1. Symétrique
    2. Diagonale
    3. Inversible

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Pour un graphe, A3=(5269)A^3 = \begin{pmatrix} 5 & 2 \\ 6 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  2. Pour un graphe, A3=(3511)A^3 = \begin{pmatrix} 3 & 5 \\ 1 & 1 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  3. Pour un graphe, A3=(7259)A^3 = \begin{pmatrix} 7 & 2 \\ 5 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?

Fiche résumé

Chemins

  • Coefficient (i;j)(i ; j) de AnA^n : chemins de longueur nn de ii à jj.
  • Graphe non orienté : AA est symétrique.

Attention : la puissance est la longueur.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Un graphe est un triangle (3 sommets, tous reliés). Combien de chemins de longueur 2 partent du sommet 1 et y reviennent ?
Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits