Déterminer dans graphe trajet le plus court - Matrices


  • N

    Bonjour,

    J'ai un exercice sur les graphes dont je n'arrive pas à faire les deux dernières questions:

    (pour ceux qui l'on il s'agit du livre hyperbole édition 2006 terminale es p330 n°58)

    1 - vrai ou faux (avec justifications): il existe au moins un chemin de longueur 3 qui relie chaque sommets à chacun des sept autres sommets du graphe

    sachant que la matrice M^3 est:

    11 ; 8 ; 11 ; 10 ; 12 ; 5 ; 13 ; 4
    8 ; 2 ; 7 ; 3 ; 5 ; 2 ; 4 ; 3
    11 ; 7 ; 8 ; 6 ; 12 ; 3 ; 10 ; 5
    10 ; 3 ; 6 ; 2 ; 11 ; 1 ; 4 ; 8
    12 ; 5 ; 12 ; 11 ; 8 ;8 ; 13 ; 3
    5 ; 2 ; 3 ; 1 ; 8 ; 0 ; 2 ; 6
    13 ; 4 ; 10 ; 4 ; 13 ; 2 ; 6 ; 9
    4 ; 3 ; 5 ; 8 ; 3 ; 6 ; 9 ; 0

    je comprends pas vraiment la question
    (désolée pour illisibilité mais je n'ai pas pu faire autrement)

    2 - Déterminer, à l'aide d'un algorithme, le trajet le plus court pour aller de A à H et donner ce trajet

    sachant que le poids des arêtes est de:

    A entre B 3
    A " C 11
    A " G 20
    A " E 16
    A " D 17
    B " C 5
    C " E 6
    C " G 7
    D " E 3
    D " H 9
    E " G 6
    E " F 7
    F " H 4
    G " H 11

    je sais à peu près comment il comment faire le tableau mais je n'y arrive pas, je ne sais pas comment prendre en compte le fait que le trajet s'arrête à H.

    est-ce que quelqu'un peut m'aider merci d'avance


Se connecter pour répondre