INFO EX2 TEST TES Spé 10 Déc 2012

                          INFO EX 2     TEST  TES   Spé  10 Décembre 2012

              EXERCICE 2

  
 d1-1.png

              1. a. La question revient à se demander si le graphe non ordonné ( et simple )

                       donné admet au moins une chaîne eulérienne.

                          OUI. 

                         En effet:

                         Dans ce graphe d'ordre 7 car ayant 7 sommets et 12 arêtes.

                        Les degrés des sommets sont:

Sommets A B C D E F G
Degrés 3 4 4 3 4 4 2

                         Comme le graphe est connexe ( tous le points sont reliables

                         par un chemin ) et que le nombre de sommets de degré impair est  2

                        il est possible d'emprunter chaque arête une et une seule fois.

                        Les deux sommets de degré trois sont A et D .

                        Conclusion:

                        Il existe au moins une chaine eulérienne  entre A et D.

                       L'énoncé ne demande pas d'en donner une.

                b. La question revient à regarder s'il existe un cyle eulérien dans le graphe .

                     NON.

                     En effet: 

                             Comme le graphe est connexe ( simple) l'existence d'un cycle eulérien

                             équivaut à avoir tous les dégrés des sommets qui soient pairs.

                             Or ici ce n'est pas le cas d'où la réponse négative.

              2. Indiquons la matrice à considérer pour connaître le nombres de chemins

                  de F à E en passant par deux stations c'est-à-dire par deux sommets.

                    Un tel chemin comporte 4 sommets. Il est donc de longueur 3.

                   ( 4 sommets cela fait 3 intervalles donc 3 arêtes )

                   M est la matrice adjacente du graphe.

                     Ainsi :

                    Conclusion: C'est  la matrice M3   qu'il faut examiner.

                    F est le sixième sommet et E est le cinquième sommet.

                  Conclusion:  C'est le terme de rang ( 6 ; 5 ) de M3  qui donnera le nombre

                         de chemins de F à E en passant par deux stations.

          3. Donnons le trajet de A à G le plus court .

                 C'est  A-B-D-G   de durée  7  + 15 + 5 = 27   mn

                Sur le graphe on peut mettre les informations d'un algoritme 

               qui permet de dire le chemin le plus court.

                   G ( 27 D) ← D ( 22 B )  ← B ( 7A )  ← A ( 0 )

         4. Donnons le nombre chromatique λ.

                 On a:    m ≤  λ ≤  Δ  + 1

                     Δ est le plus grand degré c'est-à-dire ici 4.

                     m est l'ordre du plus grand  sous grphe complet.

                   Ici   m = 3.

                  Donc     3  ≤  λ ≤ 5

                    En examinant le graphe on constate que 3 couleurs suffisent;

                    Rouge  pour  A , E , G car ces points ne sont pas adjacents.

                    Vert pour   F , B    car ces points ne sont pas adjacents.

                   Bleu  pour   celui non encore cité c'est-à-dire  pour C.

                  Conclusion: Trois suffisent pour colorier le graphe.

 

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