INFO TEST GRAPH Déc. 2010

 NOM: ......                Prénom: ..............                 Date:  Déc   2010           Classe: BTS.

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

  • Combien dans un graphe,  un chemin de longueur 4 nécessite-t-il de sommets

     distincts ou confonfus ?  Cinq sommets  

  • Soit G un graphe de n sommets avec n entier naturel tel que n > 2  et sans circuit.

    •• Peut-il avoir un chemin de longueur n ?   NON

                 Pour un chemin de longueur n

               il faut n + 1  sommets distincts ou confondus.

               Comme il n' y a pas de circuit tous les sommets des chemins sont distincts.

              Il est impossible d'avoir n + 1 sommets distincts alors

              que le graphe n'en a que n.

    •• Que peut-on dire de la matrice M n  si M est sa matrice adjacente ?   

           C'est la matice nulle.   Il n'y a pas de chemin de longueur n .

  •Soit le graphe G de sommets ABCDEF dont les arcs sont:  ( A , B ) , ( A , C ) , ( C, F ) ( C , B )

       ( B , D ) ,  ( D , F ) , ( E , F ) ,( E ,B ).

       •• Donner sa matrice d'adjacence M. 

   / 0 1 1 0 0 0  \
 / 0 0 0 1 0 0      \
| 0 1 0 0 0 1        |
| 0 0 0 0 0 1        |
 \ 0 1 0 0 0 1      /
    \ 0 0 0 0 0 0   /

 

        ••   Y a-t-il des boucles ?  NON

           car il n'y a que des 0 dans la diagonale principale.  

      •• Comment peut-on interpréter les deux colonnes de 0 de M ?

         Il n'y a aucun arc qui arrive à A ni à E

    •• Représenter G. 

  

   ••Compléter le tableau:

PREDECESSEURS       SOMMETS NIVEAUX
A 0
A C E B 2
A C 1
B D 3
E 0
CDE F 4

    ••Refaire le graphe en l'ordonnant suivant les niveaux.

              

    •• Trouver les matrices M2 , M3 , M4 , M5 . En déduire M6  .

M2   

   / 0 1 0 1 0 1  \
 / 0 0 0 0 0 1      \
| 0 0 0 1 0 0        |
| 0 0 0 0 0 0        |
 \ 0 0 0 1 0 0      /
    \ 0 0 0 0 0 0   /

 M3

   / 0 0 0 1 0 1  \
 / 0 0 0 0 0 0      \
| 0 0 0 0 0 1        |
| 0 0 0 0 0 0        |
 \ 0 0 0 0 0 1      /
    \ 0 0 0 0 0 0   /

M4

   / 0 0 0 0 0 1  \
 / 0 0 0 0 0 0      \
| 0 0 0 0 0 0        |
| 0 0 0 0 0 0        |
 \ 0 0 0 0 0 0      /
    \ 0 0 0 0 0 0   /

 M5

   / 0 0 0 0 0 0  \
 / 0 0 0 0 0 0      \
| 0 0 0 0 0 0        |
| 0 0 0 0 0 0        |
 \ 0 0 0 0 0 0      /
    \ 0 0 0 0 0 0   /

  

  M6 est nulle 

  •• On admet pour chaque arc les durées en mn suivantes:       

  AB : 2     AC: 12     CF: 17       CB : 4        BD: 7    DF :  11    EF :  12    EB: 14

      Mettre sur chaque arc la durée et donner le ou les chemins de longueur minimal de A à F.

       Le chemin de A à F  de longueur minimale est ABDF   

      Il est de longueur     2 +7 +11 = 20 mn

             

 •• Trouver la matrice booléenne M' telle que : ( M ' ne peut comporter que des 0 ou 1 )

                M ' = M ( + ) M[2] ( + ) M[3] ( + )  M[4]  ( + ) M[5] .   (  Somme booléenne )

      La matrice M ' est :  

   / 0 1 1 1 0 1  \
 / 0 0 0 1 0 1      \
| 0 1 0 1 0 1        |
| 0 0 0 0 0 1        |
 \ 0 1 0 1 0 1      /
    \ 0 0 0 0 0 0   /

   

  •• Comparer M et M '. 

           Il y a 5 arcs supplémentaire dans M '

   ••Soit G ' le graphe de matrice d'adjacence M '.

      Représenter G '  .  (  Fermeture transitive de G )

   

     Mettre en couleur les arcs de G ' qui ne sont pas dans G.

      Citer ces arcs colorés. Que représentent-ils ? .......................

     ( A , D )  , ( B , F )   , ( A , F )    , ( C , D )   , ( E ,  D )

      Ce sont les racourcis.