INFO EX 1 TEST TES 10 décembre 2012

                     INFO   TEST3      TES     Spé   10 décembre 2012

                EXERCICE 1

             1.a. Dessin du graphe  non orienté caractérisé par le tableau.

  B C L M P
B   1   1 1
C 1   1 1  
L   1   1  
M 1 1 1   1
P 1     1  

              Il apparaît que le graphe comporte 5 sommets et 7 arêtes.

                   c40.png

        b. Recherche de l'existence d'une chaîne eulérienne.

                           Utilisons le cours :  C'est la première chose à faire

                            On ne commence pas par en chercher un.

                              • Le graphe est connexe. 

                                En effet:

                                On peut relier deux sommets quelconques

                                du graphe par un chemin.

                              • Dans ce cas le cours dit quand le graphe est non orienté

                                 et est simple( c-à-d sans double arête entre deux sommets

                                comme dans le programme):

                                 " Il existe une chaîne eulérienne

                                  ssi  il y a exactement  zéro ou deux sommets de degré impair.

                                 Dans ce dernier  cas la chaîne relie les deux sommets de degré impair"

                                     Comptons donc le nombre de sommets de degrè impair.

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

                                            Il y a deux sommets exactement de degré impair.

                                            Ce sont B et C.

                                    Conclusion:   D'après le cours il existe au moins une

                                                              chaîne eulérienne entre B et C.

                                A présent on nous demande d'en citer une.

                                 On peut citer:    B-P-M-B-C-L-M-C

                                 Mais encore :     B-P-M-B-C-M-L-C 

                                  c41.png

                                 Il peut en exister d'autres.

                                 Mais attention:

                                     Ils relient les sommets B et C  obligatoirement.

                 c. Regardons s'il existe un cycle eulérien.

                                 Pareil:   On fait appel au cours.

                              Comme le graphe est connexe non orinté et simple, il dit:

                             " Il existe une cycle eulérien ssi tous les degré sont pairs."

                            Ce n'est pas le cas ici.

                            Conclusion : Il n'y a pas de cycle eulérien.

                  2. Cherchons le nombre minimum de sortes de fleurs.

                        Cela correspond au nombre chromatique λ.

                           On sait d'après le cours que :

                                         m    ≤    λ   ≤  Δ + 1

                                     o ù     Δ   est l degré le plus élevé. Ici  Δ = 4

                                        et m l'ordre du plus grand sous graphe complet. Ici m = 3

                                   On a donc:                 3  ≤    λ   ≤  4 + 1  

                                     c-à-d       3  ≤    λ   ≤  5

                                    Ici trois types de fleurs vont pour respecter les consignes.

                                   • Un type de fleurs pour M .

                                   • Un type de fleur pour B et L

                                  •  Un type de fleurs pour P et C

                          c44.png

                    ATTENTION le graphe n'a pas changé.

                 4. Cherchons le plus court chemin de D à P.

                       L'énoncé pour cette question donne un nouveau graphe.

                       c45.png

                       Il est pondéré.

                           c46-2.png

                          Utilisons un algorithme:

                             c48.png

                           On a :    P ( 17 B ) ← M (13 B  ) ←  B (8 C )  ←C (5 D) ←D ( 0 )

                            Donc en remontant:

                          Conclusion:     D-C-B-M-P    est de longueur 5 + 3 + 5 + 4 = 17 mn

                          On pouvait également faire un tableau.

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