Introduction aux graphes simples et orientés en olympiade. On étudie les notions de degré, chemin, cycle, connexité, ainsi que les graphes particuliers (arbres, planaires, bipartis). Les outils principaux sont le lemme des poignées de main, la formule d'Euler pour les graphes planaires, et la coloration.
Théorie des graphes — Résumé de cours
1ère Année Collège — Atlasmaths.ma
Cours complet
Contenu du cours
🔑 Formules clés à retenir
- Lemme des poignées de main : .
- Formule d'Euler (planaires) : pour un graphe planaire connexe.
- Borne pour un graphe planaire simple ().
- Théorème des 4 couleurs : tout graphe planaire est 4-coloriable.
- Théorème de Kuratowski : un graphe est planaire ssi il ne contient pas de subdivision de ou .
⚠️
Astuces & Pièges à éviter
Les erreurs classiques — à lire avant les exercices !
- Compter les arêtes via la somme des degrés (poignées de main).
- Coloration : descente — supposer un coloriage minimal et chercher une contradiction.
- Argument de l'extrémal : prendre le sommet de degré max/min pour amorcer la preuve.
- Graphe biparti ⇔ aucun cycle impair.
— Exercice bonus
—
Cet exercice a été ajouté récemment. Besoin d'aide ? Demande à Mentor →