INFO DS n° 2 TES SPE 18 novembre 2012

                      INFO DS n° 2      18 novembre 2012      TES  spé 

      Donné également le  16 / 12 / 2013

                                ds-tes-spe-18-nov-2012-1.png

                                 ds-page-2-tes-spe-maths-18-nov-2012.png

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

              REPONSE  

                  EXERCICE 1: 

           1.a.  Dans la somme des degrés, une arête d'un graphe non orienté

                    compte pour 2 même quand c'est une boucle.

                   L'idée c'est que chaque arête compte pour 1 pour chacune des extrémité de l'arête.

                  Chaque arête a deux extrémités.

              b. Dans le graphe G de la figure, C est de degré   1 + 1 + 2 =  4

               •   [ CE ] compte 1  pour le degré de C car C est une extrémité.

               •   [ CB ]  compte 1  pour le degré de C car C est une extrémité.

              •    CC , la boucle, compte 2  pour le degré de C car C en est les deux extrémités.

                   Le nombre d'arêtes est :  8

                En effet :                

Sommets A B C D E Total
Degrés 3 3 4 3 3   16

                  Il y a 16 pour la somme des degrés.   16 / 2 = 8

                  Il y a donc 8 arêtes.

          c. La somme des degrés du graphe G '  des sommets est 14.

               En effet :                

Sommets A B C D E Total
Degrés 3 3 2 3 3   
14
 
                        Il y a 14 pour la somme des degrés.   14 / 2 = 7
                       Il y a donc 7 arêtes.
                      L'ordre du plus grand sous graphe complet est  3
                      Le sous graphe avec les sommets ABD est l'un d'eux.
       2. D'une façon générale la parité de la somme des degrés d'un graphe non orienté est " paire" .
            En effet chaque arête ( boucle aussi ) compte pour 2 dans la somme des degrés.
       3. NON.  
                    3 × 5 = 15  serait la somme des degrés. Elle serait impaire.
           Si les 5 sommets sont de degré 3 la somme des degrés des 5 sommets est 15 qui est impair.
           Donc la situation est impossible.
        4. NON.
             Si le graphe comporte n sommets avec n impair, de degré 3 ,alors  la somme des degrés
              des sommets est  3 n , qui est impair. Ce qui est impossible .
 ---------------------------------------------------------------------------------------------------------------------
   REPONSE
               EXERCICE 2 
 
                      1. La matrice du graphe G de l'exercice 1 est:
                           
     / 0 1 0 1 1 \
    |      1     0     1     1    0    |  
M   = | 0 1 1 0 1  |
    | 1 1 0 0 1  |
     \ 1 0 1 1 0 /
  
                       2.  OUI.
                               En effet: Deux par deux les sommets sont adjacents.
                       3. OUI.
                           En effet :  Entre deux sommets il existe au moins un chemin.
                       4. La matrice M2    est :  
                          
     / 3 1 2 2  1 \
    |      1     3     1     1    3    |  
M2   = | 2 1 3 2 1  |
    | 2 1 2 3 1  |
     \ 1 3 1 1 3 /
  
                  a. Le nombre de chemins de longueur 2 est obtenu en sommant les
                       termes de  M2   c-à-d  45   puis en retirant , comme il n'y a pas d'ordre
                        la somme des termes  en dessous de la diagonale principale.
                       Donc     45 - 15 = 30        ( par exemple [ AB] n'est pas distinct de [BA]  )    
             
     / 3 1 2  2  1 \
    |      1     3     1     1    3    |  
M2   = | 2 1 3 2 1  |
    | 2 1 2 3 1  |
     \ 1 3 1 1 3 /
             
                  b.  Le nombre de chemins de longueur 2   de A à D est 2.
                        sur la première ligne et la quatrième colonne.
                              ABD    AED
                      ( On n'a pas tenu compte du 2 à l'intersection de la 4ième ligne
                           et 1ère colonne car il n'y a pas d'ordre )
------------------------------------------------------------------------------------------------------
              EXERCICE 3
 
               •  OUI. Le graphe est complet car deux à deux les sommets sont adjacents.
               •   OUI. Il y a au moins un chemin eulérien . Il est même fermé.
                                 C'est donc un cycle éulérien.
                                                   Image3duds2
                           En effet:
                   On a un graphe non orienté 
 (simple, conformément au programme c-à-d  sans doublon d'arête entre deux sommets )
                    Ls degrés des sommets sonts:
 Sommets     A     B       C       D       E  
  Dégrés  4   4   6   4    4  
                   Ainsi:
                  Il n'y a aucun sommet de degré impair et le graphe est connexe
                   ( Deux sommets quelconques sont reliés par au moins un chemin ).
                   Donc il y a une chaîne fermée eulérienne  c-à-d un cycle eulérien.
                   DECCBADCAEBD   convient.
-----------------------------------------------------------------------------------------------------