Étape 1
Pour déterminer la matrice d'adjacence $M = (a_{i,j})_{1 \le i,j \le 4}$ du graphe orienté $G$, on recense les arcs sortant de chaque sommet $i$ vers le sommet $j$ :
Étape 2
Pour le sommet $1$, les arcs orientés vont vers $2$ et $4$. La première ligne de $M$ est donc $(0, 1, 0, 1)$.
Étape 3
Pour le sommet $2$, l'unique arc orienté va vers $3$. La deuxième ligne de $M$ est donc $(0, 0, 1, 0)$.
Étape 4
Pour le sommet $3$, les arcs orientés vont vers $1$ et $4$. La troisième ligne de $M$ est donc $(1, 0, 0, 1)$.
Étape 5
Pour le sommet $4$, l'unique arc orienté va vers $2$. La quatrième ligne de $M$ est donc $(0, 1, 0, 0)$.
Étape 6
On obtient ainsi la matrice d'adjacence suivante :$$M = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$
Étape 7
On calcule le paramètre $k = \sum_{i=1}^4 \sum_{j=1}^4 i \times j \times a_{i,j}$. Seuls les couples $(i,j)$ pour lesquels $a_{i,j} = 1$ interviennent dans la somme :
Étape 8
Pour $(1,2)$ : $1 \times 2 \times 1 = 2$
Étape 9
Pour $(1,4)$ : $1 \times 4 \times 1 = 4$
Étape 10
Pour $(2,3)$ : $2 \times 3 \times 1 = 6$
Étape 11
Pour $(3,1)$ : $3 \times 1 \times 1 = 3$
Étape 12
Pour $(3,4)$ : $3 \times 4 \times 1 = 12$
Étape 13
Pour $(4,2)$ : $4 \times 2 \times 1 = 8$
Étape 14
En additionnant ces contributions, on obtient :$$k = 2 + 4 + 6 + 3 + 12 + 8 = 35$$
Méthode clé
Pour un graphe orienté, le coefficient $a_{i,j}$ vaut $1$ s'il existe un arc orienté du sommet $i$ vers le sommet $j$, et $0$ sinon.
Piège à éviter
Inverser les lignes et les colonnes : la ligne $i$ désigne le sommet de départ et la colonne $j$ le sommet d'arrivée.
