Mathematics

Print section

Discrete Mathematics

Graphs

Social Choice
Matrices

In learning about graph theory, students in the Cultural, Social and Technical option acquire new tools for analyzing situations and are introduced to a different way of reasoning. This theory is used to model and, if necessary, to optimize situations in different branches of mathematics (e.g. tree diagrams in probability, the representation of convex polyhedrons [planar graph]) and in various fields such as social sciences, chemistry, biology or computer science. It can be used to relate various elements associated with task planning, scheduling or inventory management, communication or distribution networks, electric or other types of circuits, incompatibilities (interactions), localizations, strategies, and so on.

To draw a graph for a given situation, students must choose the elements that will be represented by vertices and those that will be represented by edges. The terms associated with graphs are introduced as they arise in the situations presented; however, the point is not to memorize a series of definitions. The properties are also introduced during exploration activities.1

The following tables present the learning content associated with graphs. By basing themselves on the concepts and processes targeted, students develop the three competencies of the program, which in turn enable students to better integrate the mathematical concepts and processes presented.

Introduction to graph theory  

Student constructs knowledge with teacher guidance.

Student applies knowledge by the end of the school year.

 

Student reinvests knowledge.

Elementary

Secondary
Cycle
One
Cycle
Two
  1. Concepts associated with graph theory
6 1 2 3 4 5
  1. Describes the basic elements of graph theory: degree distance, path, circuit
          CST
    TS
    S
  1. Recognizes Euler paths or circuits and Hamiltonian paths or circuits
          CST
    TS
    S
  1. Constructs graphs: directed graphs, weighted graphs, coloured graphs, trees
          CST
    TS
    S
  1. Identifies properties of graphs
          CST
    TS
    S
  1. Situation analysis, optimization and decision making
6 1 2 3 4 5  
  1. Determines elements of a situation associated with vertices and edges
          CST
    TS
    S
  1. Represents a situation using a graph
          CST
    TS
    S
  1. Compares graphs, if necessary
          CST
    TS
    S
  1. Finds Euler and Hamiltonian paths and circuits, the critical path, the shortest path, the tree of minimum or maximum values or the chromatic number, depending on the situation
          CST
    TS
    S
1.  See Avenues of Exploration in Appendix E of the Secondary Cycle Two Mathematics program, p. 124.

Haut de page