Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrige s 2 CAHIERS DE LA CRM Introduction à la théorie des graphes Solutions des exercices Didier Müller CAHIER NO COMMISSION ROMANDE DE MATHÉMATIQUE C C Graphes non orientés Exercice On obtient le graphe biparti suivant à gauche P C P C P C P C P C P C

CAHIERS DE LA CRM Introduction à la théorie des graphes Solutions des exercices Didier Müller CAHIER NO COMMISSION ROMANDE DE MATHÉMATIQUE C C Graphes non orientés Exercice On obtient le graphe biparti suivant à gauche P C P C P C P C P C P C En colorant les arêtes de ce graphe couleur heure de l ? horaire en prenant garde que chaque sommet n ? ait pas deux arêtes incidentes de même couleur on obtient le résultat de droite De ce graphe coloré on tire l ? horaire suivant P P P ère heure rouge C C C ème heure vert C C C ème heure bleu C C C ème heure noir C Exercice On obtient le graphe complet K Il faudra jours de tournoi Voici un calendrier possible Jour - - - Jour - - - Jour - - - Jour - - - Jour - - - Ce calendrier a été construit d ? après les cinq schémas ci-dessous CAHIERS DE LA CRM No bis C Exercice On utilise le graphe qui indique les cases atteignables depuis une case courante Les mouvements sont donc par exemple c -b a -c a -b c -a b -a c -a b -c a -c c -b a -c a -b c -a b -a c -a b -c a -c Exercice Comme Holmes dessinons un graphe avec les sommets A B C E F G et H Dans ce graphe on relie deux sommets i et j si les suspectes i et j se sont rencontrées au ch? teau Pour découvrir laquelle des femmes est venue plus d ? une fois au ch? teau il faut rechercher dans le graphe des cycles reliant quatre sommets sans diagonale En e ?et un tel carré ijkl sans diagonale indique que l ? une des quatre suspectes est nécessairement venue plus d ? une fois au ch? teau Pour s ? en convaincre on peut faire le petit schéma temporel ci-dessous On voit que i a dû venir deux fois au ch? teau pour qu ? un cycle sans diagonale apparaisse dans le graphe Le seul sommet commun à ces trois cycles est le sommet A C ? est donc Ann la coupable No bis CAHIERS DE LA CRM CExercice Construisons un graphe dont les sommets représentent les six personnes deux sommets sont reliés par une arête noire lorsque les personnes se connaissent et rouge dans le cas contraire Il s ? agit de prouver que ce graphe contient une clique K dont les arêtes sont de même couleur Si l ? on ne tient pas compte de la couleur des arêtes on obtient le graphe complet K De chaque sommet partent cinq arêtes et au moins trois d ? entre elles sont de même couleur noire ou rouge Considérons la clique K composée des sommets et Supposons par exemple que les arêtes et soient grises Considérons alors la clique K composée des sommets Si toutes ces arêtes sont