Infos

Vous devez être inscrit pour accéder à ces informations.

Ceci vous permet de visualiser les ressources déjà vues et marquer à revoir celles qui nécessitent d'être retravaillées.

Inscrivez vous gratuitement ici....

Contenu

Matrice d’un graphe

Graphe complet

Nombre de chaînes de longueur 3

Exercice | temps recommandé inférieur à 5mn | Niveau 1 application directe du cours | séquence 1 du chapitre |
On a schématisé ci-dessous une partie du plan du métro londonien par un graphe $\mathcal{G}$ dont les sommets sont les stations et les arêtes sont les lignes desservant ces stations.
Chaque station de métro est désignée par son initiale comme indiqué dans la légende.
  1. Donner la matrice de ce graphe (en ordonnant les sommets dans l'ordre alphabétique).
    Rappel cours

    Matrice associée à un graphe
    La matrice associée à un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension $n$, où le terme à l'intersection de la iième ligne et de la jième colonne est nombre d'arêtes reliant i et j.
    Cette matrice est appelée matrice d'adjacence du graphe.

    Aide

    Il y a 8 sommets donc la matrice est une matrice carrée d'ordre 8
    Les coefficients de la première ligne correspondent aux arêtes partant du sommet B: Bond Street

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  2. Ce graphe est-il complet?
    Rappel cours

    Graphe complet
    Un graphe est complet si chaque sommet est adjacents à tous les autres

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  3. Donner une chaîne de longueur 4 reliant les sommets B et G.
    Rappel cours

    Matrice associée à un graphe
    La matrice associée à un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension $n$, où le terme à l'intersection de la iième ligne et de la jième colonne est nombre d'arêtes reliant i et j.
    Cette matrice est appelée matrice d'adjacence du graphe.

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  4. Pour la suite, on donne la matrice $M^3$:
  5. Un touriste se trouve à la station Holborn et prévoit de se rendre à Green Park en utilisant exactement trois lignes de métro.
    Quel est le nombre de trajets possibles?
    Rappel cours

    Nombre de chemins de longueur $p$
    Soit $G$ un graphe d'ordre $n$ et de matrice d'adjacence $M$.
    Le coefficient $m_{ij}$ de la matrice $M^p$ ($p$ entier naturel non nul) est le nombre de chaînes de longueur $p$ reliant les sommets $i$ et $j$.

    Aide

    Holborn correspond à la ligne 4 et Green Park à la colonne 3

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements


Vous devez être abonné pour accéder à ce contenu...

Infos abonnements

error: Ce contenu est protégé