Leçon 5 sur 5
Introduction à la théorie des graphes
Je sais modéliser une situation par un graphe, utiliser le vocabulaire de base (degré, chaîne, cycle, connexité, arbre), représenter un graphe par une matrice d'adjacence, reconnaître un graphe eulérien et calculer un plus court chemin avec l'algorithme de Dijkstra.
- 1 h 15
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Modéliser un problème par un graphe orienté ou non orienté
- Utiliser degrés, chaînes, cycles, connexité et appliquer le lemme des poignées de main
- Représenter un graphe par une matrice d'adjacence et reconnaître un arbre
- Déterminer si un graphe admet une chaîne eulérienne et appliquer l'algorithme de Dijkstra
Avant de commencer : Ensembles et relations (leçon 2) ; récurrence et dénombrement (leçon 3).
1Je découvre
Une entreprise fictive de transport veut relier Conakry à Labé en passant par les villes du réseau routier. Le planificateur dessine les villes comme des points et les routes comme des traits, en notant les distances. Il se pose plusieurs questions : quel est l'itinéraire le plus court ? Un camion de livraison peut-il parcourir chaque route une seule fois et revenir à son point de départ ? Combien de routes au minimum faut-il entretenir pour que toutes les villes restent reliées ?
Ce dessin de points et de traits est un graphe. Les mêmes outils servent à modéliser un réseau social, Internet, un réseau électrique ou les dépendances entre les modules d'un programme.
Qu'est-ce qu'un graphe, quel vocabulaire permet de l'étudier, et comment résoudre avec lui des problèmes de parcours et de plus court chemin ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.