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

Documents similaires
Installation complete serveur email 1 0 0
Apprendre l x27 anglais en 75 lecons progressives 0 0
Veines urbaines 2019 Du AvRIL Au juin CENTRE SOCIOCULTUREL journée d'ouverture JEAN-PRÉVOST SAMEDI AvRIL RENSEIGNEMENTS Au CLe cBo llAeTctif SWING AT THE TOP réalise pour Lyon - l'occasion des ans Projection d ? animation D sur un bloc de béton surplomban 0 0
Projet 2 L ? enseignant Sage Homme Français CEM ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? CL ? enseignant Sage Homme Français CEM ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? CL ? enseignant Sage Homme Français CEM ? 0 0
Op5 5 at 1 L ? AMBIANCE LUMINEUSE ET LES RISQUES PROFESSIONNELS Dr A TIBERGUENT C PRINCIPES FONDAMENTAUX DE L ? ECLAIRAGE LES DEFINITIONS L ? ?IL ET LA VISION LES PRINCIPES FONDAMENTAUX D ? UN BON ECLAIRAGE LES FACTEURS DE GENE ET D ? INCONFORT ET EFFETS 0 0
Devoir 1 52 CYCLES THEORIQUES Exercice Etablir les expressions des rendements théoriques du Cycle de Beau de Rocha ?? en fonction de ? th AN ? Cycle diesel pur ??th en fonction de ? et ? AN ? et ? Cycle diesel mixte ?? en fonction de et des coe ?cients de 0 0
Verifier et entretenir les installations techniques dun erp 0 0
Etude dangers 1 Dossier de demande d ? autorisation d ? exploiter une centrale d ? enrobage à chaud SEG ?? la Halte JOUE-EN-CHARNIE Indice Juillet ETUDE DE DANGERS CDossier de demande d ? autorisation d ? exploiter une centrale d ? enrobage à chaud SEG ?? 0 0
Ex ad 2016 Examen d ? admission a l ? EPFL Version Table des mati eres Proc ?edure de l ? examen d ? admission Organisation temporelle de l ? examen d ? admission Modalit ?es d ? inscription Contacts avec l ? EPFL Le descriptif des branches de l ? examen 0 0
Fiches eleves clis lecture avec ratus le son f 0 0
  • 45
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager