|
Emergents spontanés d'une analyse praxéologique( Télécharger le fichier original )par Abderrazak Chaouachi Université de Tunis - Mastère de didactique des mathématiques 2009 |
III-4. Analyse praxéologique des activités du chapitre « Initiation aux graphes »Dans cette partie, nous allons exposer d'abord la praxéologie ponctuelle associée à chaque type de tâche pour toutes les questions posées dans les activités analysées. On présentera, pour chaque question, les tâches et les types de tâche correspondants et, par le menu détail, la technique ainsi que ses objets constitutifs de la dichotomie fondamentale : à savoir les ostensifs mobilisés et les non ostensifs et enfin le bloc technologique- théorique. Les commentaires qui suivent l'analyse praxéologique donnent des éclairages quant au lien entre chaque praxéologie ponctuelle exposée et : v les éléments constitutifs du triangle didactique, notamment le pôle « Savoir ». v le moment didactique au cours duquel l'activité pourrait être réalisée.
Les activités retenues pour l'analyse sont consignées dans le tableau 7. A la fin de ce paragraphe, nous donnerons une synthèse des analyses praxéologiques des activités du manuel. Nous présenterons d'abord une synthèse des blocs pratico- techniques afin de montrer quelles sont les « Savoirs- faire » mobilisées tout au long du chapitre. Nous mettrons en relief, quand cela est possible, les cas de pénurie praxéologique et leur rapport avec l'épaisseur ostensive. Ensuite, nous exposerons une synthèse des blocs technologico- théoriques pour en tirer les « Savoirs » mis en oeuvre qui justifient les techniques. Le chapitre intitulé « Initiation aux graphes » du livre scolaire de troisième année, section : économie et gestion, compte trente activités réparties comme suit : · Cinq activités dans le paragraphe « Pour commencer». Ces activités ne seront pas analysées car, à notre avis, elles sont présentes dans le manuel parce que cette rubrique fait partie intégrante de la structure générale du livre telle qu'elle est conçue par ses auteurs « dans l'intention de faire le point sur les connaissances antérieures indispensables à l'élève pour aborder un nouveau chapitre » alors que les activités proposées ne répondent pas à cette intention . · Quatre activités dans le sous paragraphe « 1- Représentation graphique à l'aide d'un graphe » du paragraphe « I- Notion de graphe ». Nous avons analysé trois activités et nous n'avons pas analysé l'activité 2 de la page 86 pour la simple raison que cette activité pose le problème des boucles qui ne figurent pas au programme officiel. Nous estimons que la simple présence d'une telle activité posera des problèmes sémantiques pour les élèves comme pour les enseignants qui vont, dans le cas échéant, éviter d'aborder la réflexivité de la relation proposée afin de ne pas déborder des limites du programme. · Cinq activités dans le sous paragraphe « 2- Lemme de poignées de mains » du paragraphe « I- Notion de graphe ». Nous avons analysé l'activité 1 de la page 87 et les deux activités 4 et 5 de la page 88. Les autres activités ne sont pas analysées car elles ne présentent pas d'intérêt particulier. En effet, l'activité 2 de la page 87 aborde le thème de championnat de 24 équipes, lequel thème peut être abordé de manière spontanée en dehors du contexte des graphes ou à la rigueur est une répétition du schéma de graphe complet. En plus, la tâche pose un questionnement sur le type de championnat : est-ce un championnat à aller simple ? est-ce un championnat avec aller et retour ? L'autre activité non abordée est l'activité 3 de la page 87 dont la technique exige l'utilisation du raisonnement par l'absurde ou l'utilisation de la proposition contraposée et qui, à notre sens, pourrait poser des problèmes quant à sa compréhension. · Cinq activités dans le sous paragraphe « 3- Circulation sur un graphe » du paragraphe « I- Notion de graphe ». Nous avons analysé cinq activités (intitulées par les auteurs du manuel comme étant quatre activités et un exercice). L'activité 5 de la page 91 n'a pas été analysée pour la simple raison que le texte nous semble poser un autre problème de raisonnement par l'absurde. · Huit activités dans le paragraphe « II- Coloriage d'un graphe ». Nous avons analysé sept activités et nous n'avons pas analysé l'activité 8 de la page 94 pour la simple raison que cette activité pose le problème représentation graphique à 24 sommets. Cette représentation, par son encombrement, n'est évidemment pas lisible et donc non exploitable techniquement. · Sept activités dans le paragraphe « III- Recherche d'une plus courte chaîne ». Nous avons analysé les deux premières, les autres activités sont présentées avec leurs résolutions. Il serait peut être intéressant de les analyser mais alors cette analyse ne se réduirait à une simple description de la technique proposée par les auteurs et des spéculations sur les articulations entre les registres ostensifs et surtout sur les non ostensifs du bloc pratico- technique. Dans le tableau 8, nous résumons de toutes les remarques précédentes.
Tableau 7
Tableau 8 III-4.1.Analyse des activités par le modèle des quatre TDans ce paragraphe, nous présentons, d'abord et par activité retenue pour l'analyse, l'énoncé de l'activité. Puis, chaque question de cette activité est traduite en termes de tâche ou d'ensemble de tâches. Pour chaque tâche, nous avons consigné le type de tâche, la technique mobilisée et le bloc technologico- théorique. Nous avons relevé, pour chaque bloc pratico technique, les ostensifs manipulés et les non- ostensifs qui les guident. Nous avons choisi, compte tenue de ce que nous présupposons en termes d'habitudes gestuelles, les ostensifs déictiques mais qu'on peut remplacer, selon le contexte, en n'importe quel ostensif gestuel jouant le même rôle. Chaque analyse praxéologique est suivie de commentaires sur les résultats relevés au cours de cette analyse. Il est utile de signaler que, compte tenu de la nature des notions abordées dans le chapitre « initiation aux graphes », chaque type de tâche correspond à une technique particulière, d'ailleurs ciblée par les auteurs du manuel scolaire. Ainsi, nous ne nous trouvons pas en présence d'analyses praxéologiques pour lesquelles un type de tâche mobilise plusieurs organisations mathématiques et qui nous oblige à justifier le choix de telle organisation mathématique. Activité 1 page 85 i)Enoncé : Une personne souhaite inviter six amis que nous désignons par 1, 2, 3, 4, 5, 6. Malheureusement, certains de ces six amis ont des relations difficiles ; ce sont celles recensées dans le tableau suivant :
On veut résoudre le problème P suivant : Combien de personnes au maximum peuvent être invitées ensemble sans risque de problème ? 1) Représenter chaque ami par un point. 2) Relier deux points représentant deux personnes ayant une relation difficile. 3) Vérifier que l'on a un des schémas 1 3 6 1 3 2 6
2 5 1 6 2 5
4 4 5 3 6 4) Résoudre le problème P. ii)Analyse praxéologique: La question 1 : Représenter chaque ami par un point. Le travail demandé n'est pas une tâche puisqu'il a déjà été naturalisé depuis le primaire. La question 2 : Relier deux points représentant deux personnes ayant une relation difficile. Tâche et type de tâche : Pour la tâche, il s'agit de relier deux points représentant deux personnes ayant une relation difficile par une ligne. Cela appartient au type de tâche T= «Relier deux points x et y d'un ensemble sur lequel on a défini une relation R et tel que xRy ». Il s'agit d'une tâche routinière. Technique : On trace une ligne d'extrémités x et y si R est symétrique et une ligne orientée si R n'est pas symétrique. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs graphiques relevant du registre de la trace: traçage des lignes qui représentent les arcs (les liens de relation difficile). -Ostensifs discursifs relevant du registre de l'oralité: le discours accompagnant le traçage des lignes. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants : -On peut tracer, d'une infinité de manières, un arc joignant deux points quelconques du plan.
Bloc technologico- théorique :
La question 3 : Vérifier que l'on a un des schémas Tâche et type de tâche : Pour la tâche, il s'agit de vérifier pour chacun des graphes proposés s'il répond aux contraintes données dans le texte. Cette tâche appartient au type de tâche T= «Vérification si le diagramme représente fidèlement la relation donnée ». La tâche semble à première vue routinière puisqu'il s'agit de vérification de conformité. Seulement, l'élève, ne disposant pas d'une stratégie institutionnalisée, est obligé de proposer sa propre stratégie afin de s'assurer du résultat. Technique : On vérifie un à un les liens sur le tableau à partir du diagramme. Si la ligne sur le diagramme ne correspond pas au lien sur le tableau on élimine ce diagramme, sinon on passe au lien suivant jusqu'à épuisement des lignes. Les élèves découvriront que le premier schéma ne représente pas la situation proposée alors que les deux autres la représentent, mais au même temps ils découvrent qu'une même situation est représentable par plusieurs schémas. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité (plus exactement la deixis gestuelle) : On montre le lien sur le tableau et la présence ou l'absence de ce lien sur le schéma sélectionné. Cela se fait en pointant l'index sur l'information existant au tableau puis sur l'information correspondante sur le schéma. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant le gestuel. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants : -Il vaut mieux observer les différences plutôt que les similarités par soucis d'économie d'effort. -Recherche d'un contre exemple. Bloc technologico- théorique :
La question 4 : Résoudre le problème P. Tâche et type de tâche : Pour la
tâche, il s'agit de maximiser le nombre d'invités de sorte que
chaque invité n'ait de relation difficile avec aucun autre. Cette
tâche s'inscrit dans le type de tâche T= «Maximiser le nombre
sommets xi de sorte que, xi nonR xj pour
i Cette tâche est problématique. Elle se présente à l'élève pour la première fois et sa résolution est loin d'être évidente et il va être obligé de recourir à différentes stratégies pour éliminer le minimum possible d'amis et de comparer le résultat avec le reste des élèves. Technique : On colorie les sommets xi de sorte que deux sommets adjacents n'aient pas la même couleur. On essaie de minimiser le nombre de couleurs. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs matériels relevant du registre de la matérialité quelconque6(*): coloriage de chaque sommet. -Ostensifs discursifs relevant du registre de l'oralité : Les discours accompagnant le coloriage pour le choix de la couleur, choix des sommets de même couleur, justification des choix, etc. -Ostensifs déictiques relevant du registre de la gestualité : On montre que deux sommets adjacents quelconques n'ont pas la même couleur en pointant l'index sur les sommets adjacents. . La manipulation de ces ostensifs est guidée par les non- ostensifs suivants : -Il est toujours possible de faire un choix de personnes qui n'ont pas de relations difficiles. -la méthode connue sous l'appellation « essai /erreur » et le travail collectif en classe, permettent, de proche en proche, d'arriver à maximiser le nombre de ces invités. Bloc technologico- théorique : Lemme des choix de Zorn, Théorie des ensembles, théorie des graphes.
iii)Commentaire : Dans cette activité, l'élève est invité dans les deux premières questions à suivre des consignes précises. Nous aurions préféré une situation-problème qui ne se résout qu'en vérifiant, d'abord, que toutes les stratégies connues par l'élève ne permettent pas de résoudre le problème, et que la seule stratégie qui permet de s'en sortir est celle qui utilise des points et des courbes qui relient ces points. Les auteurs ont, peut être, sous estimé le rôle du second moment didactique dans l'introduction du concept « graphe » si bien que, pour un élève, le graphe paraîtrait comme un outil artificiel non nécessaire car imposé par le texte et non par les besoins de la résolution d'un problème. En principe, et vu qu'il s'agit de la première activité proposée, elle est censée être prise comme situation à présenter au premier moment didactique, c'est-à-dire le moment de première rencontre avec la notion de graphe non orienté. Cette rencontre, qui va orienter la conception de l'élève sur ces graphes ainsi que sur leurs utilités, va se dérouler à travers une situation pratique et qui fait intervenir les graphes comme artefact pour sa résolution. L'analyse praxéologique précédente montre que : - Les deux premières tâches sont, en fait, des tâches isolées et simples à mettre en oeuvre. - La troisième tâche fait appel à une technique d'identification de schémas, c'est-à-dire au concept de « graphes isomorphes » que les élèves n'étudieront pas mais qui sera contextualisé par l'activité 4 de la page 86. - La quatrième tâche, qui est en fait l'objet de l'exercice, s'appuie sur la technique de coloriage. Mais cette technique n'est pas encore connue des élèves. Dans ce cas, l'enseignant, guidé par cette technique, est amené à orienter les recherches dans la direction de la praxéologie décrite plus haut. En somme, on observe, durant cette activité de première découverte, une pénurie praxéologique qui découle de la non identification de bloc tehnologico - théorique qui permet de justifier les réponses des élèves (tel que la question 4). Cette pénurie praxéologique chez les élèves est compensée par un travail empirique s'étayant sur un ensemble d'ostensifs écrits, oraux et gestuels. Le rapport personnel de l'élève de troisième année économie et gestion avec la discipline va progressivement changer à partir de cette activité. Activité 3 page 86 i)Enoncé : 1) Dessiner un graphe d'ordre 4 tel que chaque sommet est adjacent aux autres. 2) a/ Dessiner un graphe de sommets A, B, C, D, E et F tel que : -A est adjacent à C, D et E. -B est adjacent à D. -C est adjacent à A et E. b/ Déterminer le nombre d'arêtes ayant pour extrémité D.
ii)Analyse praxéologique: La question 1 : Dessiner un graphe d'ordre 4 tel que chaque sommet est adjacent aux autres. Tâche et type de tâche : Pour la tâche, il s'agit de représenter le graphe complet K4 relevant du type de tâche T= « représentation d'un graphe complet Kn ». Cette tâche peut être considérée à ce stade comme routinière. En effet, l'élève sait déjà comment représenter un graphe connaissant les listes d'adjacence. Technique : On place quatre sommets puis on procède comme suit : -On connecte le premier sommet aux trois autres. -On connecte le second sommet au troisième et quatrième sommet. -On raccorde le troisième au quatrième sommet par une arête. On peut vérifier que tous les sommets sont adjacents. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: traçage des sommets et des arêtes. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant le traçage. -Ostensifs déictiques relevant du registre de la gestualité : On utilise l'index ou une règle ou tout autre objet permettant l'ostentation pour accompagner la preuve que tous les sommets sont adjacents. La manipulation de ces ostensifs est guidée par le non- ostensif suivant : -Le graphe étant symétrique, on peut utiliser le même raisonnement que pour les combinaisons 2 à 2 d'un ensemble à 4 éléments. Bloc technologico- théorique :
La question 2)a/ Dessiner un graphe de sommets A, B, C, D, E et F tel que : -A est adjacent à C, D et E. -B est adjacent à D. -C est adjacent à A et E. Tâche et type de tâche : Pour la tâche, il s'agit de dessiner le graphe dont les sommets et la liste d'adjacence sont donnés dans le texte. Cette tâche appartient au type de tâche T= «représentation d'un graphe dont on connaît les sommets et la liste d'adjacence ». Cette tâche est routinière pour la même raison qu'on a évoquée plus haut. Technique : On place les six sommets A, B, C, D, E et F puis on procède comme suit : -On trace les arêtes A-C, A-D et A-E. -On trace l'arête B-D. -On trace l'arête C-E. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs graphiques relevant du registre de trace: traçage des sommets et des arêtes. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant le traçage des arêtes. -Ostensifs déictiques relevant du registre de la gestualité : On utilise l'index ou une règle ou tout autre objet permettant l'ostentation des arêtes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant : -Le graphe est symétrique. Bloc technologico- théorique :
La question 2) b/ Déterminer le nombre d'arêtes ayant pour extrémité D. Tâche et type de tâche : Pour la tâche, il s'agit de déterminer le degré du sommet D relevant du type de tâche T=«Détermination du degré d'un sommet ». Cette tâche est routinière. Technique : On compte les arêtes dont le sommet D est une extrémité. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité : On utilise l'index ou une règle ou tout autre objet permettant d'accompagner le comptage des arêtes dont le sommet D est une extrémité. -Ostensifs discursifs relevant du registre de l'oralité : Le discours du comptage. La manipulation de ces ostensifs est guidée par le non- ostensif suivant : -On se place au sommet D sur le graphe déjà construit pour commencer le comptage. Bloc technologico- théorique :
iii)Commentaire: Cette activité correspond au cinquième moment didactique, c'est-à-dire le moment de travail de la technique. Toutes les tâches sont routinières et l'élève va donc investir les savoirs acquis pour établir un rapport personnel avec l'objet « graphe ». La première question met l'élève en rapport avec les graphes complets qui ont un statut spécial en théorie des graphes et qui vont lui permettre plus tard de justifier certaines assertions (tels que le nombre chromatique). La seconde question porte sur la représentation d'un graphe et le concept d'adjacence. Elle va soulever la question de la diversité de représentation d'un graphe et, en conséquence sur les conditions pour que deux graphes représentent la même situation. Activité 4 page 86 i)Enoncé : Parmi les graphes ci-dessous, déterminer ceux qui sont susceptibles de décrire une même situation. Graphe G1 Graphe G2 Graphe G3
Graphe G4 Graphe G5 Graphe G6 ii)Analyse praxéologique: Tâche et type de tâche : Pour la tâche, il s'agit de trouver les graphes isomorphes parmi les six présentés relevant du type de tâche T= «Etant donnés deux graphes, étudier s'ils sont isomorphes». Cette tâche est problématique car l'élève ne dispose pas des outils théoriques qui permettent d'appréhender ce genre de problème. Technique : On procède comme suit: -On regroupe les graphes de même ordre (G1 et G3), (G2 et G5) et (G4 et G6). -G1 et G3 ont le même nombre d'arêtes donc pourraient représenter la même situation. G2 et G5 n'ont pas le même nombre d'arêtes donc ne représentent pas la même situation. G4 et G6 ont le même nombre d'arêtes, donc ils sont susceptibles de représenter la même situation. Concernant ces deux derniers graphes, il faut passer aux degrés des sommets pour découvrir s'il y a bijection entre les sommets et la bijection correspondante entre les arêtes. Pour cela, on remarque que dans les deux graphes il y a deux sommets de degré 2 et deux sommets de degré 3. Cela permet la correspondance : 1 2 3 4 Les deux graphes représentent la situation :
On peut utiliser la même procédure pour prouver que les deux graphes G1 et G3 décrivent une même situation. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité : On utilise l'index ou une règle ou tout autre objet permettant l'ostentation pour suivre le comptage des sommets et des arêtes ainsi les correspondances entre sommets puis entre arêtes. -Ostensifs discursifs relevant du registre de l'oralité : Le discours de comptage et de correspondance. -Ostensifs scripturaux relevant du registre de la trace: Désignation des étiquettes des sommets et des arêtes, les définitions des bijections entre sommets et entre arêtes. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants : -La définition de graphes isomorphes. -Les conséquences de cette définition (équipotence entre ensemble des sommets et aussi entre ensemble d'arêtes correspondantes, etc.) -Recherche de propriété manquante par ordre croissant d'éléments d'information disponibles. Bloc technologico- théorique :
iii)Commentaire: En théorie des graphes, deux graphes qui représentent la même situation sont dits isomorphes. Cette notion d' « isomorphisme de graphes » n'est pas institutionnalisée dans le cycle secondaire car sa définition fait appel à une double bijection inter- reliées (bijection entre sommets, bijection entre arêtes homologues) et qui débouche sur la propriété fondamentale : deux graphes isomorphes ont les mêmes propriétés. C'est cette propriété qui va servir comme toile de fond (ou non ostensif) pour la technique exposée ci-dessus et qui permet de répondre à cette question. Ainsi, les élèves vont disposer, en fin de compte, d'une technique et pas de bloc technologico - théorique qui la justifie. La variable didactique v=(nombre de sommets, nombre d'arêtes) favorise le travail empirique et la découverte de la technique. Activité 1 page 87 i)Enoncé : Pour chacun des graphes suivants donner : 1 B 1 a b A D 2 5 1 C d c e 3 g 2 E 4 f 1)a/ Le degré de chaque sommet. b/ La somme des degrés de tous les sommets. c/ Le nombre d'arêtes. 2) Quelle conjecture peut-on faire ? ii)Analyse praxéologique: La question 1)a/ Le degré de chaque sommet. Tâche et type de tâche : Pour la tâche, il s'agit de donner le degré de chaque sommet. Cela appartient au type de tâche T= «Donner le degré d'un sommet pour un graphe donné sous la forme d'un schéma ». Il s'agit d'une tâche routinière. Technique : On choisit un sommet et on compte les arêtes dont ce sommet est une extrémité. Puis, on passe au sommet suivant et on fait le même travail jusqu'à épuisement de tous les sommets. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité : On montre le sommet choisi et les arêtes dont ce sommet est une extrémité. Cela est fait en pointant l'index sur le sommet et les arêtes. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant les désignations sur le tableau. -Ostensifs scripturaux relevant du registre de la trace: écriture des réponses sur un tableau ou toute autre forme de rédaction. La manipulation de ces ostensifs est guidée par le non -ostensif suivant: -Degré d'un sommet. Bloc technologico- théorique
La question 1/b : La somme des degrés de tous les sommets. Tâche et type de tâche : Pour la tâche, il s'agit de donner la somme des degrés de tous les sommets. Cela appartient au type de tâche T= «Donner la somme de nombres entiers donnés ». Il s'agit d'une tâche routinière. Technique7(*) : On calcule soit oralement soit en utilisant une calculatrice les nombres trouvés. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre da gestualité : On montre le sommet et son degré et on fait la somme des degrés. -Ostensifs scripturaux relevant du registre de la trace : écriture des nombres à additionner et le résultat de l'addition. La manipulation de ces ostensifs est guidée par le non -ostensif suivant: -L'addition dans IN est commutative (on peut commencer par n'importe quel sommet). Bloc technologico- théorique : Addition dans IN en Algèbre.
La question 1)c/ : Le nombre d'arêtes. Tâche et type de tâche : Pour la tâche, il s'agit de donner le nombre d'arêtes. Cela appartient au type de tâche T= «Donner le nombre d'arêtes d'un graphe donné sous la forme d'un schéma ». Il s'agit d'une tâche routinière. Technique : On écrit la liste de toutes les arêtes du graphe choisi puis on les compte8(*). Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité : On montre les arêtes en les pointant par l'index -Ostensifs scripturaux relevant du registre de la trace: écriture des réponses. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant les gestes et le discours de comptage. La manipulation de ces ostensifs est guidée par le non -ostensif suivant: - Eléments caractéristiques d'un graphe non orienté. Bloc technologico- théorique :
La question 2): Quelle conjecture peut-on faire ? Tâche et type de tâche : Pour la tâche, il s'agit de conjecturer sur les résultats trouvés, c'est-à-dire sur le lien possible entre la somme des degrés de tous les sommets et le nombre d'arêtes. Cela appartient, compte tenu des pré-requis des élèves, au type de tâche T= «Donner une relation linéaire liant deux variables ». Il s'agit d'une tâche routinière surtout qu'il s'agit de relation linéaire simple. Technique : On dresse un tableau9(*) dans lequel sont consignés : le graphe, la somme des degrés et le nombre d'arêtes. On peut alors conjecturer sur le lien entre la somme des degrés des sommets et le nombre d'arêtes. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: écriture des réponses trouvées dans les questions précédentes sur le tableau. -Ostensifs déictiques relevant du registre de la gestualité: Les gestes accompagnant la comparaison des nombres pour chacun des graphes. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant l'établissement du tableau, la comparaison des nombres et la rédaction. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -Lien entre deux variables. -Expression algébrique linéaire y=ax. Bloc technologico- théorique :
iii)Commentaire: On peut observer que :
L'énoncé de la conjecture découle d'une interprétation du tableau reliant la somme des degrés de tous les sommets et le nombre d'arêtes. L'enseignant s'attend à ce que les élèves énoncent la relation de linéarité qui devrait être institutionnalisée par la suite et qu'ils admettent la validité de cette relation dans le cas général. Pour les élèves, c'est l'enseignant qui est garant de la validité de cette conjecture pour tout graphe non orienté quand il déclare : « En théorie des graphes, on démontre que cette conjecture est valide pour tous les graphes orientés ». L'enseignant peut, s'il observe que les élèves ne sont pas assez convaincus, esquisser une démonstration. Activité 4 page 88 i)Enoncé : On s'intéresse aux graphes dont tous les sommets sont de degré 3. Construire, si c'est possible, de tels graphes ayant 4, 5, 6, 7 sommets. ii)Analyse praxéologique: Tâche et type de tâche : Cette question peut être divisée en deux tâches : -La première tâche t1= « étudier l'existence de graphes 3-réguliers d'ordre 4, 5, 6, 7 » qui appartient au type de tâche T= «étudier l'existence d'un graphe d'ordre donné et k- régulier» -La seconde tâche t2= «dans le cas où le graphe existe, construire de tels graphes » qui appartient au type de tâche T= «Construire un graphe k- régulier d'ordre donné ». Il s'agit de deux tâches problématiques. Techniques : -Pour la tache t1, On calcule la somme des degrés des sommets. Si la somme est impaire alors le graphe n'existe pas. Sinon, on peut espérer que de tels graphes existent et on peut passer à la tâche t2. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: l'addition des degrés des sommets (qui, en fait est une multiplication) et la conclusion. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant le raisonnement. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Le lemme des poignées de mains. -Pour la tache t2, déjà on sait que les graphes 3-réguliers d'ordre 5 ou 7 n'existent pas. On focalise le travail sur ceux d'ordre 4 et 6. Pour chaque cas, on calcule le nombre d'arêtes et on construit le graphe10(*). Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs graphiques relevant du registre de la trace: le marquage des sommets et le traçage des arêtes. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant le travail écrit. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Les relations entre le nombre d'arêtes et le nombre de sommets dans le cas d'un graphe complet (premier cas). -L'analogie avec les prismes à base triangulaires pour le second cas. Bloc technologico- théorique : -Le lemme des poignées de mains en théorie des graphes.
iii)Commentaire: Cette activité fait appel au théorème des poignées de mains dans sa phase initiale et en conséquence sa praxéologie est bien connue et routinisée. La seconde partie de la question, c'est-à-dire la construction, pose un problème méthodologique sur la façon de construire un graphe connaissant le nombre de ses sommets et le nombre de ses arêtes. L'élève et l'enseignant ne disposent pas de technique pour résoudre ce genre de question. Nous sommes, en conséquence en présence de pénurie praxéologique qui va être compensée par des schémas et des figures géométriques (quadrilatère convexe avec diagonales, prisme à base triangulaire) qui répondent aux conditions énoncées. Ce raisonnement par analogie ne va pas de soi chez l'élève et c'est peut être le moment de première rencontre entre l'élève et ce « va et vient » entre les cadres de la théorie des graphes et la géométrie. Activité 5 page 88 i)Enoncé : Sept personnes se retrouvent pour un dîner. Certaines d'entre elles, qui se sont déjà vues dans la journée, ne se serrent pas la main. Quatre personnes ont serré trois mains, deux en ont serré une. La septième personne peut elle serrer qu'une seule main ? ii)Analyse praxéologique: Tâche et type de tâche : Pour la tâche, il s'agit de répondre à la question : est-il vrai que la septième personne ait serré une seule main ? Cela appartient, compte tenue des hypothèses données, au type de tâche T= «Quelle est la parité du nombre de mains que la septième personne a serré ? ». Il s'agit d'une tâche routinière. Technique : On modélise d'abord la situation (choix des sommets: S1, S2, ....., S7 et de la relation qui indique les arêtes : se serrer ma main). Puis, on calcule la somme des degrés des sommets11(*) afin de pouvoir conclure. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : la désignation des sommets, l'addition des degrés des sommets et la conclusion. -Ostensifs discursifs relevant du registre de l'oralité : le discours accompagnant la mise en place des ostensifs écrits. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -La modélisation d'une situation par un graphe. -Le lemme des poignées de mains. -La règle: la somme de deux entiers de même parité est paire et la somme de deux entiers de parités différentes est impaire. -Il n'existe pas un nombre entier à la fois pair et impair. Bloc technologico- théorique :
iii)Commentaire: Cette activité fait appel à :
Nous avons, ici, un exemple de tâche dont la technique peut se décomposer en deux sous tâches :
Activité 1 page 88 i)Enoncé : A B D G C F E Des touristes sont logés dans ville A. Ils veulent visiter les sites B, C, D, E, F et G. Les tronçons de route sont représentés par le graphe ci-dessous :
1) Donner un parcours qui permet d'aller de A à E. 2) Donner un parcours qui permet d'aller de C à F. 3) A partir de la ville A, les touristes peuvent-ils emprunter tous les tronçons de route en passant une et une seule fois chacun d'eux ? 4) Même question s'ils doivent obligatoirement terminer leur circuit à la ville A. ii)Analyse praxéologique: La question 1) : Donner un parcours qui permet d'aller de A à E. Tâche et type de tâche : Pour la tâche, il s'agit de donner trouver une chaîne d'extrémités A et E. Cela appartient au type de tâche T= «Donner un chemin d'extrémités deux sommets donnés». Il s'agit d'une tâche routinière. Technique : On part du sommet A et on peut suivre un itinéraire afin d'atteindre le sommet E. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité : On montre le sommet A puis le parcours jusqu'au sommet E. -Ostensifs scripturaux relevant du registre de la trace: écriture de l'itinéraire trouvé. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant le choix de l'itinéraire. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Le graphe est d'un seul tenant, ce qui permet d'aller de n'importe quel sommet à n'importe quel sommet. Bloc technologico- théorique : Définition de chaîne dans un graphe non orienté.
Question 2) répond à la même analyse. Les questions 3 et 4: 3 ) A partir de la ville A, les touristes peuvent-ils emprunter tous les tronçons de route en passant une et une seule fois chacun d'eux ? 4) Même question s'ils doivent obligatoirement terminer leur circuit à la ville A. Tâche et type de tâche : Pour la tâche, il s'agit de trouver une chaîne eulérienne pour la question 3 ou un cycle eulérien pour la question 4. Cela appartient au type de tâche T= «Le graphe donné est-il semi- eulérien? Est-il eulérien ?». Il s'agit d'une tâche problématique. Technique : D'abord on étudie les degrés de tous les sommets. S'il y a zéro ou deux sommets de degrés impairs, on conclut à l'existence d'une chaîne eulérienne. Sinon, on conclut que le graphe n'est pas semi- eulérien. Ensuite, on construit la chaîne en partant de n'importe quel sommet si tous les sommets sont de degrés pairs (et on obtient alors un cycle eulérien) ; sinon, la chaîne doit impérativement commencer et aboutir par l'un des deux sommets de degré impair. On a seulement 2 sommets de degrés impairs (A et D). On trouve, par exemple, la chaîne Eulérienne : A-B-C-G-A-D-F-E-C-G-D et pas de cycle Eulérien. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité: On montre le sommet de départ et l'itinéraire choisi. -Ostensifs scripturaux relevant du registre de la trace: écriture des degrés des sommets sur un tableau ou toute autre forme de rédaction. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant le choix du sommet du départ, l'itinéraire et la vérification qu'il s'agit bien d'une chaîne simple. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -Graphe semi- eulérien. -Le théorème d'Euler. Bloc technologico- théorique : Théorème d'Euler en théorie des graphes.
iii)Commentaire: Les questions 1 et 2 ne nécessitent pas de technique élaborée, étant donnée la simplicité du graphe proposé. Il suffit de commencer par le point de départ et s'approcher du point d'arrivée en minimisant la distance qui reste à parcourir soit visuellement soit en calculant cette distance. Les questions 3 et 4 peuvent, par contre, poser des problèmes quant à l'élaboration de stratégie de recherche de parcours avec la contrainte énoncée. Il est clair que les objectifs de l'activité sont :
La technique pour résoudre les questions 3 et 4 et les réponses sont connues de l'enseignant. Laquelle technique ne sera institutionnalisée que bien plus tard. Ainsi, les élèves, dans ce cadre d'une pénurie praxéologique, vont essayer empiriquement de répondre à ces questions. Ils peuvent eux- mêmes valider par ostension, au sein d'un groupe d'élèves, leurs réponses sans l'intervention de l'enseignant. . Activité 2 page 89 i)Enoncé : La figure ci-dessous représente un parcours de santé. Dresser la liste de toutes les paires de sommets et vérifier qu'il existe une chaîne reliant ces deux sommets. A B E F C D ii)Analyse praxéologique: Tâche et type de tâche : Il s'agit en fait de deux tâches : - La première t1 = « Dresser la liste de toutes les paires de sommets du graphe donné» qui appartient au type de tâche T1 = « Dresser la liste des paires d'éléments d'un ensemble fini donné ». Il s'agit d'une tâche routinière puisqu'elle a été traitée dans le chapitre dénombrements. Technique : On ordonne d'abord les sommets, puis on procède comme suit :
Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : la liste ordonnée des sommets et les paires. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Le dénombrement des paires de sommets12(*). Bloc technologico- théorique :
- La seconde tâche t2 = « Vérifier que pour toute paire de sommets du graphe donné il existe une chaîne les reliant » qui appartient au type de tâche T2 = « Vérifier que, pour toute paire de sommets d'un graphe, il existe une chaîne les reliant». Il s'agit d'une tâche routinière vu la simplicité du graphe. Technique : On dresse le tableau consignant les paires de sommets et les chaînes les reliant. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: traçage du tableau, la liste de toutes les paires et les chaînes correspondantes. -Ostensifs déictiques relevant du registre de la gestualité : On montre les chaînes. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant les choix des chaînes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Chaîne dans un graphe non orienté. Bloc technologico- théorique : Définition d'une chaîne dans un graphe non orienté en théorie des graphes.
iii)Commentaire: Il s'agit d'une activité qui représente le premier moment didactique sur le concept de connexité de graphes. Dans la première partie de la question, c'est-à-dire pour donner toutes les paires possibles, l'élève dispose d'une technique applicable à tous les ensembles finis. En revanche, le type de tâche T2 se présente à l'élève pour la première fois. Donc l'élève ne dispose pas d'une praxéologie et va répondre empiriquement à la question qui peut se prêter à ce genre de traitement du fait de la simplicité du graphe proposé. Exercice page 89 i)Enoncé : Parmi les graphes suivants, reconnaître ceux qui sont connexes : G1 G2 G3
G4 G5 G6 ii)Analyse praxéologique: Tâche et type de tâche : Pour la tâche, il s'agit d'étudier la connexité d'un graphe donné par son schéma. Cela appartient au type de tâche T= «Etudier la connexité d'un graphe». Il s'agit d'une tâche routinière puisque la définition est déjà donnée et appliquée dans l'activité précédente. Technique : On commence par prouver le non connexité du graphe sélectionné en montant qu'il y a deux sommets qui ne peuvent pas être reliés par une chaîne. Sinon, on utilise la technique de l'activité précédente pour prouver la connexité. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité : On montre, s'ils existent, les deux sommets qui ne peuvent pas être reliés par une chaîne. Ou bien on montre, en faisant passer l'index sur les arêtes, que le graphe est d'un seul tenant. -Ostensifs scripturaux relevant du registre de la trace: Les sommets qui ne peuvent pas être reliés par une chaîne ou le tableau tel que l'on a indiqué dans l'activité précédente. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les choix des sommets. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -Connexité d'un graphe non orienté. -La négation de la proposition : pour tout couple de sommets x et y, il existe une chaîne reliant x et y. -Le dénombrement des paires de sommets. -Chaîne dans un graphe non orienté. Bloc technologico- théorique :
iii)Commentaire: Il s'agit d'une activité de consolidation sur la définition de la connexité d'un graphe et qui est institutionnalisée. La technique esquissée dans l'activité 2 de la même page est faisable pour les graphes G1 et G6. Par contre, cette technique est très lourde concernant le graphe G3. Car elle exigerait un travail sur 15 paires de sommets. D'autres techniques plus économiques devraient être envisagées à partir d'une certaine grandeur de l'ordre d'un graphe. Pour les graphes G2, G4 et G5, il s'agit en fait de montrer qu'ils ne sont pas connexes et donc d'utiliser la négation de la proposition : « Pour chacune des paires de sommets, il existe une chaîne reliant ces deux sommets ». Cette négation s'énonce : « Il existe une paire de sommets qui ne sont pas reliés ». Les deux graphes G2 et G5 peuvent induire en erreur certains élèves qui pourraient penser que certaines arêtes se croisent et déduisent que ces deux graphes sont connexes alors qu'ils ne le sont pas. En somme, on peut observer que l'on dispose d'une praxéologie à portée limitée par rapport au nombre de sommets et qu'elle nécessite, dans le cas de non connexité, à recourir à un contre-exemple. Ainsi, pour ce type de tâche, il n'y a pas de pénurie praxéologique à proprement parler mais nous nous trouvons en présence d'une praxéologie à portée limitée et qui va obliger les élèves, à partir d'un certain ordre de grandeur du nombre de sommets, à s'investir dans d'autres techniques plus économiques, c'est-à-dire faisables. Activité 3 page 89 i)Enoncé : Peut-on reproduire les graphes ci-dessous sans lever le crayon et ne passant qu'une seule fois sur chaque arête. G1 G2 G3 ii)Analyse praxéologique: Tâche et type de tâche : Pour la tâche, il s'agit de faire glisser le crayon sur la feuille afin de reproduire le graphe proposé de sorte que chaque arête soit tracée une seule fois. Cela appartient au type de tâche T= «Reproduire un graphe sans passer deux fois par la même arête». Il s'agit d'une tâche problématique. Technique : On procède par essai/erreur. La simplicité du graphe permet de décider si le travail demandé est possible ou non. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs graphiques relevant du registre de la trace: Le traçage des arêtes. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant le choix du sommet du départ et le traçage des arêtes. -Ostensifs déictiques relevant du registre de la gestualité : On montre le sommet du départ et on simule par le geste le mouvement entre les sommets. -Ostensifs scripturaux relevant du registre de la trace: On écrit le résultat qui indique soit l'impossibilité d'une telle manoeuvre soit d'une itinéraire solution. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Le théorème d'Euler. Bloc technologique- théorique :
iii)Commentaire: Cette activité prépare le terrain pour l'énoncé du théorème d'Euler. L'enseignant connaît ce théorème et possède, donc, une technique permettant de répondre à la question sur chacun des quatre cas proposés. La forme accrocheuse de la question et la simplicité des graphes proposés va inciter les élèves à se prendre en charge par défi mutuel. Il en résultera une première rencontre avec :
Cela étant, on remarque que sur cette activité il y a pénurie praxéologique car il n'y a pas de technique connue préalablement par l'élève pour réaliser cette tâche. En fait, nous observons un cas typique de situation de pénurie praxéologique palliée par une grande épaisseur ostensive et qui débouche sur la mise en place d'une praxéologie. Activité 1 page 91 i)Enoncé : A, B, C, D, E, F, G et H désignent huit poissons. Dans le tableau ci-dessous, une croix signifie que les poissons ne peuvent pas cohabiter dans un même aquarium.
On se propose de résoudre le problème P suivant : Quel est le nombre d'aquariums nécessaires ? 1) Représenter cette situation par un graphe. (Deux sommets sont adjacents si les deux poissons ne cohabitent pas). 2) Expliquer pourquoi la résolution du problème P revient à la résolution du problème suivant : « Quel est le nombre minimal de couleurs nécessaires pour colorier les huit sommets de ce graphe de sorte que deux sommets adjacents ne soient pas de même couleur ? ». 3) Les quatre sommets A, C, D et H sont deux à deux adjacents. Déduire qu'il faut au moins quatre couleurs. 4) Vérifier que quatre couleurs suffisent. 5) Résoudre le problème P. ii)Analyse praxéologique: La question 1) : Représenter cette situation par un graphe. (Deux sommets sont adjacents si les deux poissons ne cohabitent pas). Tâche et type de tâche : Pour la tâche, il s'agit de représenter la situation donnée par un graphe. Cela appartient au type de tâche T= «Représenter la situation donnée par un graphe». Il s'agit d'une tâche routinière, vu l'indication du type de relation à représenter. Technique : On représente chaque poisson par un point et là où observe une croix (ligne x et colonne y) on trace une arête reliant les sommets x et y. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs graphiques relevant du registre de la trace: les sommets et les arêtes. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les choix des sommets le traçage des arêtes. -Ostensifs déictiques relevant du registre de la gestualité : On montre la correspondance entre les données et le graphe. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -Graphe non orienté. -Représentation d'un graphe. Bloc technologico- théorique :
La question 2) : Expliquer pourquoi la résolution du problème P revient à la résolution du problème suivant : « Quel est le nombre minimal de couleurs nécessaires pour colorier les huit sommets de ce graphe de sorte que deux sommets adjacents ne soient pas de même couleur ? ». Tâche et type de tâche : Pour la tâche, il s'agit d'expliquer que la formulation du problème P équivaut en termes de la théorie des graphes au texte donné. Cela appartient au type de tâche T= «Equivalence sémantique de deux propositions appartenant à deux registres lexicaux différents». Il s'agit d'une tâche problématique dans la mesure où les élèves n'ont jamais fait auparavant, en mathématique, ce genre de passage entre deux registres linguistiques. Technique : On établit une correspondance entre deux registres linguistiques, ce sont celui du langage vernaculaire et le registre terminologique de la théorie des graphes. Cette correspondance permet le passage (la traduction) entre les deux registres.
Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : écriture des correspondances entre propositions et termes. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les gestes de va et vient entre les deux registres linguistiques. -Ostensifs déictiques relevant du registre de la gestualité : On montre la correspondance entre les deux registres. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -Définition d'un graphe non orienté. -Analyse sémantique des propositions. Bloc technologique- théorique :
La question 3) : Les quatre sommets A, C, D et H sont deux à deux adjacents. Déduire qu'il faut au moins quatre couleurs. Tâche et type de tâche : Pour la tâche, il s'agit de déduire qu'il faut au moins quatre couleurs. Cela appartient au type de tâche T= «donner un minorant du nombre chromatique». Il s'agit d'une tâche routinière, vu l'indication de l'existence d'un sous graphe complet d'ordre 4. Technique : On remarque que le sous- graphe
engendré par les sommets A, C, D et H est complet donc son nombre
chromatique est 4, et puisque l'ordre d'un graphe est supérieur ou
égal à l'ordre de ses sous graphes. On conclut que Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs graphiques relevant du registre de la trace: Le sous graphe GACDH, le nombre chromatique et les graphes complets. -Ostensifs déictiques relevant du registre de la gestualité: On montre les sommets à colorier. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les gestes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Minoration du nombre chromatique. Bloc technologique- théorique :
La question 4): Vérifier que quatre couleurs suffisent. Tâche et type de tâche : Pour la tâche, il s'agit de vérifier que quatre couleurs suffisent. Cela appartient au type de tâche T= «Vérifier que l'on peut colorier le graphe donné par k couleurs, k donné». Il s'agit d'une tâche routinière. Technique : On commence par colorier le sous graphe complet GACDH puis les quatre autres sommets. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs relevant du registre de la matérialité quelconque: coloration du sous graphe complet, coloration des autres sommets. -Ostensifs déictiques relevant du registre de la gestualité: On montre les sommets à colorier. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les gestes. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -Coloration d'un graphe. -Nombre chromatique d'un graphe complet. Bloc technologique- théorique :
La question 5) : Résoudre le problème P. Tâche et type de tâche : Pour la tâche, il s'agit de trouver le nombre minimum d'aquariums. Cela appartient au type de tâche T= «Calculer le nombre chromatique du graphe donné». Il s'agit d'une tâche routinière. Technique : Déduire la valeur du nombre
chromatique Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace:
les deux encadrements et la valeur de -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les gestes sur les passages entre les encadrements. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: -Déduction logique : -si Bloc technologico- théorique :
iii)Commentaire: La première question est une tâche dont on connaît la technique, surtout que le choix des sommets et des arêtes a été énoncé dans le texte : « Deux sommets sont adjacents si les deux poissons ne cohabitent pas ». . Par contre, en ce qui a trait à la seconde question, l'élève ne dispose pas de technique à laquelle il peut se référer. Car il s'agit bien de traduire un texte en langage vernaculaire en un texte utilisant une terminologie propre à la théorie des graphes dans sa majorité. Les trois autres questions (ou tâches) se réfèrent chacune à une praxéologie. En somme, dans cette activité, on observe que toutes les tâches demandées se réfèrent à une praxéologie sauf la seconde qui présente une pénurie praxéologique. Activité 2 page 92 i)Enoncé : Colorier les graphes suivants : G1 G2 G3 G4 G5 ii)Analyse praxéologique: Tâche et type de tâche : Pour la tâche, il s'agit de colorier un graphe présenté par son schéma. Cela appartient au type de tâche T= «colorier un graphe». Il s'agit d'une tâche routinière. Technique : On utilise l'algorithme de Walsh et Powell. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : Le tableau dans lequel sont consignés les sommets, leurs degrés, l'ordre et la couleur. -Ostensifs déictiques relevant du registre de la gestualité : On désigne le sommet sélectionné, sa couleur et les sommets suivants qui ne lui sont pas adjacents. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant les gestes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -L'ordre d'un sommet est déterminant pour le déroulement de l'algorithme. Bloc technologico- théorique :
iii)Commentaire: La tâche proposée possède une technique du fait que l'algorithme à utiliser a été déjà institutionnalisé. Il s'agit, en fait, d'une application directe de l'algorithme de Walsh et Powell. Activité 3 page 92 i)Enoncé : On donne le graphe le graphe suivant : C D A B G H E F 1) a/ Colorier le graphe en utilisant l'algorithme précédent. b/ Quel est le nombre de couleurs utilisées. 2) Est-il possible de colorier le graphe en utilisant uniquement deux couleurs ? ii)Analyse praxéologique: La question 1) : a/ Colorier le graphe en utilisant l'algorithme précédent. b/ Quel est le nombre de couleurs utilisées. Tâche et type de tâche : Pour la tâche, il s'agit de colorier un graphe présenté par son schéma en utilisant l'algorithme de Wash et Powell. Cela appartient au type de tâche T= «colorier un graphe en utilisant l'algorithme de Walsh et Powell». Il s'agit d'une tâche routinière. Technique : On utilise l'algorithme de Walsh et Powell. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : Le tableau dans lequel sont consignés les sommets, leurs degrés, l'ordre et la couleur. -Ostensifs déictiques relevant du registre de la gestualité : On désigne le sommet sélectionné, sa couleur et les sommets suivants qui ne lui sont pas adjacents. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les gestes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -L'ordre d'un sommet est déterminant pour le déroulement de l'algorithme. Bloc technologico- théorique :
La question 2) : Est-il possible de colorier le graphe en utilisant uniquement deux couleurs ? Tâche et type de tâche : Pour la tâche, il s'agit de colorier un graphe présenté par son schéma sans recourir à l'algorithme de Walsh et Powell. Cela appartient au type de tâche T=«colorier un graphe». Il s'agit d'une tâche routinière. Technique : Il suffit de ne pas commencer par colorier les sommets E et G. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs matériels relevant du registre de la matérialité quelconque : Une première couleur pour les sommets A, C, E et G ; puis le coloriage par une second couleur des autres sommets. -Ostensifs déictiques relevant du registre de la gestualité : On désigne les sommets sélectionnés A, C, E et G puis les autres sommets. -Ostensifs discursifs relevant du registre de l'oralité : Le discours accompagnant les choix. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Coloriage d'un graphe. Bloc technologico- théorique :
iii)Commentaire: La première tâche (1/a) proposée possède une technique routinisée du fait que l'algorithme à utiliser a été institutionnalisé. La seconde tâche (1/b) est une simple opération de comptage. La dernière tâche peut être réalisée en choisissant un premier sommet différent de celui choisi par l'algorithme de Walsh et Powell. L'enjeu didactique de cette activité est de montrer un cas extrême : L'algorithme ne donne jamais le nombre chromatique. Car, dans la plupart des cas, il suffit de permuter les sommets de même degré pour obtenir le nombre chromatique. Dans ce cas (il y en a d'autres), l'algorithme donne toujours trois couleurs alors que l'on peut vérifier facilement que deux couleurs suffisent. En d'autres termes, l'objet de cette activité est de modérer le rapport personnel de l'élève à l'objet du savoir « Algorithme de Walsh et Powell » dans la mesure où il faut s'attendre de cet algorithme une bonne approximation du nombre chromatique et occasionnellement le nombre lui-même. Activité 4 page 93 i)Enoncé : 1) Quel est le nombre chromatique d'un graphe complet d'ordre 3 ? 2) Quel est le nombre chromatique d'un graphe complet d'ordre 5 ? 3) Quel est le nombre chromatique d'un graphe complet d'ordre n?
ii)Analyse praxéologique: Les questions : 1, 2 et 3. Tâche et type de tâche : Pour la tâche, il s'agit de déterminer le nombre chromatique d'un graphe complet. Cela appartient au type de tâche T= «Déterminer le nombre chromatique d'un graphe complet». Il s'agit d'une tâche routinière dans la mesure où la technique à utiliser a été déjà institutionnalisée. Technique : On remarque que tous les sommets sont adjacents et donc tous les sommets ont des couleurs différentes. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs graphiques relevant du registre de la trace : traçage d'un graphe complet d'ordre 2 puis un autre d'ordre 3. -Ostensifs scripturaux relevant du registre de la trace: Les hypothèses, analyse de la coloration. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Coloration de deux sommets adjacents. -Généralisation des résultats observés au cas général (question 3). Bloc technologico- théorique :
iii)Commentaire: La tâche proposée possède une technique du fait que l'algorithme à utiliser a été institutionnalisé. Les graphes et les sous graphes complets ont un statut particulier en théorie des graphes et en particulier dans la recherche du nombre chromatique. Car, il suffit de commencer par colorer un sous graphe complet d'ordre maximal et, en général les couleurs utilisées sont suffisantes. Ainsi, l'enjeu didactique principal de cette activité est d'établir un rapport de l'élève à l'objet du savoir « sous graphe complet » qui consiste à en tenir compte en premier lieu dans toute situation de coloriage. Activité 5 page 93 i)Enoncé : On donne le graphe ci-contre : 1) Déterminer tous les sous graphes complets d'ordre 4. 2) Vérifier que quatre couleurs sont suffisantes pour colorier le graphe. ii)Analyse praxéologique: La question 1) : Déterminer tous les sous graphes complets d'ordre 4. Tâche et type de tâche : Pour la tâche, il s'agit de déterminer les sous graphes complets d'un graphe donné sous la forme d'un schéma. Cela appartient au type de tâche T= «Déterminer les sous graphes complets d'un graphe donné». Il s'agit d'une tâche problématique. Technique : On sélectionne un sous graphe d'ordre 4 et on vérifie s'il est complet. On peut éliminer visuellement la majorité des sous graphes d'ordre 4. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: Les sommets qui engendrent le sous graphe d'ordre 4 sélectionné. -Ostensifs déictiques et visuels relevant du registre de la gestualité : soit l'utilisation de la deixis gestuelle ou la gestuelle visuelle pour la désignation des sous graphes d'ordre 4. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les gestes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Graphe complet, sommets adjacents. Bloc technologico- théorique :
La question 2) : Vérifier que quatre couleurs sont suffisantes pour colorier le graphe. Tâche et type de tâche : Pour la tâche, il s'agit de colorier le graphe ci-dessus par quatre couleurs. Cela appartient au type de tâche T= «Colorier un graphe en utilisant k couleurs, k donné». Il s'agit d'une tâche routinière. Technique : On trouve un seul sous graphe complet d'ordre 4, il suffit de le colorier et compléter le coloriage du graphe. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs matériels relevant du registre de la matérialité quelconque : Les couleurs des sommets qui engendrent le sous graphe d'ordre 4 sélectionné. -Ostensifs déictiques et visuels relevant du registre de la gestualité : on montre la coloration au fur et à mesure de sa mise en place. -Ostensifs scripturaux relevant du registre de la trace: Le texte accompagnant la mise en place de la coloration. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les gestes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Pour colorier un graphe, on commence par colorier un sous graphe complet d'ordre maximal. Bloc technologico- théorique :
iii)Commentaire: Les deux tâches de l'activité sont, par rapport aux activités précédentes, devenues routinières. Ils correspondent à deux praxéologies établies : l'une qui permet de vérifier si un graphe est complet et l'autre servant à colorier un graphe à partir de la coloration d'un sous graphe complet d'ordre maximum. Activité 6 page 93 i)Enoncé : Soit G un graphe d'ordre n. Soit G' un sous graphe complet d'ordre k. Vérifier que ii)Analyse praxéologique: Tâche et type de tâche : Pour la tâche, il s'agit de vérifier l'inégalité donnée. Cela appartient au type de tâche T= «Comparer le nombre chromatique d'un graphe et de l'un de ses sous graphes». Il s'agit d'une tâche routinière. Technique : On observe que le nombre de couleurs à utiliser pour colorier un graphe est certainement supérieur ou égal à celui de tous ses sous graphes. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: Comparaison des nombres chromatiques d'un graphe et d'un sous graphe. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Si un graphe est colorié alors il est de même de tous ses sous graphes. Bloc technologico- théorique :
iii)Commentaire: Cette activité peut être utilisée dans un moment de d'exploration de l'environnement technologico- théorique. Il s'agit, en fait, de préciser la technologie de la tâche t= «montrer que le nombre chromatique d'un graphe est supérieur ou égal à celui de ses sous graphes complets» appartenant au type de tâche T= « montrer que le nombre chromatique d'un graphe est supérieur ou égal à celui de ses sous graphes ». Nous avons déjà relevé l'importance de cette tâche pour la procédure de coloration d'un graphe et la précision du nombre chromatique. Cette activité sera suivie d'un moment d'institutionnalisation. Activité 7 page 93 i)Enoncé : 5 1 2 3 1 2 7 8 6 5 4 4 3 G G' 1) Vérifier que trois couleurs suffisent pour colorer les deux graphes G et G'. 2) Pour les deux graphes G et G', déterminer le plus haut degré de ses sommets. ii)Analyse praxéologique: La question 1) : Vérifier que trois couleurs suffisent pour colorer les deux graphes G et G'. Tâche et type de tâche : Pour la tâche, il s'agit de colorier le graphe ci-dessus par trois couleurs. Cela appartient au type de tâche T= «Colorier un graphe en utilisant k couleurs, k donné». Il s'agit d'une tâche routinière. Technique : On commence par colorer un sous graphe complet d'ordre 3 puis compléter le coloriage du graphe. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs relevant du registre de la matérialité quelconque: Les couleurs des sommets qui engendrent le sous graphe d'ordre 3 sélectionné puis la coloration du reste des sommets. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant la coloration des sommets. -Ostensifs scripturaux relevant du registre de la trace : écriture de la correspondance (sommet- couleur). La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Stratégie pour colorier un graphe : on commence par colorier un sous graphe complet d'ordre maximal. Bloc technologico- théorique :
La question 2) : Pour les deux graphes G et G', déterminer le plus haut degré de ses sommets. Tâche et type de tâche : Pour la tâche, il s'agit de déterminer le plus haut degré de ses sommets donné par son schéma. Cela appartient au type de tâche T= «Détermination du degré maximal d'un graphe». Il s'agit d'une tâche routinière. Technique : On dresse la liste d'adjacence de chaque sommet et on tire le degré maximal. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: Le tableau où son consignés les sommets avec leurs degrés. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Représentation d'un graphe par sa liste d'adjacence. Bloc technologico- théorique :
iii)Commentaire: Les deux tâches de cette activité possèdent déjà des praxéologies et ne vont poser, a priori, aucun problème à l'élève. Elles présentent un moment de l'exploration de l'environnement technologico- théorique pour une propriété de majoration du nombre chromatique. Il ne s'agit pas de démontrer cette propriété mais de l'observer sur deux exemples et de généraliser le résultat sans démonstration même si la démonstration n'est pas difficile à être expliquée aux élèves par l'enseignant. Exercice page 94 i)Enoncé : On désire implanter 7 stations radio dans 7 villes dont les distances mutuelles (en Km) sont données ci-dessous. Sachant que deux stations interfèrent si elles se trouvent à moins de 100 Km l'une de l'autre.
1) Représenter cette situation à l'aide d'un graphe G (deux sommets sont adjacents si la distance séparant les deux villes est inférieure à 100 Km). 2) Vérifier que 3) a/ Vérifier que trois couleurs suffisent pour colorier G. b/ Quel est alors le nombre minimum de longueurs d'onde qu'il faut prévoir pour éviter toute interférence ? ii)Analyse praxéologique: La question 1) : Représenter cette situation à l'aide d'un graphe G (deux sommets sont adjacents si la distance séparant les deux villes est inférieure à 100 Km). Tâche et type de tâche : Pour la tâche, il s'agit de représenter une situation par un graphe. Cela appartient au type de tâche T= «représenter une situation par un graphe». Il s'agit d'une tâche routinière. Technique : On réalise le schéma de la situation en plaçant d'abord les sommets puis, deux sommets si et sj sont reliés par une arête si le nombre figurant dans s'intersection de la ligne i et la colonne j est inférieur à 100. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : La matrice incomplète donnée. -Ostensifs graphiques relevant du registre de la trace : Les sommets et les lignes joignant les sommets. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: - La fonction distance est symétrique. - La comparaison de la distance avec 100 indique une présence ou l'absence de relation. - La ligne traduit cette présence. Bloc technologico- théorique :
La question 2) : Vérifier que Tâche et type de tâche : Pour la tâche, il s'agit de montrer que le nombre chromatique est supérieur à 3. Cela appartient au type de tâche T= «Minoration du nombre chromatique d'un graphe donné». Il s'agit d'une tâche routinière. Technique : On montre qu'il y a un sous graphe complet d'ordre 3. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs déictiques relevant du registre de la gestualité : On montre un sous graphe complet d'ordre 3. -Ostensifs graphiques relevant du registre de la trace : Les sommets et les lignes joignant les sommets du sous graphe complet d'ordre 3. -Ostensifs discursif relevant du registre de l'oralité : Le discours accompagnant les gestes -Ostensifs scripturaux relevant du registre de la trace : Le texte accompagnant le discours. La manipulation de ces ostensifs est guidée par les non- ostensifs suivants: - La fonction distance est symétrique. - La comparaison de la distance avec 100 indique une présence ou l'absence de relation. - La ligne traduit cette présence. Bloc technologico- théorique
La question 3)a/ Vérifier que trois couleurs suffisent pour colorier G. Tâche et type de tâche : Pour la tâche, il s'agit de colorier le graphe ci-dessus par trois couleurs. Cela appartient au type de tâche T= «Colorier un graphe en utilisant k couleurs, k donné». Il s'agit d'une tâche routinière. Technique : On commence par colorer un sous graphe complet d'ordre 3 puis compléter le coloriage du graphe. Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs matériels relevant du registre de la matérialité quelconque : Les couleurs des sommets qui engendrent le sous graphe d'ordre 3 sélectionné. -Ostensifs déictiques relevant du registre de la gestualité : par la deixis gestuelle, on montre les couleurs à éviter ou à choisir. -Ostensifs discursifs relevant du registre de l'oralité : le discours accompagnant les gestes. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Stratégie pour colorier un graphe : on commence par colorier un sous graphe complet d'ordre maximal. Bloc technologico- théorique :
La question 3)b/ : Quel est alors le nombre minimum de longueurs d'onde qu'il faut prévoir pour éviter toute interférence ? Tâche et type de tâche : Pour la tâche, il s'agit de déterminer le nombre chromatique du graphe en utilisant les questions précédentes. Cela appartient au type de tâche T= «Déterminer le nombre chromatique». Il s'agit d'une tâche routinière. Technique : On déduit des questions
précédentes que Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : Les deux inégalités, la traduction écrite en langage vernaculaire. -Ostensifs discursifs relevant du registre de l'oralité: le discours en langage vernaculaire. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -une condition suffisante sur un minimum se traduit par une majoration. Bloc technologico- théorique :
iii)Commentaire: Les tâches de cette activité possèdent, au moment de leur déroulement, des praxéologies. Cependant, il convient de noter que :
Activité 1 page 95 i)Enoncé : Le graphe ci-dessous représente un réseau routier. Sur ses arêtes on a marqué les distances séparant deux villes. Entre Bizerte et le Kef trouver le plus court chemin. Bizerte 140 65 Tabarka Tunis 70 166 Jendouba 175 63 Le Kef ii)Analyse praxéologique: Tâche et type de tâche : Pour la tâche, il s'agit de trouver un plus court chemin entre Bizerte et Le Kef. Cela appartient au type de tâche T= «Trouver un plus court chemin entre deux sommets d'un graphe». Il s'agit d'une tâche problématique. Technique : On procède de la manière suivante :
Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace : Les distances, les pondérations, les sommets sélectionnés et L'ensemble S. -Ostensifs discursifs relevant du registre de l'oralité: Le discours accompagnant les manipulations écrites. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Toute sous chaîne d'une chaîne minimale est minimale. Bloc technologico- théorique :
iii)Commentaire: Les données simples de cette activité permettent à celle-ci d'être un bon support pour une introduction à l'algorithme de Moore- Djikstra. Car cet algorithme se base essentiellement sur le lemme prouvant que toute sous chaîne d'une plus courte chaîne est une plus courte chaîne et qui n'est pas connue des élèves. Cependant, ce lemme peut être évoqué à la suite de cet exemple pour mieux appréhender l'algorithme. Activité 3 page 95 i)Enoncé : On a représenté ci-dessous un réseau d'ordinateurs qu'un virus informatique vient d'infecter par l'ordinateur A. On a noté sur les arêtes les temps (en minutes) que met un fichier infecté pour aller d'un ordinateur à un autre.
B 4 D 4 2 2 3 E A 1 3 C 1) Au bout d'une minute le virus est-il arrivé en B ? En C ? 2) a/ Reproduire le graphe ci-dessus et colorier en rouge tous les ordinateurs atteints par le virus au bout d'une minute. b) Indiquer, à côté du sommet C et entre parenthèses, de quel ordinateur est venue l'attaque. 3) Quel est l'ordinateur atteint ensuite ? Au bout de combien de temps ? Le colorier en rouge. 4) Y a-t-il un ordinateur sain qui est atteint par le virus à la troisième minute ? À la quatrième minute ? Le colorier en rouge et indiquer aussi de quel ordinateur est venue l'attaque. 5) Recopier et compléter le tableau suivant :
6) Indiquer pourquoi il n'est pas utile de continuer après la sixième minute. 7) Indiquer le parcours du virus pour atteindre le plus rapidement possible l'ordinateur E. ii)Analyse praxéologique: Les questions : 1, 2, 3 et 4 : 1) Au bout d'une minute le virus est-il arrivé en B ? En C ? 2) a/ Reproduire le graphe ci-dessus et colorier en rouge tous les ordinateurs atteints par le virus au bout d'une minute. b) Indiquer, à côté du sommet C et entre parenthèses, de quel ordinateur est venue l'attaque. 3) Quel est l'ordinateur atteint ensuite ? Au bout de combien de temps ? Le colorier en rouge. 4) Y a-t-il un ordinateur sain qui est atteint par le virus à la troisième minute ? À la quatrième minute ? Le colorier en rouge et indiquer aussi de quel ordinateur est venue l'attaque. Tâche et type de tâche : Pour la tâche, il s'agit d'effectuer une lecture graphique pour trouver les ordinateurs infectés au bout de k minutes. Cela appartient au type de tâche T= «Trouver les sommets s tels que la distance de A è S est égale à k, k donné». Il s'agit d'une tâche routinière, vu les données. Technique : On procède de la manière suivante :
Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: Les distances et les sommets sélectionnés. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Ne pas construire un cycle. Bloc technologico- théorique : Absence de discours technologique.
La question 513(*)) Recopier et compléter le tableau suivant :
Tâche et type de tâche : Pour la tâche, il s'agit d'effectuer une lecture graphique pour trouver les ordinateurs infectés au bout de k minutes et provenance de l'attaque. Cela appartient au type de tâche T= «Trouver les sommets s tels que la distance de A è S est égale à k, k donné et déterminer le dernier sommet contaminé avant S». Il s'agit d'une tâche routinière, vu les données. Technique : On procède de la manière suivante :
Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: Les distances et les sommets sélectionnés. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Tout sous chemin d'un plus court chemin est un plus court chemin. Bloc technologico- théorique :
Les questions 6) : Indiquer pourquoi il n'est pas utile de continuer après la sixième minute. Tâche et type de tâche : Pour la tâche, il s'agit de déduire des réponses précédentes que tous les cas sont épuisés et le plus court chemin entre les sommets A et E. Cette tâche appartient au type de tâche T= « Montrer l'exhaustivité des cas étudiés » Il s'agit d'une tâche routinière, vu les données. Technique : On procède de la manière suivante :
Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: L'ensemble des ordinateurs contaminés. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Raisonnement par exhaustion. Bloc technologico- théorique :
Les questions 7) : Indiquer le parcours du virus pour atteindre le plus rapidement possible l'ordinateur E. Tâche et type de tâche : Pour la tâche, il s'agit de déduire, le plus court chemin entre les sommets A et E. Cette tâche appartient au type de tâche T= « Déterminer le plus court chemin entre deux sommets » Il s'agit d'une tâche routinière, puisque les données sont visibles sur le tableau. Technique : On procède de la manière suivante :
Cette technique présuppose la manipulation des ostensifs suivants : -Ostensifs scripturaux relevant du registre de la trace: L'ensemble des ordinateurs contaminés. La manipulation de ces ostensifs est guidée par le non- ostensif suivant: -Raisonnement par exhaustion. Bloc technologico- théorique :
iii)Commentaire : Les tâches de cette activité sont facilement réalisables et présentent dans l'ordre les étapes de l'algorithme de Moore - Djikstra. Il s'agit, en fait d'une contextualisation de cet algorithme qui se termine, par sa décontextualisation, à l'énoncé en langage vernaculaire (et non en langage formel) de l'algorithme en question. * 6 La coloration d'un sommet est assimilée à la fixation sur le sommet d'une punaise coloriée. * 7 On a : -Pour le graphe G1 : d(1)+d(2)+d(3)=2+2+2=6. -Pour le graphe G2 : d(A)+d(B)+d(C)+d(D)+d(E)=2+3+2+3+2=12. -Pour le graphe G3 : d(1)+d(2)+d(3)+d(4)+d(5)=2+4+2+4+2=14. -Pour le graphe G4 : d(a)+d(b)+d(c)+d(d)+d(e)+d(f)= 3+3+4+4+2+4+2=22. * 8 On a : -Pour le graphe G1 : 1-2, 1-3, 2-3. Donc : 3 arêtes. -Pour le graphe G2 : A-B, A-E, B-C, B-D, C-D, D-E. Donc : 6 arêtes. -Pour le graphe G1 : 1-2, 1-4, 2-3, 2-4, 2-5, 3-4, 4-5. Donc : 7 arêtes. -Pour le graphe G1 : a-b, a-d, a-e, b-c, b-d, c-d, d-f, c-g, c-f, g-f, e-f. Donc : 11 arêtes. * 9
* 10 * 11 3+3+3+3+1+1+d(S7)=14+d(S7). Cette somme doit être paire d'après le lemme des poignées de mains et donc d(S7) doit être pair. D'où l'on tire qu'il est impossible d'avoir d(S7)=1. * 12 Il y a * 13
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
j
».
est
routinisée dès la fin du premier paragraphe
intitulé :Notion de graphe.
est bien
définie.
.
d'après les deux encadrements trouvés dans les questions
3 et 4.
.
.
alors 
k.
3.
3.
=3 et on
traduit ce résultat en langue vernaculaire.
paires.