Leçon 5 sur 5
Graphes eulériens, hamiltoniens et coloration
Je sais reconnaître un graphe eulérien grâce au théorème d'Euler, distinguer les problèmes eulériens et hamiltoniens, et colorier un graphe pour résoudre un problème d'incompatibilités.
- 1 h 10
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Énoncer et appliquer le théorème d'Euler sur les cycles et chaînes eulériens
- Distinguer graphe eulérien et graphe hamiltonien et connaître une condition suffisante (Dirac)
- Définir coloration et nombre chromatique et l'encadrer
- Appliquer un algorithme glouton (Welsh-Powell) à un problème de planification
Avant de commencer : Leçons 1 à 4 de ce cours (degrés, chaînes, cycles, connexité, graphes bipartis).
1Je découvre
Un agent de la voirie de Kindia doit inspecter toutes les rues d'un quartier après de fortes pluies. Il aimerait parcourir chaque rue exactement une fois et revenir à son point de départ, sans repasser inutilement par une rue déjà vue. Est-ce toujours possible ? Il s'aperçoit vite que non : tout dépend de la manière dont les rues se croisent aux carrefours.
Au même moment, un livreur se pose une question qui ressemble à la première mais qui est très différente : passer chaque client exactement une fois et revenir au dépôt.
Enfin, le service de la scolarité de l'université doit programmer les examens de fin de semestre. Deux examens suivis par un même étudiant ne peuvent pas avoir lieu au même créneau. Combien de créneaux faut-il au minimum ?
Ces trois questions sont des classiques de la théorie des graphes ; la première est à son origine même.
Quand peut-on parcourir toutes les arêtes, ou tous les sommets, d'un graphe une seule fois, et comment colorier un graphe avec le moins de couleurs possible ?
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.