Annexes TC
Annexes TC
Annexes TC
Séances : 04
N° CAPACITES CONTENUS
graphe non orienté, sous graphe
graphe complet, graphe connexe
Reconnaitre une
1 chaine, chaine eulérienne, longueur d’une
structure
chaine
cycle
Déterminer un sommets adjacents
2
ensemble
3 Déterminer un degré d’un sommet
nombre ordre d’un graphe
1
nombre chromatique
Utiliser un algorithme de coloriage de sommets
4
algorithme (Welsh-Powell)
Mathématiser une exemples de situations problèmes faisant
5
situation appel aux graphes
Contrôle de prérequis
Exercice 1 Exercice 2
Le graphe d’une fonction f d’un Soit l’ensemble E={a; b; c; d; e; f;
ensemble E dans un ensemble F g}
1. Donner deux sous-ensembles de
est le sous-ensemble G de E×F
E de cardinal 2.
formé par les couples (x, f(x)) tels 2. Combien y-a-t-il de sous-
que x appartient à E. Si E et F sont ensembles de E de cardinal 2.
des sous-ensembles de IR, on peut 3. Soit A={c; d; f; g} et B={a; c; d;
faire une représentation graphique g} deux sous-ensembles de E
de G. Déterminer l’intersection puis la
réunion de A et B.
On considère la fonction f définie
par le tableau suivant :
x -2 -1 0 1 2 3 4
f(x
1 5 2 4 3 0 5
)
Représenter graphiquement le
graphe de f.
Situation d’apprentissage
Voici une partie de la carte d’Afrique représentant les frontières
communes pour 5 pays : Burkina Faso, Niger, Nigéria, Benin et Togo.
1. Peut-on partir du Burkina Faso et arriver au Niger en franchissant
chaque frontière une fois et une seule ? (Il n’est pas interdit de
traverser un même pays plusieurs fois)
2. Peut-on partir du Burkina Faso et y revenir en franchissant chaque
frontière une fois et une seule ?
2
Figure 1
Stratégies pédagogiques et choix didactique
La situation a un intérêt mathématique, économique et professionnel. Elle
conduit l’apprenant dans une démarche de recherche empirique de
chaînes sur un graphe pour lequel il va identifier les sommets et les
arêtes. Ce faisant, elle met en lumière les opportunités d’asseoir des
activités sur des modèles faisant recours à un graphe.
Les apprenants seront amenés à faire des conjectures en imaginant la
possibilité d'un cycle contenant toutes les arêtes d'un graphe, une seule
fois chacune. La stratégie est celle d’un travail individuel et collectif,
permettant aux élèves de partager les idées et démarche.
3
Déroulement :
Première séance
Moment didactique et Support de travail,
Activités du professeur Activités des élèves
durée matériel, trace écrite
Remobilisation des Le professeur propose des Les élèves résolvent Exercices de contrôle
prérequis ou évaluation exercices portant sur les des prérequis
diagnostique nombres et les intervalles
(éventuellement)
Durée : 10 min
Présentation de la situation - Le professeur fait lire par un Des élèves lisent Enoncé de la
élève situation ;
Durée : 5 min -Il s’assure que tous les élèves
écoutent
- il dit aux élèves d’utiliser tous
les instruments géométriques
Résolution du problème - Précise que chaque élève doit Ils résolvent le Enoncé de la situation
4
(individuellement puis en d’abord essayer de résoudre problème
groupes) individuellement (5mn) individuellement puis
- Organise les élèves en groupe en petits groupes
Durée (travail individuel) : - Contrôle les productions des - ils entrent dans une
5 min élèves et les encourage, démarche
- observe et repère les d’investigation : essais,
Durée (travail de groupe) : différentes procédures et les conjectures,
10 min difficultés des élèves de manière ajustement, vérification
à organiser la phase de synthèse - ils communiquent
- les oriente si nécessaire sans entre eux (idées,
fournir une solution procédures…),
débattent, dégagent
une position du groupe
sur la procédure et les
résultats
- chaque groupe
prépare une synthèse
de son travail
Synthèse et bilan du travail - Demande à un groupe de - un élève du groupe Enoncé de la situation
présenter son travail présente
Durée (travail collectif) : 20
min - puis choisis un autre groupe - les membres des
présentant une procédure et autres groupes
résultats différents. réagissent en prenant
position
-Instaure les débats
- fait le point - posent des questions
- fait la synthèse
Démarches des élèves :
inductive, déductive ou
5
analogique
6
Début de synthèse :
On note F1, F2, F3, F4, F5, F6, F7 les frontières comme dans le
tableau ci-dessous.
Figure 2
Introduction
Les graphes permettent de simplifier la compréhension de tout type de
réseaux (transport routier, lignes ferroviaires, web,…).
La théorie des graphes est le domaine des mathématiques qui étudie les
graphes. Elle est indispensable dans beaucoup de domaines tels que
l’informatique fondamentale et appliquée, l’optimisation, et la complexité
7
algorithmique. Elle permet la résolution de beaucoup de problèmes
pratiques concernant les réseaux routiers, le web, les réseaux sociaux,
etc.
On distingue plusieurs types de graphes (non orienté, orienté, mixte,
pondéré, …).
Dans cette leçon nous n’étudierons que des graphes non orientés. Après
avoir défini quelques éléments de base, nous étudierons les graphes
eulériens. La dernière partie de la leçon est consacrée à l’étude de
l’algorithme de Welsh-Powell permettant de faire un coloriage des
sommets d’un graphe.
Eléments de base
Définitions
Définition
- Un graphe non orienté est un ensemble de points et de lignes reliant
certains de ces points.
- Un sommet du graphe est un point du graphe. Le nombre de sommets
est appelé ordre du graphe.
- Une arête du graphe est une ligne reliant deux sommets.
sommets.
-
Un graphe simple est un graphe sans boucle tel que, entre deux
sommets, il y ait au plus une arête.
-
pas adjacents).
Exemple 1:
8
Considérons le graphe de la situation d’apprentissage :
- Son ordre est 5
- Il a 7 arêtes
- C’est un graphe simple
- d(Tg)=2, d(Bf)=3 et d(Bj)=5.
- Le sous-graphe composé des sommets Tg et Ne est stable.
Exemple 2:
Figure 3 Figure 4
9
Graphe complet
Définition
Définition
Un graphe complet est un graphe simple dont deux sommets quelconques
sont reliés par une arête.
Exemple:
Le graphe suivant est le graphe complet d’ordre 4.
Figure 5
Situation d’apprentissage
1. Dessiner les graphes complets d’ordre 2, 3 et 5.
2. Combien y a-t-il d’arêtes pour chacun de ces graphes ?
3. Combien un graphe complet ayant n sommets possède-t-il d’arêtes ?
Propriété
La taille d’un graphe complet d’ordre n est C n= .
2 n ( n−1 )
2
10
Théorème : La somme des degrés de tous les sommets d’un graphe est égale
au double de la taille du graphe
Chaînes et cycles
Définitions
Dans la situation d’apprentissage 1, le déplacement Bf-Tg-Bj-Ng-Ne-
Bj-Bf-Ne consiste à visiter les sommets en parcourant des arêtes
mise bout à bout.
Définitions
- Une chaîne, dans un graphe non orienté, est une suite d’arêtes mises
bout à bout reliant deux sommets du graphe. La longueur d’une chaîne
est le nombre d’arêtes qui la composent.
Une chaîne est notée par la liste des sommets où elle passe si le graphe
est simple.
Graphe connexe
11
Définitions
Un graphe est connexe lorsque, pour chaque paire de sommets, il existe
au moins une chaîne reliant ces deux sommets.
Situation d’apprentissage
Peut-on dessiner sans lever le crayon et en ne passant qu’une seule fois
sur chaque arête les graphes ci-dessous ?
Figure 9
Définition
- Une chaîne eulérienne est une chaîne composée de toutes les arêtes du
graphe, prises une seule fois chacune.
- Un cycle eulérien est une chaîne eulérienne dont les extrémités
coïncident.
- Un graphe qui possède un cycle eulérien est appelé graphe eulérien.
Exemple : Pour le graphe de la figure 1, la chaîne (Bf, Tg, Bj, Ng, Ne, Bj,
Bf, Ne) est une chaîne eulérienne.
Exercice d’application :
12
Justifier que :
1. le graphe de la figure 6 est eulérien puis en donner un cycle
eulérien.
2. le graphe de la figure 7 n’est pas eulérien.
Définitions
Colorier les sommets d’un graphe G, c’est leur attribuer une
couleur de façon à ce que deux sommets adjacents ne soient pas
coloriés de la même couleur. Dans cette partie, on ne considère que
des graphes simples et finis.
Définition
Le nombre minimal de couleurs nécessaires est le nombre chromatique
du graphe, noté γ ( G ).
Som A B C D E
13
met
Degr 3 2 2 3 4
é
Le plus haut degré est 4. De plus le sous-graphe formé par les sommets B,
D et E est un sous-graphe complet d’ordre 3 et il est maximal. Donc
3 ≤ γ ( G ) ≤ 4+1. On aura donc au moins trois couleurs et au plus 5.
Figure 10
1) Une liste des sommets par ordre décroissant des degrés est : E, A,
D, B, C.
2) Attribuons la couleur Rouge à E. Tous les sommets lui sont
adjacents.
3) Attribuons la couleur Verte à A (premier sommet non colorié de la
liste). Seul le sommet B ne lui est pas adjacent, donc attribuons la
couleur verte à B. Il reste les sommets D et C qui ne sont pas
coloriés.
4) Attribuons la couleur Violette à D et à C qui ne lui est pas adjacent.
Ce qui termine la coloration des sommets du graphe. On
obtient une coloration du graphe:
14
Figure 11
15
EXERCICES D’ENTRAINEMENT
Exercice1
Répondre par Vrai ou Faux.
1. Une chaîne eulérienne peut passer plusieurs fois par une même
arête.
2. Une chaîne eulérienne peut passer plusieurs fois par un même
sommet.
3. Dans un graphe connexe tous les sommets sont adjacents.
4. Un graphe non orienté est simple si et seulement s’il est sans
boucle.
5. Un graphe complet ayant 10 sommets possède 20 arêtes.
6. Soit G un graphe non orienté ayants 5 sommets dont les degrés sont
les suivants : 4 ; 2 ; 2 ; 2 ; 0. Alors G est un graphe eulérien.
Exercice 2
On considère le graphe G ci-contre.
1. Donner l’ordre et la taille de ce graphe.
2. Donner le degré de chaque sommet. Donner la liste
des sommets par ordre décroissant de degré.
3. Ce graphe est-il connexe ?
4. Ce graphe possède-t-il un cycle eulérien ? En donner
un si possible.
5. Dessiner deux sous-graphes complets de G d’ordres 2 et 3.
6. Donner les sommets de deux sous-graphes stables de G d’ordres 2
et 3.
Exercice 3
On considère le graphe G ci-contre.
1. Donner l’ordre et la taille de ce graphe.
2. Donner le degré de chaque sommet. Donner la liste des
sommets par ordre décroissant de degré.
3. Ce graphe est-il connexe ?
4. Ce graphe possède-t-il un cycle eulérien ? En donner un si
possible.
5. Compléter le tableau d’adjacence suivant en mettant une croix dans
case si l’élément de la ligne et de la colonne correspondants sont
adjacents.
A B C D E
A
B
C
16
D
E
6. Quel est l’ordre maximal d’un sous-graphe complet de G ?
7. Quel est l’ordre maximal d’un sous-graphe stable de G ?
8. Déterminer un encadrement du nombre chromatique de G.
Proposer un coloriage des sommets de G.
Exercice 4
On considère le graphe G par le tableau d’adjacence ci-dessous.
A B C D E F
A x x x
B x x x x
C x x x
D x x
E x x
F
1. l’ordre et la taille de ce graphe.
2. Donner le degré de chaque sommet. Donner la liste des sommets
par ordre décroissant de degré.
3. Ce graphe est-il connexe ?
4. Ce graphe possède-t-il un cycle eulérien ? En donner un si possible.
5. Compléter le tableau d’adjacence suivant en mettant une croix dans
case si l’élément de la ligne et de la colonne sont adjacents.
6. Quel est l’ordre maximal d’un sous-graphe complet de G ?
7. Quel est l’ordre maximal d’un sous-graphe stable de G ?
8. Déterminer un encadrement du nombre chromatique de G.
Proposer un coloriage des sommets de G.
Exercice 5
Réaliser le coloriage de la carte de la situation d’apprentissage.
PROBLEMES
Exercice 6 (Une histoire de salutation)
Pour une séance d’entraînement de danse, 13 membres du club
chorégraphique du lycée se sont retrouvés après les cours. Chaque
personne a salué un certain nombre d’autres.
1. Est-il possible que chacun ait salué exactement 7 personnes ?
2. Est-il possible que chacun ait salué exactement 4 personnes ?
17
3. On suppose que chacun a salué au plus 4 personnes. Le nombre
total de ceux qui ont salué 1 personne et 3 personnes peut-il être
impair ?
A B C D E F G H
A x x x x x
B x x x x
C x x x x x
D x x x x
E x x x x
F x x x
G x x x x
H x x x
Une croix signifie que les poissons ne peuvent pas cohabiter ensemble
dans un même aquarium. Il se demande combien d’aquariums il doit
construire et sollicite ton aide.
Déterminer le nombre d’aquariums qu’il doit construire.
18
La carte administrative d’une ville est
représentée ci-contre où les quartiers sont A,
B, C, D, E, F, G, H et I. Le maire de cette ville
souhaite colorier cette carte de sorte que les
quartiers ayant une frontière commune
n’aient pas la même couleur avec un nombre
minimal γ de couleurs.
Après avoir déterminer un encadrement de γ
proposer un tel coloriage.
EXPOSE
Exercice 10
Le célèbre problème des sept ponts de Königsberg étudié par Euler en
1736 est souvent considéré comme précurseur de la théorie des graphes
même si l’un des premiers ouvrages sur le sujet n’ait été écrit que 200
ans plus tard. Faire un exposé de 15 min le problème des ponts de
Königsbergn (présentation du problème et sa résolution).
Bibliographie :
1. Alain Bretto et al. Éléments de théorie des graphes. Springer, 2012.
2. Jean-Claude Fournier. Théorie des graphes et applications. Springer,
2e édition.
3. Irène Larramendy Valverde et Alain Marie-Jeanne. Introduction à la
théorie des graphes, Cours et exercices corrigés. Ellipse, 2018.
4. Quelques sites:
Pierre Arnoux et al. Graphes Pour la Terminale ES 2002
https://dept-info.labri.fr/~baudon/Master/MEEF/polygraph.pdf
Un petit résumé de cours et exercices :
https://dept-info.labri.fr/~baudon/Master/MEEF/graphes-Gelineau-
Lyon1.pdf
http://math.univ-lyon1.fr/~gelineau/CAPES/graphes_exos.pdf
19
20
Annexe 2 : Situations d’apprentissage/d’intégration
Leçon : Arithmétique
Situation 1
Lors de son anniversaire mademoiselle Frida veut offrir des colis a des
invités. Le colis qu’elle désire offrir contient trois bonbons et deux
biscuits. Frida dispose un lot de 120 bonbons et 180 biscuits. Amivi sa
sœur qui l’aide à faire les colis, après réflexions lui dit qu’elles ne
peuvent faire que 60 colis.
Situation 2
Ton père veut recouvrir sa terrasse rectangulaire de 4,29m sur 3,63m
avec des pavés carrés dont la longueur en centimètres du coté est un
nombre entier naturel. Il souhaite en plus utiliser le moins de pavés
possibles pouvant couvrir exactement la terrasse
Détermine pour ton père le nombre de pavés à commander.
Situation 3
Deux voitures A et B partent en même temps de CIMTOGO et décident de
faire le circuit CIMTOGO – échangeur agoe – dekon – CIMTOGO
plusieurs. La voiture A fait le tour du circuit en 40 min alors que la
voiture B fait le même tour en 1h.
Un passant affirme que la voiture A ne peut jamais rattraper la voiture B.
Es-tu même avis que lui ?
21
Deux amis discutent la forme et le nombre de solutions de l’équation
( z−1 )5= ( z +1 )5. Le premier Aboda dit que les solutions sont au nombre de 4
et toutes réelles. Le second Foli dit qu’il y a 5 solutions imaginaires purs.
Ils t’appellent à trancher.
Situation 4
Un de tes grands frères du quartier te dit qu’il a lu dans le concours
d’olympiades de 2022 une question qui demande de répondre par vrai ou
faux :
Si trois points A(a), B(b) et C(c) d’affixes non nuls sont tels que a+ b+c=0
et |a|=|b|=¿ c∨¿ alors le triangle ABC n’est pas équilatéral.
Il te dit qu’il a lu plusieurs fois mais toujours indécis. Avec tes
connaissances dans les nombres complexes aide-le à faire le bon choix.
Leçon : Conique
Situation 1
Pour aménager la cour de leur établissement, les élèves se proposent de
créer un espace vert délimité par l’ensemble d’équation
( x−2 )2 y 2
( Γ ) + =1
, en se rapportant à un repère orthonormé ( O , I , J ).
9 4
Le professeur de maths fait observer par ailleurs que si on fixe les deux
3
Situation 2
Un camionneur ignore le volume exact de son camion-citerne mais une
inscription lue sur le fût indique c’est un cylindre droit de hauteur OA
dont la base est une ellipse d’équation
( x−3 )2 y 2
+ =1
Pour déterminer sa capacité on se rend compte qu’on doit considérer le
4 9
22