La page http://www.mathemaths.com/pages/algorithmique/424.html est protégée par un mot de passe.

INFO EX 2 TEST BTS1A janvier 2015

                       INFO EXERCICE 2   TEST BTS 1 A   mercredi 21 janvier 2015

          EXERCICE 2

                Soit G un graphe orienté simple de sommets ABCDEF dont la matrice adjacente est :

                   Ewv1

        1. a. Comment interprétez-vous la présence de trois colonnes de zéros dans M ?

                  REPONSE:

                       Les sommets A , B , C n'ont pas de prédécesseur.

            b. Comment interprétez-vous la présence d'une ligne de zéros dans M?

                    REPONSE:

                    Le sommet F n'admet pas de succsseur.

            2. Le graphe comporte-t-il des boucles?

                      REPONSE:

                         NON. En effet il n'y a aucun 1 dans la diagonale principale.

           3. Combien d'arcs G comporte-t-il?

                 REPONSE:

                     Il comporte 7 arcs car il y a sept 1 dans la matrice adjacente M.

              Dresser le tableau des prédécesseurs et des successeurs.

                     REPONSE:   On a : 

Prédécesseurs     Sommets      Successeurs  
  A  D F
  B  D
  C  E F
    A B D  E
   C D E  F
 A C E F  

              4.Compléter le tableau par les niveaux des sommets.                      

                      REPONSE:

Prédécesseurs    Sommets     Niveaux   
  A   0
  B   0
  C   0
     A  B D   1
        C  D E   2
    A  C  E   F   3

           5. Proposer une repésentation de G en l'ordonnant suivant les niveaux.

                        REPONSE:

                                   Wev2

            6. Trouver les matrices M2 , M3 , M4 , M5  , M6 .

                     REPONSE:

                        On a :

                         M2e

                          M2e1

                               M4  =  M5 = M6  = 0

          7. a.Combien y a-t-il de chemins de longueur 2 qui arrivent à E?

                   REPONSE:

                     Dans M2 dans la 5 ième  colonne il y a deux 1 .

                      Donc il y a deux chemins de longueur 2 qui arrivent à E.

              b. Combien y a-t-il de chemins de longueur 2 qui arrivent à F?

                     REPONSE:

                       Dans M2 dans la 6 ième  colonne il y a deux 1 .

                      Donc il y a deux chemins de longueur 2 qui arrivent à F.

              c. Trouver les chemins de longueur 2.

                       REPONSE:

                       A   D  E                   B  D   E                   C  E   F         D E  F

           8. a.Combien y a-t-il de chemins de longueur 3?

                     REPONSE:

                          Il y a deux 1 dans la matrice M3 .

                          Donc il y a deux chemins de longueur 3.

                b. Existe-t-il des chemins de longueur supérieur à 3?

                     REPONSE:

                             NON. En effet  M4 = 0

           9 . a. Reproduire le graphe précédent en rajoutant les raccourcis.

                      On obtient un nouveau graphe G ' appelé :

                     << Fermeture transitive de G >>

                  REPONSE:

                          Il y a 4 raccourcis.

                       Wev245 1  

                b. Donner la matrice adjacente au graphe G .

                       REPONSE:

                          On a :

                         M2e12                  

            10. a Préciser les matrices booléennes:

                      M[ 2 ]   ,   M[3 ]  ,  M[ 4 ]  , M[ 5 ]  , M[ 6 ]               

               Ici ce sont les matrices    M 2    ,   M 3   ,  M 4   , M 5   , M 6    

                déjà trouvées.   

                 b. Calculez la somme booléenne A des matrices

                        M[ 2 ]   ,   M[3 ]  ,  M[ 4 ]  , M[ 5 ]  , M[ 6 ]

                       C'est-à-dire trouver la matrice A telle que :

      Ske14

                   REPONSE:

           On obtient :

                       M2e123

                         Comparer M ' et A .

                On a  :  M '  = A

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