Introduction aux graphes et leurs propriétés

📋 Plan du Cours

1. Ponts de Königsberg et circuit eulérien
2. Définitions des graphes et arêtes
3. Types de graphes : planaire, simple, connexe
4. Degré des sommets et propriétés
5. Sous-graphes, sous-graphes induits et couvrants
6. Isomorphisme de graphes
7. Chaînes et cycles dans un graphe
8. Connexité et composantes connexes
9. Représentations non graphiques : matrices et listes

📖 1. Ponts de Königsberg et circuit eulérien

🔑 Notions clés & Définitions

• Euler : Personne à l’origine de la formalisation du problème des ponts de Königsberg en 1736.
• Circuit eulérien : Circuit qui parcourt chaque arête exactement une fois tout en revenant au point de départ.
• Graphe de Königsberg : Modélisation du problème où les ponts deviennent des arêtes et les zones terrestres deviennent des sommets.

📝 Points essentiels

• Le problème de 1736 demande de revenir au point de départ en empruntant chaque pont une seule fois.
• La modélisation transforme les ponts en arêtes et les zones en sommets.
• La question devient l’existence d’un circuit qui utilise chaque arête exactement une fois et revient au départ.
• Dans le cas présenté, la réponse à l’existence d’un tel circuit est non.

💡 Astuce mémo

Ponts → arêtes, zones → sommets, puis “une fois chaque arête” pour chercher un circuit.

📖 2. Définitions des graphes et arêtes

🔑 Notions clés & Définitions