EXERCICE matrices et graphe TES spé

 

             TEST   Graphes       Spé math.                        décembre 2012

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

           EXERCICE 1

                   graphe234-1.png 

                 Un graphe G pondéré simple non orienté d'ordre 7 est représenté ci-dessus.

                 Le nombre positif sur chaque arête est un nombre de minutes.                 

                  1. Donner la matrice adjacente M de G.

                  2. Ce graphe est-il complet ? connexe ? Expliquer.

                  3. Quel est l'ordre m du plus grand sous graphe complet de G ?

                  4. Donner le tableau des degrés des sommets.

                  5. Soit Δ le degré le plus élévé d'un sommet de G.

                       Donner un encadrement du nombre chromatique λ.

                       Déduire alors le nombre chromatique λ .

                   6.Colorier ce graphe G.

                   7. On veut déterminer le chemin de plus courte durée entre le sommet

                      D et L.

                     Pour cela compléter le tableau suivant:

Sommet

de marque

fixée à

chaque étape

    D         G        M       H      C       S      L      Commentaires                

     D: 0     


   0  8(D)  10(D) + ∞ + ∞ + ∞ + ∞  De D à G 8mn et de D à M 10mn 
               

 

 

 

 

               

 

 

               

 

 

                 
                 
                 
        0              

       Quel est donc le plus dourt chemin de D à L ?     

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

           EXERCICE 2

                 Voici un graphe G  pondéré non orienté simple d'ordre 8

                de sommets A B C D E F G H.

                    graphe235.png

                Expliquez le tableau suivant que vous pouvez améliorer.

               Que permet-il de savoir?

Marque fixée  A      B      C      D      E     F     G     H     
    A: 0 0  2 1 3  + ∞   + ∞  + ∞  + ∞  
    C : 1       2 4        
    B : 2           6      
     D :2         3   4    
     E: 3                  
     I : 4 0 2 1 2 3 6 4 8  
                   

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