Matrice d'adjacence et nombre de chemins

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

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

Les puissances de $A$ comptent les chemins.

La matrice d'adjacence $A$ a pour coefficient $a_{ij} = 1$ s'il existe une arête de $i$ vers $j$ , 0 sinon.

Le coefficient $(i ; j)$ de $A^n$ est le nombre de chemins de longueur $n$ reliant $i$ à $j$ .

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

A^2 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}

Calcul de A².

2

chemins

Coefficient (2 ; 2).

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

1

Coefficient (1 ; 1).

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

$A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ . Que vaut le coefficient $(1 ; 1)$ de $A^2$ ?
$A = \begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix}$ . Que vaut le coefficient $(1 ; 1)$ de $A^2$ ?

$A = \begin{pmatrix} 0 & 5 \\ 2 & 0 \end{pmatrix}$ compte les arêtes de chaque sommet vers chaque sommet. Combien d'arêtes vont du sommet 1 au sommet 2 ?

La matrice d'adjacence d'un graphe non orienté est toujours :
1. Symétrique
2. Diagonale
3. Inversible

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

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

Chemins

Attention : la puissance est la longueur.

À propos de cette leçon