INFO Problème1 bac ES spé

                     Deux problèmes de niveau bac                    TES Spé maths                            10 décembre  2012

             PROBLEME 1:

  1. a.  Dessinons un graphe représentant cette situation.

     B    C     L     M     P  
 B      X     X  X
 C    X    X   X  
 L       X     X  
 M      X   X  X    X
 P   X       X  

        D'apès le tableau on peut considérer le graphe non orienté suivant:

                                       Graphepbbac  

      b. Regardons s'il est possable de trouver un trajet qui passe une fois et une seule par toutes les rues de ce plan.

           Cela revient à regarder s'il y a une chaîne  eulérienne.

            Pour cela donnons le tableau des degrés des sommets.

 Sommets    B    C    L     M     P  
  Degrés  3   3    2   4  2

          On voit que le nombre de sommets de degré impair est 2 et le graphe est connexe.

                       Ce sont les sommets B et C qui sont seulement de degrés  impairs.

                       D'après le Th d'Euler il existe bien une chaîne eulérienne reliant B et C.

            On peut considérer :    B - P-  M - B - C - L-  M- C  

       c. Regardons si un distributeur qui veut passer dans toutes les rues une fois et une seule

          peut partir d'un sommet pour revenir au sommet  de départ.

                              Autrement dit regardons s'il existe un cycle eulérien.

                              Ce n'est possible , d'après le th d'euler, que si tous les sommets sont de degré pair.

                              Ce qui n'est pas le cas.

                   Donc .

                 Conclusion:  NON. Quelque soit le sommet de départ choisi le distributeur ne peut pas 

                  passer dans toutes les rues une fois et une seule  pour finlement revenir au sommet de départ.

               2.   Indiquons le nombre de types différents de fleurs à prévoir .

                     Cela revient à donner le nombre  chromatique λ  c-à-d le nombre minimal de couleurs 

                     pour que deux sommets adjacents ne soientt pas de la même couleur.

                     L'ordre du plus grand sous graphe complet est  ici m = 3.

                   Le degré le plus élevé est :   Δ = 3

                   Donc d'après le cours :    m ≤  λ   ≤   Δ + 1

                    c-à-d                                    3  ≤  λ   ≤   4   

      Rangeons les sommets dans l'ordre décroisssant de leur degré:                             

Sommets    M       B       C        L       P   
Degrés     4     3     3    2     2
couleurs  Rouge Bleu Vert Bleu Vert

                               Graphepbbaccolorie

                Conclusion:    Trois couleurs suffisent.   λ = 3

              3. Proposons un trajet le plus court possible de D à P

                   pour le graphe orienté donné.

                            Groriente 1

              Tableau de Moore:

  B     C     D               L          M      P           Sommet sélectionné ( mais pas forcément retenu )   
∞   ∞   0            ∞         ∞       ∞          D        Les sommets adjacents à D sont:   B C   L
 9 D  au lieu de ∞  5 D IIIIII   11 D    au lieu de  ∞           ∞       ∞          C    car 5D: le plus petit. Sommets adjcents à C : B M L
5 +3=8 C mieux que 9 D IIIIII IIIIII  5 + 4 C  mieux que 11D  5+9 C    mieux que ∞       ∞         B     car 8 C: le plus petit .   Sommets adjcents à B: M P   
IIIIIIIIIIIIIIIIIIIIIIIIIIIII IIIIII IIIIII  9 C  ( non adjacent  à B)  8+5=13 B mieux que 14C 8+10=18 B mieux que  ∞         M     car 13 B : le plus petit.  Sommets adjacents à M:  P
IIIIIIIIIIIIIIIIIIIIIIIIIIIII IIIIII IIIIII   IIIIIIIIIIIIIIIIIIIIIIIIII 13+4=17 M  mieux que 18 B         P
IIIIIIIIIIIIIIIIIIIIIIIIIIIII IIIIII IIIIII   IIIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIII    
IIIIIIIIIIIIIIIIIIIIIIIIIIIII IIIIII IIIIII   IIIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIII    
IIIIIIIIIIIIIIIIIIIIIIIIIIIII IIIIII IIIIII   IIIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIII    

                    On va retenir :

                   P  ( 17 M ) ---- M  (13 B) ------- B  ( 8 C)   ------ C ( 5 D )  ------D(0)

            Donc  le trajet le plus court est  de 17 mn en considérant :    D ------> C ------->  B -------> M  --------> P 

                            Groriente2 1

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