Introduction à la théorie des graphes

📋 Plan du Cours

1. Notion de graphe
2. Histoire de Euler
3. Exemples de graphes
4. Graphes non-orientés
5. Graphes orientés
6. Chemins et circuits
7. Vocabulaire des graphes
8. Applications des graphes
9. Connexité et composantes
10. Forte connexité
11. Tri topologique
12. Exploration en profondeur

📖 1. Notion de graphe

🔑 Notions clés & Définitions

Graphe
Un graphe est une structure composée d’un ensemble de sommets et d’un ensemble d’arêtes ou arcs qui relient ces sommets. Il sert à modéliser des relations ou des connexions entre différents éléments. La notion de graphe est fondamentale dans l’étude des réseaux, des structures de données ou des systèmes complexes. La définition précise de cette structure est essentielle pour comprendre la modélisation des relations dans divers contextes.

Sommet
Un sommet, aussi appelé nœud, est un élément fondamental d’un graphe. Il représente un point ou un acteur dans la structure, comme une personne dans un réseau social ou une ville dans un réseau de transport. Les sommets sont les entités que l’on relie par des arêtes ou arcs.

Arête
Une arête est une connexion ou un lien entre deux sommets dans un graphe non-orienté. Elle est représentée par une ligne reliant deux sommets. Dans un graphe non-orienté, l’arête n’a pas de direction spécifique, ce qui signifie que la relation qu’elle représente est symétrique.