INFO TEST 6 GRAPHE BTS1 janvier 14

                         INFO TEST 6        GRAPHE BTS1            janvier 14

    EXERCICE        

          G est le graphe de sommets A,B,CD,E,F  défini par

       sa matrice adjacente  M suivante:

            Tam

            1. Faire une représentation du graphe G.

                 Réponse:

                        Gr791 1

            2. Rechercher le nombre de chemins de longueur 3. Enumérer ces chemins.

                Réponse:

                  On a :

                       Maucube

               La somme des termes de la matrice M3 est :   1+1+1+1+1 = 5

                    Conclusion:   Il y a donc 5 chemins de longueur 3 

                                   On a :   ACCC

                                                AEEE

                                                CCCC

                                                EEEE

                                                FCCC

            3.  La conjecture disant que le graphe ne comporte aucun chemin de longueur 5

                  est-elle vraie?

                  Que  peut-on en déduire?

                 Réponse:

            La conjecture est fausse puique  C C C C C C  est déjà un chemin de longueur 5.

            On peut en déduire que la matrice M5  n'est pas la matrice nulle.

            4.  Rechercher  la matrice de la fermeture transitive de G.

                  Placez en couleur, si nécessaire, sur le dessin précédent les arcs manquants

                  pour obtenir le graphe de la fermeture transitive.

                 Réponse:

                      Somme

 

                       A l'aide de la calculatrice:

                            M6 = M5 = M4 = M3

 

                         Donc :  

                            Sompart

                 De plus :  

                           Mcarr

              On obtient:

               Mtt 2

               La fermeture transitive du graphe G est lui-même.

                       Gr791 1

----------------------------------------------------------------------------------------------------------