Terminale Option Experte / Annales graphes 9 exercices (dont 7 corrigés)

a
1. Graphe E.7672 Un jardinier doit décorer un jardin privatif en répartissant 10 variétés de fleurs notées V 1 à V 10 dans différents parterres. Certaines de ces variétés ne peuvent pas être plantées ensemble pour des raisons diverses (tailles, couleurs, conditions climatiques,. . . ) et ces incompatibilités sont résumées dans le tableau ci-dessous (une croix indique qu’il y a incompatibilité entre deux variétés) . Fleur V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9 V 10 V 1 × × × V 2 × × × × V 3 × × × × V 4 × × × × × V 5 × × × × V 6 × × × V 7 × × V 8 × × × V 9 × × V 10 × × 1 Représenter par son graphe G la situation. 2 a Trouver un sous-graphe complet d’ordre 4 et le dessiner. b Que peut-on en déduire pour la coloration du graphe G ? Quel est le nombre minimum de parterres que le jar-dinier doit décorer? 3 a Classer les sommets de G par ordre de degré décrois-sant. b En déduire un encadrement de C , nombre chromatique de G . 4 a Procéder à la colorisation du graphe G . b Que peut-on en déduire pour le nombre C ? Justifier avec soin. c Proposer un ensemble de parterres avec une répartition adaptée des variétés de fleurs. E.7674 Un jardinier possède un terrain bien ensoleillé avec une partie plus ombragée. Il décide d’y organiser des parcelles où il plantera 8 variétés de légumes : de l’ail (A) , des courges (Co) , des choux (Ch) , des poireaux (Px) , des pois (Po) , des pommes de terre (Pt) , des radis (R) et des tomates (T) . Il consulte un almanach où figurent des incompatibles de plantes, données par les deux tableaux : Expositions incompatibles de plantes Plantes d’ombre par-tielle Plantes de plein soleil poids Radis Choux Tomates Courges Par exemple: les pois sont incompatibles avec les choux, les tomates et les courges. Associations incompat-ibles de plantes dans une même parcelle poids ail, poireaux pommes de terre courges, radis et to-mates choux tomates, ail, poireaux et courges courges tomates Par exemple: les pois sont incompatibles avec l’ail et les poireaux Pour ternir compte de ces incompatibilités le jardinier décide de modéliser la situation sous la forme d’un graphe de huit sommets, chaque sommet représentant un légume. 1 Sur la feuille annexe : compléter le graphe mettant en évidence les incompatibilités d’exposition ou les associ-ations incompatibles indiquées dans les deux tableaux ci-dessus. 2 Calculer la somme des degrés des sommets du graphe, en déduire le nombre de ses arêtes 3 Rechercher un sous-graphe complet d’ordre 4 , qu’en déduit-on pour le nombre chromatique du graphe? 4 Donner le nombre chromatique du graphe et l’interpréter en nombre minimum de parcelles que le jardinier devra créer. 5 Donner une répartition des plantes par parcelle de façon à ce que chaque parcelle contienne exactement deux types de plantes et que le nombre de parcelles soit minimum. 6 Donner une répartition des plantes de façon à ce qu’une parcelle contienne trois plantes et que le nombre de par-celles soit minimum. 2. Graphe probabiliste E.6399 Les services commerciaux d’une grande surface de produits alimentaires ont défini un profil de client qui a été appelé ˇ consommateur bio ı. Sur la base d’observations réalisées les années précédentes, il a été constaté que : 90 % des clients ˇ consommateur bio ı maintenaient cette pratique l’année suivante ; 15 % des clients n’ayant pas le profil de ˇ consomma-teur bio ı entraient dans la catégorie ˇ consommateur bio ı l’année suivante. On suppose que cette évolution se poursuit d’une année à l’autre à partir de 2013 , année au cours de laquelle il a été constaté que 20 % des clients ont le profil ˇ consommateur bio ı. Par un tirage aléatoire effectué tous les ans, on choisit un client de cette grande surface. Pour tout nombre entier naturel n , on note : b n : la probabilité que le client choisi lors de l’année 2013+ n soit un ˇ consommateur bio ı ; c n : la probabilité que le client choisi lors de l’année 2013+ n ne soit pas un ˇ consommateur bio ı. https://chingmath.fr sacados/7672 Antilles-Guyane Juin 2006 sacados/7674 chapExoCorrec/6399 sacados/6399 Antilles-Guyane Juin 2014
P n : la matrice ligne b n c n donnant l’état proba-biliste lors de l’année 2013+ n . 1 a Représenter la situation par un graphe probabiliste de sommets B et C où B correspond à l’état ˇ consom-mateur bio ı. b Donner P 0 l’état probabiliste en 2013 et la matrice M de transition correspondant à ce graphe, les sommets B et C étant classés dans cet ordre. c On donne la matrice M 2 : M 2 = 0 ; 825 0 ; 175 0 ; 2625 0 ; 7375 En précisant la méthode de calcul, déterminer la prob-abilité que le client choisi en 2015 soit un ˇ consomma-teur bio ı. d Déterminer l’état stable b c du graphe proba-biliste. 2 Le directeur du supermarché affirme que, dans un futur proche, plus de la moitié de sa clientèle aura le profil ˇ consommateur bio ı. a Recopier et compléter l’algorithme suivant afin qu’à la fin de son exécution la variable N ait pour valeur le nombre minimal d’années pour que l’affirmation du directeur soit vérifiée: N ← 0 B ← 0;2 C ← 0;8 Tant que ... B ← 0;9 × B + 0;15 × C C ← 1 − B N ← N+1 Fin Tant que E.6401 Alice participe à une compétition de tir à l’arc; elle effectue plusieurs lancers de flèches. Lorsqu’elle atteint la cible à un lancer, la probabilité qu’elle atteigne la cible au lancer suivante est égale à 0 ; 9 . Lorsqu’elle a manqué la cible à un lancer, Alice se déconcen-tre et la probabilité qu’elle atteigne la cible au lancer suivante est égale à 0 ; 4 . On suppose qu’au premier lancer, elle a autant de chances d’atteindre la cible que de la manquer. Pour tout nombre entier naturel n strictement positif, on note : a n la probabilité qu’Alice atteigne la cible au n -ième lancer; b n la probabilité qu’Alice manque la cible au n -ième lancer; P n = a n b n la matrice ligne traduisant l’état proba-biliste au n -ième lancer. 1 a Représenter la situation par un graphe probabiliste de sommets A et B ( A représentant l’état ˇ Alice at-teint la cible ı et B l’état ˇ Alice manque sa cible ı) . b Indiquer la matrice de transition M associée à ce graphe. On prendra les sommets A et B dans l’ordre ( A ; B ) . c Justifier que : P 1 = 0 ; 5 0 ; 5 ; P 2 = 0 ; 65 0 ; 35 2 a Montrer que, pour tout nombre entier n strictement positif : a n +1 = 0 ; 9 · a n + 0 ; 4 · b n b En déduire que, pour tout nombre entier n strictement positif : a n +1 = 0 ; 5 · a n + 0 ; 4 3 a On considère ci-dessous la fonction f d’un algo-rithme prenant pour paramètre l’argument n qui est un entier naturel supérieur ou égal à 2 . Fonction f(n) a ← 0;5 b ← 0;5 Pour i allant de 2 à n a ← ... × a+ ... b ← 1 − a Fin Pour Renvoyer ( a ; b) Compléter la fonction f afin qu’à la fin de son exécu-tion, le couple renvoyé par cette fonction indique l’état probabiliste au n -ième lancer. b Déterminer le couple de valeurs renvoyées lorsque cette fonction est appelée avec pour argument n =5 . 4 a On considère la suite u n définie pour tout nombre entier naturel n strictement positif par : u n = a n − 0 ; 8 . Montrer que la suite u n est une suite géométrique dont on précisera la raison et le premier terme. b Donner l’expression de u n en fonction de n , puis en déduire que pour tout nombre entier naturel n stricte-ment positif : a n = 0 ; 8 − 0 ; 3 × 0 ; 5 n − 1 . c À long terme, que peut-on penser de la probabilité qu’Alice atteigne la cible? https://chingmath.fr chapExoCorrec/6401 sacados/6401
d Par quelle autre méthode aurait-on trouvé le résultat précédent? E.6403 Pour satisfaire ses adhérents, un club de sport a instauré trois niveaux d’apprentissage : DEBUTANT (D), CONFIRME (C) et EXPERT (E) Au 1 er septembre 2012 , lors de l’inscription, le club comptait : 30 % de débutants ; 50 % de confirmés ; 20 % d’experts. D’une année sur l’autre, on constate que : parmi les adhérents de niveau débutant, 40 % restent à ce niveau et 60 % passent au niveau confirmé ; parmi les adhérents de niveau confirmé, 60 % restent à ce niveau et 40 % passent au niveau expert ; parmi les adhérents de niveau expert, 80 % restent à ce niveau, 10 % redescendent au niveau confirmé et les autres 10 % préfèrent reprendre les bases au niveau débu-tant. On considère qu’il n’y a pas de nouveaux venus ni de départs dans le club. Soit P n = d n c n e n la matrice ligne décrivant l’état probabiliste de la répartition parmi les trois niveaux d’apprentissage D , C et E au 1 er septembre de l’année 2012+ n pour tout entier naturel n . 1 a Donner sans justification la matrice P 0 . b Traduire la situation par un graphe probabiliste de sommets D , C et E . On donne la matrice carrée M de transition en respectant l’ordre D , C , E des sommets. M = 0 ; 4 0 ; 6 0 0 0 ; 6 0 ; 4 0 ; 1 0 ; 1 0 ; 8 Dans la suite de l’exercice, on pourra utiliser les résultats suivants (résultats arrondis au millième) : M 5 = 0 ; 085 0 ; 331 0 ; 584 0 ; 097 0 ; 293 0 ; 610 0 ; 104 0 ; 298 0 ; 598 M 10 = 0 ; 100 0 ; 299 0 ; 601 0 ; 100 0 ; 300 0 ; 600 0 ; 100 0 ; 300 0 ; 600 2 Dans cette matrice, on lit 0 ; 6 et 0 ; 8 en italique gras. a Préciser, à l’aide d’une phrase, à quoi correspondent ces deux valeurs en lien avec la situation étudiée. b Calculer P 1 . c Déterminer la répartition prévisible, en pourcentages, des adhérents dans ce club de sport au 1 er septembre 2017 . Les résultats seront donnés à 0 ; 1 % près. 3 a En calculant P 10 , émettre une conjecture sur la ma-trice P correspondant à l’état probabiliste stable. b Vérifier cette conjecture. c Quelle conclusion peut-on en tirer pour la répartition des adhérents? E.6404 La première semaine de l’année, le responsable de la communication d’une grande entreprise propose aux employés de se déterminer sur un nouveau logo, le choix devant être fait par un vote en fin d’année. Deux logos, désignés respectivement par A et B , sont soumis au choix. Lors de la présentation qui se déroule la première semaine de l’année, 24 % des employés sont favorables au logo A et tous les autres employés sont favorables au logo B . Les discussions entre employés font évoluer cette répartition tout au long de l’année. Ainsi, 9 % des employés favorables au logo A changent d’avis la semaine suivante et 16 % des employés favorables au logo B changent d’avis la semaine suivante. Pour tout n , n 1 , on note : a n la probabilité qu’un employé soit favorable au logo A la semaine n ; b n la probabilité qu’un employé soit favorable au logo B la semaine n ; P n la matrice a n b n traduisant l’état probabiliste la semaine n . On a donc, pour tout n 1 : a n + b n = 1 ; P 1 = 0 ; 24 0 ; 76 1 Traduire la situation par un graphe probabiliste de som-mets A et B . 2 Déterminer la matrice de transition M de ce graphe, en rangeant les sommets dans l’ordre alphabétique. 3 a À l’aide de la relation P n +1 = P n × M , exprimer, pour tout n 1 , a n +1 en fonction de a n et de b n . b En déduire que l’on a, pour tout n 1 : a n +1 = 0 ; 75 · a n + 0 ; 16 . 4 À l’aide de la calculatrice, donner, sans justifier, la prob-abilité à 0 ; 001 près qu’un employé soit favorable au logo A la semaine 4 . 5 On note P = a b l’état stable de la répartition des employés. a Déterminer un système de deux équations que doivent vérifier a et b . b Résoudre le système obtenu dans la question précé-dente. c On admet que l’état stable est P = 0 ; 64 0 ; 36 . In-terpréter le résultat. 6 On considère l’algorithme suivant : A ← 0;24 N ← 0 Tant que A<0;639 N ← N+1 A ← 0;75 × A+0;16 Fin Tant que Donner, après l’exécution de l’algorithme, une interpréta-tion de la valeur de la variable N (on ne demande pas de donner la valeur de N en fin d’exécution de l’algorithme) . https://chingmath.fr chapExoCorrec/6403 sacados/6403 chapExoCorrec/6404 sacados/6404
E.6408 Les sites internet A , B , C ont des liens entre eux. Un internaute connecté sur un de ces trois sites peut, à toutes les minutes, soit y rester, soit utiliser un lien vers un des deux autres sites : Pour un internaute connecté sur le site A , la probabilité d’utiliser le lien vers B est de 0 ; 2 et celle d’utiliser le lien vers C est de 0 ; 2 . Pour un internaute connecté sur le site B , la probabilité d’utiliser le lien vers A est de 0 ; 1 et celle d’utiliser le lien vers C est de 0 ; 4 . Pour un internaute connecté sur le site C , la probabilité d’utiliser le lien vers A est de 0 ; 2 mais il n’y a pas de lien direct vers B . L’unité de temps est la minute, et à un instant t =0 , le nom-bre de visiteurs est, respectivement sur les sites A , B et C : 100 , 0 et 0 . On représente la distribution des internautes sur les trois sites après t minutes par une matrice N t ; ainsi, N 0 = 100 0 0 . On suppose qu’il n’y a ni déconnexion pendant l’heure de (de t =0 à t =60 ) ni nouveaux internautes visiteurs. 1 Représenter le graphe probabiliste de sommets A , B et C correspondant à la situation décrite. 2 Écrire la matrice M de transition associée à ce graphe (dans l’ordre A , B , C ) . 3 On donne : M 2 = 0 ; 42 0 ; 22 0 ; 36 0 ; 19 0 ; 27 0 ; 54 0 ; 28 0 ; 04 0 ; 68 M 20 ≈ 0 ; 3125 0 ; 125 0 ; 5625 0 ; 3125 0 ; 125 0 ; 5625 0 ; 3125 0 ; 125 0 ; 5625 Calculer N 2 . Interpréter le résultat obtenu. 4 Calculer N 0 × M 20 . Conjecturer la valeur de l’état stable et interpréter la réponse. 5 Un des internautes transmet un virus à tout site qu’il visitera. Il se connecte initialement sur le site C et commence sa navigation. À l’instant t =0 , le site C est donc infecté. a Quelle est la probabilité qu’à l’instant t =1 le site A soit infecté? b Quelle est la probabilité qu’à l’instant t =2 les trois sites soient infectés? E.6421 Dans un pays, seulement deux opérateurs de téléphonie mobile SAFIR et TECIM proposent la 4G (standard de transmission de données) . Une étude a montré que d’une année à l’autre: 41 % des clients de l’opérateur SAFIR le quittent pour l’opérateur TECIM ; 9 % des clients de l’opérateur TECIM le quittent pour l’opérateur SAFIR; Aucun client ne renonce à l’utilisation de la 4G. Cette situation peut être modélisée par un graphe probabiliste G de sommets S et T où : S est l’événement ˇ l’utilisateur de la 4G est un client de l’opérateur SAFIR ı ; T est l’événement ˇ L’utilisateur de la 4G est un client de l’opérateur TECIM ı ; On note P n = s n t n la matrice ligne de l’état probabiliste pour l’année 2014+ n . Dans cet exercice, on se propose de savoir si l’opérateur TECIM atteindra l’objectif d’avoir comme clients au moins 80 % de la population utilisatrice de la 4G. Partie A 1 Dessiner le graphe probabiliste G . 2 On admet que la matrice de transition du graphe G en considérant les sommets dans l’ordre S et T est M = 0 ; 59 0 ; 41 0 ; 09 0 ; 91 On note P = a b la matrice ligne correspondant à l’état stable de ce graphe G . a Montrer que les nombres a et b sont les solutions du système : 0 ; 41 · a − 0 ; 09 · b = 0 a + b = 1 b Résoudre le système précédent. 3 On admet que a =0 ; 18 et b =0 ; 82 . Déterminer, en justifiant, si l’opérateur TECIM peut es-pérer atteindre son objectif. Partie B En 2014 , on sait que 35 % des utilisateurs de la 4G sont des clients de l’opérateur SAFIR et que 65 % sont des clients de l’opérateur TECIM. Ainsi : P 0 = 0 ; 35 0 ; 65 . 1 Déterminer la répartition des clients de la 4G au bout de 2 ans. 2 Montrer que, pour tout entier naturel n , on a: t n +1 = 0 ; 5 · t n + 0 ; 41 3 Pour déterminer au bout de combien d’années, l’opérateur TECIM atteindra son objectif, on a com-mencé par élaborer l’algorithme ci-dessous. Recopier et compléter les lignes ‘ .4 et ‘ .5 afin qu’en fin d’exécution la valeur de la variable N donne le résultat attendu. ‘ .1 T ← 0;65 ‘ .2 N ← 0 ‘ .3 Tant que T<0;80 ‘ .4 T ← ... ‘ .5 N ← ... ‘ .6 Fin Tant que 4 On considère la suite u n définie pour tout entier na-turel n par : u n = t n − 0 ; 82 . a Montrer que la suite u n est une suite géométrique de raison 0 ; 5 . Préciser son premier terme. b En déduire que : t n = − 0 ; 17 × 0 ; 5 n + 0 ; 82 c Résoudre dans l’ensemble des entiers naturels l’inéquation: − 0 ; 17 × 0 ; 5 n + 0 ; 82 0 ; 80 . d Interpréter ce résultat dans le contexte de l’énoncé. https://chingmath.fr chapExoCorrec/6408 sacados/6408 chapExoCorrec/6421 sacados/6421 Liban Mai 2015
3. Graphe pondéré et probabiliste E.6411 Une étude est réalisée chaque hiver sur une population composée de personnes qui peuvent pratiquer le ski de piste ou le snowboard. L’élève révèle que : Si une personne pratique le ski de piste, alors la probabil-ité qu’elle pratique le snowboard l’hiver suivant est égale à 0 ; 2 . Si une personne pratique le snowboard, alors la probabil-ité qu’elle pratique le ski de piste l’hiver suivant est égale à 0 ; 3 . On note S l’état: ˇ la personne pratique le ski de piste ı et S l’état: ˇ la personne pratique le snowboard ı. On note également pour tout entier naturel n : p n la probabilité qu’une personne pratique le ski de piste lors du n -ième hiver; q n la probabilité qu’une personne pratique le snowboard lors du n -ième hiver; P n = p n q n la matrice ligne donnant l’état proba-biliste du système lors du n -ième hiver. On suppose que la population initiale ne comporte que des personnes pratiquant le ski de piste, on a donc P 0 = 1 0 . Partie A 1 Représenter la situation à l’aide d’un graphe probabiliste de sommets S et S . 2 a Donner la matrice de transition M de ce graphe probabiliste. b Calculer M 2 . c Déterminer l’état probabiliste P 2 . 3 Montrer que pour tout entier naturel n , on a: p n +1 = 0 ; 5 · p n + 0 ; 3 . 4 On considère l’algorithme suivant : Variables ‘ . 1 J et N sont des entiers naturels ‘ . 2 p est un nombre réel Entrée ‘ . 3 Saisir N Initialisation ‘ . 4 p prend la valeur 1 Traitement ‘ . 5 Pour J allant de 1 à N ‘ . 6 p prend la valeur . . . . . . . . . ‘ . 7 Fin Pour Sortie ‘ . 8 Afficher p Recopier et compléter la ligne 6 de cet algorithme afin d’obtenir la probabilité p n . Partie B On considère, pour tout entier naturel n , l’événement S n : ˇ la personne pratique le ski de piste lors du n -ième hiver ı. La probabilité de l’événement S n est notée p S n . On a donc : p n = p S n . On sait d’après la partie A que pour tout entier naturel n : p n +1 = 0 ; 5 · p n + 0 ; 3 Soit la suite u n définie pour tout entier naturel n par : u n = p n − 0 ; 6 . 1 Démontrer que la suite u n est une suite géométrique de raison 0 ; 5 et préciser la valeur de u 0 . 2 En déduire l’expression de u n en fonction de n puis l’expression de p n en fonction de n . 3 Déterminer la limite de la suite p n et interpréter le résultat. Partie C Une partie du domaine skiable est représentée par le graphe ci-dessous. Le sommet A représente le haut des pistes de ski et le sommet I en représente le bas. Les sommets B , C , D , E , F , G et H représentent des points de passages. Chacune des arêtes est pondérée par la distance, en centaine de mètres, entre deux sommets. Déterminer, à l’aide de l’algorithme de Dijkstra, la distance minimale permettant de relier le sommet A au sommet I . https://chingmath.fr chapExoCorrec/6411 sacados/6411 ABCDEFGHI7162113181581285651218713719