Matiko Logo

6 ex.

Difficulté :
L'essentiel du cours (2 notions)

Matrice d'adjacence d'un graphe

Définition : Matrice carrée $M = (m_{i,j})$ de taille $n \times n$ où $m_{i,j}$ est le nombre d'arêtes (ou d'arcs) allant du sommet $i$ au sommet $j$.

Méthode : 1. Numéroter les sommets de $1$ à $n$. 2. Placer en ligne $i$ et colonne $j$ le nombre d'arêtes reliant $i$ à $j$.

Exemple : Pour un graphe à $3$ sommets où $1$ est relié uniquement à $2$ et $3$, la ligne 1 vaut $[0, 1, 1]$.

Nombre de chemins et matrice $M^n$

Propriété : Le coefficient $(i, j)$ de la matrice $M^n$ donne le nombre de chemins de longueur $n$ reliant le sommet $i$ au sommet $j$.

Méthode : 1. Poser la matrice d'adjacence $M$. 2. Calculer la puissance matricielle $M^n$. 3. Lire le coefficient en ligne $i$ et colonne $j$.

★ Standard

On considère un graphe orienté $G$ dont les sommets sont numérotés $1$, $2$, $3$ et $4$, représenté ci-dessous.

Soit $M = (a_{i,j})_{1 \le i,j \le 4}$ sa matrice d'adjacence, où la ligne $i$ et la colonne $j$ correspondent respectivement aux sommets $i$ et $j$.

En déterminant la matrice d'adjacence $M$, calculer la valeur exacte du paramètre $k$ défini par :

$$k = \sum_{i=1}^4 \sum_{j=1}^4 i \times j \times a_{i,j}$$

Saisir la valeur de $k$ :
★ Standard

Soit $G$ un graphe orienté dont les sommets sont notés $S_1$, $S_2$ et $S_3$. La matrice d'adjacence associée à ce graphe est :

$$M = \begin{pmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \\ 1 & k & 0 \end{pmatrix}$$

où $k$ est un entier naturel inconnu.

On souhaite déterminer la valeur de $k$ sachant qu'il existe exactement $18$ chemins de longueur $3$ reliant le sommet $S_1$ au sommet $S_3$.

  1. Déterminer la première ligne de la matrice $M^2$ en fonction de $k$.
  2. En déduire l'expression, en fonction de $k$, du nombre de chemins de longueur $3$ reliant le sommet $S_1$ au sommet $S_3$.
  3. Déterminer la valeur de $k$.

Saisir la valeur de $k$.
★ Standard

On considère un graphe non orienté à $3$ sommets numérotés $1$, $2$ et $3$, dont la matrice d'adjacence est notée $M$ :

$$M = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

D'après le cours, pour tout entier naturel $n \ge 1$, le coefficient situé sur la ligne $i$ et la colonne $j$ de la matrice $M^n$ est égal au nombre de chemins de longueur $n$ reliant le sommet $i$ au sommet $j$.

On cherche à déterminer la plus petite longueur $n \ge 1$ telle qu'il existe au moins $16$ chemins de longueur $n$ reliant le sommet $1$ à lui-même.

Pour cela, on pourra calculer la matrice $M^2$, puis exprimer $M^3$ en fonction de la matrice $M$.

Déterminer la plus petite valeur de l'entier naturel non nul $n$ vérifiant cette condition.
★★ Avancé

On considère un graphe orienté dont les quatre sommets sont notés $S_1$, $S_2$, $S_3$ et $S_4$. Les connexions directes entre ces sommets sont codées par la matrice $M$ suivante :

$$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$$

Par une justification théorique rigoureuse, déterminer la plus petite longueur $n \in \mathbb{N}^*$ pour laquelle il existe au moins $5$ chemins distincts de cette longueur reliant le sommet $S_1$ au sommet $S_2$.

Saisir la valeur de la longueur minimale $n$.
★★ Avancé

On considère le graphe orienté ci-dessous, dont les sommets sont notés $A$, $B$ et $C$.

On s'intéresse aux chemins orientés débutant au sommet $B$ et se terminant au sommet $A$.

Déterminer la longueur $n$ (avec $n \ge 1$) pour laquelle il existe exactement 4 chemins distincts reliant $B$ à $A$.

Saisir la valeur de $n$.
★★ Avancé

On considère un graphe orienté dont les sommets sont numérotés 1, 2, 3 et 4. Sa matrice d'adjacence est notée $M$ :

$$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 2 \\ k & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}$$

où $k$ désigne un entier naturel non nul.

On sait qu'il existe exactement 23 chemins de longueur 3 reliant le sommet 3 au sommet 4.

Saisir la valeur de l'entier $k$.