CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 1 SÉQUENCE 2 GRAPHES S

CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 1 SÉQUENCE 2 GRAPHES SÉANCE 9 TD6 : Détermination du niveau d’un sommet et d’un graphe (partie 2/2) Contenu Exercices. ...................................................................................................................................................... 1 Corrections................................................................................................................................................... 4 — — Exercice 1 (D’après un sujet de l’épreuve de mathématiques pour l’information du BTS IG session 2011) On considère le graphe orienté G de sommets A, B, C, D, E et F pris dans cet ordre, dont la matrice d’adjacence est : 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 M æ ö ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ = ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç è ø 1) Écrire le tableau des prédécesseurs pour les sommets du graphe G. 2) Déterminer le niveau de chacun de ces sommets. 3) Dessiner le graphe G en ordonnant les sommets par niveaux. — — Exercice 2 (D’après un sujet de l’épreuve de mathématiques pour l’information du BTS SIO session 2013) Pour obtenir un diplôme, des étudiants doivent valider quatre modules différents notés A, B, C et D. Les modules nécessitent certaines connaissances et doivent donc être validés en respectant les règles suivantes : — Une fois le module A validé, on peut valider les modules B, C ou D. — Une fois le module B validé, on peut valider le module D. — Une fois le module C validé, on peut valider les modules B ou D. — Aucun module ne peut être validé après le module D. solution CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 2 On définit ainsi un graphe orienté de sommets A, B, C et D, pris dans cet ordre, et dont la matrice d’adjacence est la matrice M : 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 M æ ö ÷ ç ÷ ç ÷ ç ÷ ç = ÷ ç ÷ ç ÷ ÷ ç ÷ ç è ø 1) Écrire le tableau des prédécesseurs pour les sommets du graphe G. 2) Déterminer le niveau de chacun de ces sommets. 3) Dessiner le graphe G en ordonnant les sommets par niveaux. — — Exercice 3 (D’après un sujet de l’épreuve de mathématiques pour l’information du BTS SIO session 2015) On sait qu’il y a des chemins de : — A vers B et A vers D. — B vers D et B vers E. — D vers C. — E vers C et E vers F. — F vers C. 1) Écrire le tableau des prédécesseurs pour les sommets du graphe G. 2) Déterminer le niveau de chacun de ces sommets. 3) Dessiner le graphe G en ordonnant les sommets par niveaux. — — Exercice 4 (D’après un sujet de l’épreuve de mathématiques pour l’information du BTS SIO session 2016) La planification d’un projet de création d’un robot requiert les sept tâches listées ci-dessous. Description de la tâche Tâches Prédécesseurs Achat de la structure A - Modélisation numérique B A Montage de la maquette C A, D Achat des capteurs D - Développement du programme E D Test du programme sur la maquette et ajustements F C, E Négociation des frais de fabrication G B, F 1) Écrire le tableau des successeurs pour les sommets du graphe G. 2) Déterminer le niveau de chacun de ces sommets. 3) Dessiner le graphe G en ordonnant les sommets par niveaux. solution solution solution CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 3 — — Exercice 5 (D’après un sujet de l’épreuve de mathématiques pour l’information du BTS SIO session 2017) Cinq joueurs, notés A, B, C, D et E, jouent régulièrement à un jeu en ligne. Chaque partie de ce jeu oppose deux adversaires. Le tableau suivant donne, pour chacun des cinq joueurs, la liste des adversaires qu’il a déjà battus. Le joueur A déjà battu A B, D B C C B, D D E E D Ainsi, par exemple, le joueur C a déjà battu les joueurs B et D. 1)  En considérant le tableau précèdent comme un tableau de successeurs, représenter la situation par un graphe orienté G, dans lequel un arc relie un sommet x à un sommet y si le joueur x a déjà battu le joueur y. 2) Écrire la matrice d’adjacence M du graphe G. 3) Recopier et compléter le tableau des prédécesseurs dans le graphe G. Le joueur A déjà ...... A B C D E 4) Le graphe G contient-il un circuit ? Contient-il un chemin hamiltonien ? Justifier les réponses. 5) Quelles sont les conséquences sur le niveau des sommets ? — — Exercice 6 (D’après un sujet de l’épreuve de mathématiques pour l’information du BTS IG session 2003) A, B, C, D, E, F et G sont les différents points d’une ville reliés par des lignes de transport en commun. On sait qu’il y a des lignes : — De A vers B et de A vers G. — De B vers E. — De C vers F et de C vers G. — De D vers A et de D vers C — De F vers B. — De G vers B. 1) Écrire le tableau des prédécesseurs pour les sommets du graphe G 2) Déterminer le niveau de chacun de ces sommets. 3) Dessiner le graphe G en ordonnant les sommets par niveaux. solution solution CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 4 CORRECTIONS — — Exercice 1 1) Sommets Prédécesseurs - A, D, E C E D A E A F B, C, D 2)  On utilise la méthode expliquée dans le cours. Le sommet A n’a pas de prédécesseur il est de niveau 0. Puis on supprime tous les A. Sommets Prédécesseurs - - B D, E C E D - E - F B, C, D Les sommets D et E n’ont pas de prédécesseur ils sont de niveau 1. Puis on supprime tous les D et E. Sommets Prédécesseurs - - B - C - - - - - F B, C Les sommets B et C n’ont pas de prédécesseur ils sont de niveau 2. Puis on supprime tous les B et C. Sommets Prédécesseurs - - - - - - - - - - F - Le sommet F n’a pas de prédécesseur il est de niveau 3. CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 5 Niveaux Sommet(s) 0 A 1 D, E 2 B, C 3 F 3) — — Exercice 2 1) Sommets Prédécesseur(s) A - B A, C C A D A, B, C 2)  On utilise la méthode expliquée dans le cours. Le sommet A n’a pas de prédécesseur il est de niveau 0. Puis on supprime tous les A. Sommets Prédécesseur(s) - - B C C - D B, C Le sommet C n’a pas de prédécesseur il est de niveau 1. Puis on supprime tous les C. Sommets Prédécesseur(s) - - B - - - D B Le sommet B n’a pas de prédécesseur il est de niveau 2. Puis on supprime tous les B. CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 6 Sommets Prédécesseur(s) - - - - - - D - Le sommet D n’a pas de prédécesseur il est de niveau 3. Niveaux Sommet(s) 0 A 1 C 2 B 3 D 3) — — Exercice 3 1) Sommets Prédécesseur(s) A - B A C D, E, F D A, B E B F E 2) On utilise la méthode expliquée dans le cours. Le sommet A n’a pas de prédécesseur il est de niveau 0. Puis on supprime tous les A. Sommets Prédécesseur(s) - - B - C D, E, F D B E B F E Le sommet B n’a pas de prédécesseur il est de niveau 1. Puis on supprime tous les B. CNED – BTS SIO – MATHÉMATIQUES – SÉQUENCE 2 – Séance 9 – 7 Sommets Prédécesseur(s) - - - - C D, E, F D - E - F E Les sommets D et E n’ont pas de prédécesseur ils sont de niveau 2. Puis on supprime tous les D et E. Sommets Prédécesseur(s) - - - - C F - - - - F - Le sommet F n’a pas de prédécesseur il est de niveau 3. Puis on supprime tous les F. Sommets Prédécesseur(s) - - - - C - - - - - - - Le sommet C n’a pas de prédécesseur il est de niveau 4. Niveauxs Sommet(s) 0 A 1 B 2 D, E 3 F 4 C 3) CNED – BTS SIO – MATHÉMATIQUES – uploads/Litterature/ 876m1tewb1520.pdf

Tags
littérature sommets niveau prédécesseur sommet mathématiques
Documents similaires
  • 46
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager