III-3.2.Description du
chapitre « Initiations aux graphes »
Le chapitre « Initiation aux graphes »
est, à l'instar des autres chapitres, organisé en cinq
rubriques:
-Pour
commencer.
-Cours :
v Notion de
graphe.
v
Représentation d'une situation à l'aide d'un
graphe.
v Lemme de
poignées de mains.
v circulation sur un
graphe.
v Coloriage d'un
graphe.
v Recherche d'une plus
courte chaîne.
-Utilisation
des TIC.
-Exercices et
problèmes.
-Math culture.
Nous allons décrire, une à une, toutes ces
rubriques :
o La rubrique « Pour
commencer » :
Elle est composée de cinq activités qui motivent
certes l'élève à s'intéresser aux graphes mais ne
traitent en aucun cas les connaissances antérieures indispensables
à l'élève comme annoncé par les auteurs dans la
préface à la page 2 du livre. En fait, dans cette page, les
auteurs indiquent que « dans cette rubrique sont proposées
des activités dans l'intention de faire le point sur les connaissances
antérieures indispensables à l'élève pour aborder
un nouveau chapitre ». A notre avis, les raisons de cette
absence de traitement des connaissances antérieures sont :
- La théorie des graphes est introduite pour la
première fois dans le cursus scolaire de l'élève et, en
conséquence, on ne demande pas à un élève de
mobiliser des connaissances antérieures à propos de cette
théorie.
- L'objet du chapitre est une simple initiation aux graphes
sans aucune démonstration des théorèmes et, donc, il n'y a
pas de pré-requis du même domaine pour ce chapitre.
Parmi les cinq activités proposées dans cette
rubrique nous trouvons quatre activités qui introduisent la notion de
coloration d'un graphe (ce sont les activités 1, 2, 4 et 5) et une
activité qui évoque les graphes eulériens
l'activité 3).
o La rubrique
« cours » :
La sous rubrique :« Notion de
graphe» :
Cette sous rubrique contient dix neuf activités dont
cinq intitulées « exercices ». Les auteurs
n'indiquent pas dans l'introduction les différences entre ce qu'ils
appellent « activité » et ce qu'ils désignent
par « exercice ». Cependant, nous avons noté que les
activités traitent essentiellement des situations de la vie courante
alors que les exercices (à l'exception de l'exercice du bas de la page
87), et qui ne devrait pas figurer dans cette rubrique, servent à
approfondir une notion institutionnalisée. On observe, en outre, que
l'activité 2 de la page 86 pose un problème d'existence de
boucles : un verbe est conjugué au même temps que lui
même. Or, les boucles ont une existence dans les graphes multiples, qui
ne figurent pas au programme et pas dans les graphes simples, objets du
programme de la troisième année économie et gestion.
La sous rubrique « coloration d'un
graphe » :
Dans cette rubrique, on trouve huit activités dont un
seul intitulé « exercice ». L'activité 1 de
la page 91 est la plus importante du point de vue moments didactiques car, non
seulement elle présente une situation de gestion de conflits,
principale caractéristique des problèmes faisant recours à
la modélisation et au coloriage des graphes, mais surtout elle introduit
les éléments technologiques servant à sa
résolution. En fait, si nous suivons la logique des séquences des
questions nous allons constater qu'il s'agit des étapes à suivre
pour réaliser la tâche annoncée au début par la
phrase « on se propose de résoudre le problème P
suivant : Quel est le nombre d'aquariums
nécessaires ? ». Nous sommes, ainsi, en présence
d'une activité servant au second moment didactique, c'est-à-dire
celui de l'exploration du type de tâche et de l'élaboration d'une
technique appropriée.
La sous rubrique « Recherche d'une plus courte
chaine » :
Cette rubrique est composée de cinq activités.
L'activité 3 de la page 95 est incontournable car elle explique, en
fait, comment fonctionne l'algorithme de Moore-Djikstra. L'activité 1
introduit la notion de graphe pondéré. Il s'agit de trouver le
plus court chemin entre Bizerte et Le Kef à partir du réseau
routier entre cinq villes : Le Kef, Tabarka, Jendouba, Bizerte et Tunis.
La seconde activité présente une situation où l'on cherche
à minimiser la somme dépensée en péage dans
réseau autoroutier. Dans l'activité 3, il est question
d'illustrer le mécanisme de l'algorithme de Moore-Djikstra sur un cas de
propagation d'un virus dans un réseau d'ordinateurs. L'activité 4
est une application de l'algorithme de Moore-Djikstra sur un cas d'un
réseau routier. Dans l'activité 5, nous avons un autre cas
d'application de l'algorithme de Moore-Djikstra sur la minimisation du cout de
livraison d'un commerçant.
La rubrique « Utilisation des
TIC » :
Dans cette rubrique, on trouve deux activités qui font
suite à deux travaux pratiques (pages 104-106). Ces dernières
sont une sorte de guide méthodologique de l'utilisation du logiciel en
ligne gratuit Grin40. Ce logiciel permet de créer, modifier et faire un
travail de recherche sur les caractéristiques d'un graphe orienté
ou non, soit en manipulant les informations dans la feuille des données
soit directement sur le graphe par un travail interactif sur écran. Il
permet de résoudre les problèmes liés aux grands graphes
(ayant jusqu'à 250 sommets), notamment: les cycles Eulériens et
Hamiltoniens, la coloration, les plus cours chemins et les chemins critiques.
En plus, le logiciel GRIN40 permet le passage aisé entre la matrice
d'adjacence et le graphe, ce qui permet de contrôler les donner ou de les
insérer dans un rapport. Ce logiciel gratuit est l'oeuvre de
PETCHENKINE Vitaly (E-mail :pechv@mail.ru).
o La rubrique « Exercices et
problèmes »:
Cette partie est composée de vingt sept exercices
pouvant servir au travail des techniques, donc au cinquième moment
didactique où il est question de travailler les techniques en vue de
leur routinisation.
Ces exercices ne sont réparties ni par rubrique ni par
ordre de difficulté.
o La rubrique « Math
culture » :
Dans cette rubrique, On trouve un très bref
aperçu historique de la théorie des graphes depuis Euler et
certaines applications de cette théorie dans des domaines importants de
la vie économique et sociale ainsi que dans d'autres domaines
scientifiques.
Nous avons consigné, dans le tableau suivant, la
ventilation des activités, les exercices et les travaux pratiques (TP)
du chapitre « Initiation aux graphes » par rubrique ainsi
que les éléments institutionnalisés. On peut observer
qu'il y a trente quatre activités à la disposition de
l'enseignant pour être utilisées en classe. Institutionnellement,
il peut utiliser d'autres supports pédagogiques en complément ou
à la place. Seulement, comme il est l'unique manuel officiel et que le
programme officiel n'est pas explicite, il est difficile à un enseignant
de s'en éloigner. D'où son importance.
|
Rubrique
|
Pages
|
Nombre
|
Eléments institutionnalisés
|
|
Activités
|
Exercices
|
TP
|
|
Pour commencer
|
83-84
|
5
|
-
|
-
|
-
|
|
Notion de graphe
|
85-91
|
14
|
5
|
-
|
Définitions : d'un graphe, sommet, arête,
sommets adjacents, degré d'un sommet, sommet isolé.
Lemme des poignées de mains. Chaîne, longueur
d'une chaîne, cycle, graphe connexe, chaîne eulérienne,
cycle eulérien. Théorème d'Euler.
|
|
Coloriage d'un graphe
|
91-94
|
7
|
1
|
-
|
Définitions de : coloriage d'un graphe, nombre
chromatique, nombre chromatique d'un graphe complet et d'un sous graphe.
Encadrement du nombre chromatique. Algorithme de Walsh et Powell.
|
|
Recherche d'un plus court chemin
|
95-103
|
5
|
-
|
-
|
Définition de : graphe pondéré,
poids d'une chaîne, plus courte chaîne.
Algorithme de Moore-Djikstra.
|
|
Utilisation des TIC
|
104-108
|
2
|
-
|
2
|
Utilisation d'un logiciel.
|
|
Exercices
|
109-112
|
-
|
27
|
-
|
|
|
Math culture
|
113
|
1
|
-
|
-
|
Appréciation des apports des mathématiciens.
|
|
Total
|
-
|
34
|
33
|
2
|
|
Tableau 6
| 
