Terminale ES 2015-2016
Kartable
Terminale ES 2015-2016

Déterminer et utiliser la matrice d'adjacence d'un graphe

Pour construire la matrice d'adjacence M d'un graphe, on liste sommet par sommet les arêtes qui les relient entre eux.

Une matrice d'adjacence à la puissance n permet de connaître le nombre de chemins de longueurs n entre n'importe quel couple de point du graphe.

On considère le graphe suivant :

-

Construire sa matrice d'adjacence M puis déterminer le nombre de chaînes de longueur 3 reliant les sommets A et C.

Etape 1

Ranger les sommets dans l'ordre

On range les sommets dans un ordre déterminé.

  • Si les sommets sont des lettres, on les range de préférence dans l'ordre alphabétique.
  • Si ce sont des numéros, on les range dans l'ordre croissant.

On range les sommets dans l'ordre alphabétique : A, B, C, D.

Etape 2

Construire la matrice M vide

On construit la matrice vide en associant à chaque ligne et à chaque colonne un sommet, en respectant l'ordre déterminé précédemment.

On construit la matrice vide, en notant les en-têtes des lignes et des colonnes.

M=ABCDABCD

Etape 3

Remplir la matrice M ligne par ligne

Pour chaque ligne, on complète colonne par colonne :

  • Si le sommet associé à cette ligne est relié (en étant le point de départ de l'arrête dans le cas d'un graphe orienté), au sommet associé à la colonne, on marque le chiffre 1.
  • Sinon on marque le chiffre 0.

La première ligne correspond aux arêtes partant du sommet A :

  • Il n'y a pas de boucle en A : on note donc 0 sur la première colonne.
  • Il y en a une vers B : on note donc 1 sur la deuxième colonne.
  • Il y en a une vers C : on note donc 1 sur la troisième colonne.
  • Il y en a une vers D : on note donc 1 sur la dernière colonne.

On obtient :

M=ABCDA0B1C1D1

La deuxième ligne correspond aux arêtes partant du sommet B :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers D : on note donc 1 sur la dernière colonne.

On note 0 au niveau des autres colonnes.

On obtient :

M=ABCDA01B10C10D11

La troisième ligne correspond aux arêtes partant du sommet C :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers elle-même : on note donc 1 sur la troisième colonne.

On note 0 au niveau des autres colonnes.

On obtient :

M=ABCDA011B100C101D110

La dernière ligne correspond aux arêtes partant du sommet D :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers B : on note donc 1 sur la deuxième colonne.

On note 0 au niveau des autres colonnes.

Finalement, on obtient la matrice d'adjacence M :

M=ABCDA0111B1001C1010D1100

Etape 4

Calculer Mn

Afin de trouver le nombre de chaînes possibles de longueur n reliant deux points d'un graphe, on doit préalablement calculer Mn.

Sauf mention contraire de l'énoncé, on peut effectuer le calcul de Mn à la calculatrice.

On cherche le nombre de chemins de longueur 3 entre les sommets A et C. On calcule donc au préalable M3.

À l'aide la calculatrice, on obtient :

M3=3444422342324322

Etape 5

En déduire le nombre de chaînes de longueur n

Le nombre de chaînes de longueur n partant du sommet I et allant vers le sommet J est égal au coefficient de aij (le coefficient à l'intersection de la ligne correspondant au sommet I et de la colonne correspondant au sommet J) de la matrice Mn.

On en déduit le nombre de chemins de longueur n reliant les deux points.

Dans un graphe non orienté, le nombre de chaînes reliant I à J est égal au nombre de chemins reliant J à I, donc aij=aji.

Le nombre de chaînes de longueur 3 entre les sommets A et C est donné par le coefficient correspondant à la ligne A et à la colonne C de la matrice M3.

M3=3444422342324322

Il existe donc 4 chaînes de longueur 3 reliant A à C.

Si le graphe n'est pas orienté, la matrice d'adjacence est symétrique.

La présence d'un 1 sur la diagonale de la matrice M signifie que le sommet en question est relié à lui-même.

pub

Demandez à vos parents de vous abonner

Vous ne possédez pas de carte de crédit et vous voulez vous abonner à Kartable.

Vous pouvez choisir d'envoyer un SMS ou un email à vos parents grâce au champ ci-dessous. Ils recevront un récapitulatif de nos offres et pourront effectuer l'abonnement à votre place directement sur notre site.

J'ai une carte de crédit

Vous utilisez un navigateur non compatible avec notre application. Nous vous conseillons de choisir un autre navigateur pour une expérience optimale.