Nouveau

🔥 Découvre nos fiches d'exercices gratuites avec corrections en vidéo !Accéder aux fiches  →

Tchat avec un prof

🤔 Bloqué sur un exercice ou une notion de cours ? Échange avec un prof sur le tchat !Découvrir  →

Déterminer la matrice d'adjacence d'un graphe - Exercice 1

3 min
5
On considère le graphe GG représenté ci-dessous :
Question 1

Donner la matrice d’adjacence MM du graphe \mathcal{} (les sommets seront rangés dans l’ordre alphabétique)

Correction
Le graphe possède 55 sommets donc le graphe est d'ordre 55. Cela signifie que la matrice d'adjacence MM sera une matrice carrée d'ordre 55.
Nous allons expliquer pour ce premier exemple, comment nous avons rempli les deux premières ligne de la matrice MM étape par étape .
N'hésitez pas à reprendre la vidéo également.
Etape 1 :\red{\text{Etape 1 :}} La première ligne correspond aux arêtes partant du sommet AA .
  • Il n'y a pas d'arête qui va de AA vers AA, c'est à dire il n'y a pas de boucle en AA. Il y aura donc 00 sur la première ligne et première colonne.
  • Il y a une arête qui va de AA vers BB. Il y aura donc 11 sur la première ligne et deuxième colonne.
  • Il y a une arête qui va de AA vers CC. Il y aura donc 11 sur la première ligne et troisième colonne.
  • Il n'y a pas d'arête qui va de AA vers DD. Il y aura donc 00 sur la première ligne et quatrième colonne.
  • Il y a une arête qui va de AA vers EE. Il y aura donc 11 sur la première ligne et cinquième colonne.
    • Etape 2 :\red{\text{Etape 2 :}} La deuxième ligne correspond aux arêtes partant du sommet BB .
  • Il y a une arête qui va de BB vers AA. Il y aura donc 11 sur la deuxième ligne et première colonne.
  • Il n'y a pas d'arête qui va de BB vers BB, c'est à dire il n'y a pas de boucle en BB. Il y aura donc 00 sur la deuxième ligne et deuxième colonne.
  • Il n'y a pas d'arête qui va de BB vers CC. Il y aura donc 00 sur la deuxième ligne et troisième colonne.
  • Il y a une arête qui va de BB vers DD. Il y aura donc 11 sur la deuxième ligne et quatrième colonne.
  • Il n'y a pas d'arête qui va de BB vers EE. Il y aura donc 00 sur la deuxième ligne et cinquième colonne.
    • Finalement, la matrice d'adjacence MM s'écrit alors :
    M=(0110110010100100110110010)M=\left(\begin{array}{ccccc} {0} & {1} & {1} & {0} & {1} \\ {1} & {0} & {0} & {1} & {0} \\ {1} & {0} & {0} & {1} & {0} \\ {0} & {1} & {1} & {0} & {1} \\ {1} & {0} & {0} & {1} & {0} \end{array}\right)

    Signaler une erreur

    Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

    Connecte-toi ou crée un compte pour signaler une erreur.