Mathématique

Imprimer la section

Mathématiques discrètes

Graphes

L’introduction à la théorie des graphes fournit aux élèves de la séquence Culture, société et technique des nouveaux outils pour analyser des situations et raisonner autrement. Cette théorie est utilisée pour modéliser des situations et les optimiser au besoin, tant dans les différents champs de la mathématique (ex. : arbre en probabilités, représentation d’un polyèdre convexe [graphe planaire]) que dans des domaines aussi divers que les sciences sociales, la chimie, la biologie ou l’informatique. Les situations exploitées permettent de mettre en relation différents éléments relatifs à la planification de tâches, à la gestion d’horaires ou d’inventaires, à des réseaux de communication ou de distribution, à des circuits (électriques ou autres), à des incompatibilités (interactions), à des localisations, à des stratégies, etc.

Pour représenter une situation à l’aide d’un graphe, les élèves choisissent les éléments de la situation à mettre en relation et ils associent ces éléments aux composantes du graphe, c’est-à-dire les sommets et les arêtes. La terminologie concernant les graphes est introduite au fur et à mesure que les termes apparaissent dans les situations proposées. Il ne s’agit pas de mémoriser un ensemble de définitions. Les propriétés sont également introduites à l’occasion de situations d’exploration1.

Les tableaux qui suivent présentent les connaissances relatives aux graphes. C’est en s’appuyant sur les concepts et les processus visés que les élèves peuvent développer les trois compétences du programme. Le fait de développer ces compétences leur permet en retour de mieux intégrer les concepts et processus mathématiques en cause.

Théorie du choix social
Matrices

Introduction à la théorie des graphes  

L’élève apprend à le faire avec l’intervention de l’enseignante ou de l’enseignant.

L’élève le fait par lui-même à la fin de l’année scolaire.

 

L’élève réutilise cette connaissance.

Primaire

Secondaire
1er
cycle
2e
cycle
  1. Concepts associés à la théorie des graphes
6e 1re 2e 3e 4e 5e
  1. Décrire les éléments de base de la théorie des graphes : degré, distance, chaîne, cycle
          CST
    TS
    SN
  1. Reconnaître une chaîne eulérienne, un cycle eulérien, une chaîne hamiltonienne ou un cycle hamiltonien
          CST
    TS
    SN
  1. Construire des graphes : graphe orienté, graphe valué (pondéré), graphe coloré, arbre
          CST
    TS
    SN
  1. Dégager les propriétés des graphes
          CST
    TS
    SN
  1. Analyse de situations, optimisation et prise de décisions
6e 1re 2e 3e 4e 5e  
  1. Déterminer les éléments de la situation associés aux sommets et aux arêtes
          CST
    TS
    SN
  1. Représenter une situation à l’aide d’un graphe
          CST
    TS
    SN
  1. Comparer des graphes, au besoin
          CST
    TS
    SN
  1. Rechercher, selon la situation, la chaîne ou le cycle eulérien et hamiltonien, le chemin critique, la chaîne la plus courte, l’arbre de valeurs minimales ou maximales ou le nombre chromatique
          CST
    TS
    SN

Théorie du choix social
Matrices

1.  Se référer aux pistes d’exploration contenues à l’annexe E du programme de mathématique du 2e cycle du secondaire, p. 128.

Haut de page