Fondamentaux des graphes et connexité

📋 Plan du Cours

1. Théorie des graphes
2. Graphes orientés et non orientés
3. Représentations graphiques et matricielles
4. Propriétés des graphes
5. Connexité et composantes
6. Parcours en largeur et profondeur
7. Recherche de composantes fortement connexes
8. Plus courts chemins
9. Algorithme de Kosaraju
10. Algorithme de Bellman-Ford et Floyd-Warshall

📖 1. Théorie des graphes

🔑 Notions clés & Définitions

• Graphe : Représentation mathématique composée d’un ensemble de sommets (nœuds) et d’un ensemble d’arcs ou arêtes reliant ces sommets.
  Exemple : Un réseau de transport.

• Graphe orienté : Graphe où chaque arc possède une direction, représenté par une flèche.
  Notations : $G=(X,U)$ avec $U \subseteq X \times X$.

• Degré d’un sommet : Nombre d’arêtes ou arcs incident à ce sommet.

  • Dans un graphe orienté :
    • Degré entrant ($d^-$) : nombre d’arcs arrivant au sommet.
    • Degré sortant ($d^+$) : nombre d’arcs partant du sommet.
  • Dans un graphe non orienté :
    • Degré ($d$) : nombre d’arêtes incidentes.

• Connexité : Propriété d’un graphe non orienté où chaque paire de sommets est reliée par une chaîne.

  • Composante connexe : Sous-ensemble maximal de sommets reliés entre eux.