contrôles en terminale ES

contrôle du 05 fevrier 2011

Corrigé de l'exercice 2 : Élèves ayant suivi l'enseignement de spécialité

On considère le graphe suivant :

Graphe : L'illustration svg n'est pas visible par votre navigateur.
  1. Le graphe est-il connexe ?

    La chaîne A-B-C-D-E-F-G-H contient tous les sommets du graphe par conséquent, il existe au moins une chaîne reliant deux sommets quelconques.

    Le graphe est connexe


  2. Le graphe admet-il des chaînes eulériennes ? Si oui, en préciser une.

    Déterminons le degré de chacun des sommets.

    SommetsABCDEFGH
    Degré43444344

    Le graphe est connexe et il existe deux sommets de degré impair, il admet donc une chaîne eulérienne commençant par un des deux sommets de degré impair (B ou F) et finissant par le deuxième sommet de degré impair. Par exemple :

    Graphe, chaîne eulérienne : L'illustration svg n'est pas visible par votre navigateur.

    F - C - H - E - A - D - G - B - C - D - E - F - G - H - A - B est une chaîne eulérienne.


  3. Justifier la non-existence d'un cycle eulérien pour le graphe . Quelle arête peut-on alors ajouter à ce graphe pour obtenir un graphe contenant un cycle eulérien ?

    Il y a un cycle eulérien si tous les sommets du graphe sont pairs. Il suffit donc d'ajouter une arête entre les sommets G et F pour obtenir un graphe connexe dont tous les sommets sont de degré pair


  4. Soit M la matrice associée à ce graphe (les sommets sont pris dans l'ordre alphabétique).On donne la matrice M3=(41031278312100111811113110143110141211421211427831241031281111100111311014311014121142121142) Déterminer le nombre de chaînes de longueur 3 partant du sommet G et aboutissant au sommet E. Citer alors toutes ces chaînes

    Les sommets de la matrice M sont pris dans l'ordre alphabétique, par conséquent, le terme m75 situé à l'intersection de la septième ligne et de la cinquième colonne de la matrice M3, donne le nombre de chaînes de longueur 3 partant du sommet G et aboutissant au sommet E  

    Il y a 3 chaînes de longueur 3 partant du sommet G et aboutissant au sommet E : G-B-A-E, G-D-A-E et G-H-A-E.


  5. Donner un encadrement du nombre chromatique X du graphe. Déterminer ce nombre chromatique, en explicitant clairement la démarche.

    Le plus haut degré des sommets est 4 donc X4+1 . D'autre part, A-D-E est un sous graphe complet d'ordre 3 donc X3. Ainsi, 3X5

    Utilisons l'algorithme de coloration de Welsh et Powell :
    Les sommets étant classés par ordre de degré décroissant, on attribue la couleur 1 aux sommets A, C et G; la couleur 2 aux sommets D, H, B et F ; la couleur 3 au sommet E.

    Graphe, coloration : L'illustration svg n'est pas visible par votre navigateur.

    Une coloration du graphe avec 3 couleurs est possible et 3X5 donc le nombre chromatique de ce graphe est égal à 3.



Rechercher des exercices regoupés par thème


[ Accueil ]


Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.