Déterminer les degrés sortants et entrants

Énoncé

Soit M = pmatrix 0 & 1 & 1 1 & 0 & 1 0 & 1 & 0 pmatrix la matrice d'adjacence d'un graphe avec les sommets \{A, B, C\}. Déterminer le degré sortant et le degré entrant de chaque sommet.

Indice : Le degré sortant d'un sommet est la somme de sa ligne. Le degré entrant est la somme de sa colonne.

Correction

1. Étape 1 : Deux degrés, deux directions de lecture — et c'est la convention ligne/colonne qui les distingue : Degrés d'un sommet orienté : Degré sortant de i = somme de la ligne i (les arcs qui partent) Degré entrant de i = somme de la colonne i (les arcs qui arrivent)
2. Étape 2 : Degrés sortants, en sommant les lignes :

   d^+(A) = 0+1+1 = 2 d^+(B) = 1+0+1 = 2 d^+(C) = 0+1+0 = 1

3. Étape 3 : Degrés entrants, en sommant les colonnes. La colonne 1 est faite du premier coefficient de chaque ligne :

   d^-(A) = 0+1+0 = 1 d^-(B) = 1+0+1 = 2 d^-(C) = 1+1+0 = 2

4. Étape 4 : Le contrôle qui valide les six calculs d'un coup. Chaque arc part d'un sommet et arrive à un sommet, donc les deux totaux comptent la même chose :

   d^+ = 2+2+1 = 5 d^- = 1+2+2 = 5

5. Étape 5 : Le graphe possède bien 5 arcs — c'est aussi le nombre de 1 dans la matrice. Les deux degrés d'un même sommet n'ont aucune raison d'être égaux : Ici A a 2 sorties pour 1 entrée, et C l'inverse. C'est justement ce que l'orientation permet de décrire. Dans un graphe NON orienté (matrice symétrique), les deux coïncident forcément. Ce contrôle est gratuit et attrape presque tout : Sommer les lignes et sommer les colonnes revient à additionner les mêmes coefficients dans deux ordres différents. Un écart entre les deux totaux signale une erreur de lecture, sans qu'on ait à tout refaire.