Médaille
N°1 pour apprendre & réviser du collège au lycée.
Graphes et matrices

Déjà plus de

1 million

d'inscrits !

Prenant appui sur la résolution de problème et la modélisation, cette partie a pour objectif d’introduire les notions de graphes et de matrices en soulignant l’intérêt de les appliquer à d’autres disciplines, notamment les sciences économiques et sociales, les sciences de la vie et de la Terre, la physique-chimie, l’informatique, etc.

Les matrices sont étudiées sous divers points de vue : modélisation de problèmes issus des autres disciplines, systèmes linéaires, transformations géométriques. Il s’agit de mettre en valeur l’efficacité du calcul matriciel pour représenter et résoudre des problèmes.

La notion de graphe est fondamentale pour les mathématiques discrètes et a des applications dans de nombreux domaines. Le programme la fait interagir avec les matrices. Une illustration exemplaire dans le domaine des probabilités, les chaînes de Markov, fait l’objet d’un développement spécifique.

Histoire des mathématiques

L’histoire de cette partie combine trois thèmes très contemporains : les graphes, outils fondamentaux des mathématiques discrètes, les matrices et les chaînes de Markov. Les liens mis en évidence soulignent l’unité et l’efficacité des mathématiques.

L’histoire des graphes remonte au moins à Euler, par exemple à travers le problème des ponts de Königsberg. Des applications plus récentes en intelligence artificielle, concernant notamment les réseaux, soulignent la pertinence et l'actualité de la modélisation à l'aide de graphes et matrices.

La considération de tableaux de nombres en liaison avec les systèmes linéaires est très ancienne, mais l’introduction par Cayley des matrices comme objets de calcul représentant des transformations linéaires date du milieu du XIXe siècle, et leur importance ne sera clairement reconnue qu’au XXe siècle.

L’étude des chaînes de Markov, qui remonte au début du XXe siècle, donne une belle utilisation du formalisme matriciel. Contenus

  • Graphe, sommets, arêtes. Exemple du graphe complet.
  • Exemples de représentations matricielles : matrice d’adjacence d’un graphe ; transformations géométriques du plan ; systèmes linéaires ; suites récurrentes.
  • Sommets adjacents, degré, ordre d’un graphe, chaîne, longueur d’une chaîne, graphe connexe.

Capacités attendues

  • Modéliser une situation par un graphe.
  • Graphe orienté pondéré associé à une chaîne de Markov à deux ou trois états.

Démonstration

  • Expression du nombre de chemins de longueur nn reliant deux sommets d'un graphe à l’aide de la puissance nn-ième de la matrice d’adjacence.