Graphe orienté
Algo 15
Résumé du cours
Graphes orientés
Les graphes orientés sont caractérisés par des arêtes qui ne peuvent être parcourues que dans un seul sens. Voici les points clés :
- Degré d’un sommet : On distingue le degré entrant (d-) et le degré sortant (d+).
- Propriété : La somme des degrés entrants et sortants d’un graphe est toujours paire.
- Sommets adjacents : On différencie les prédécesseurs et les successeurs.
Représentation en mémoire
Matrice d’adjacence :
- Matrice non symétrique pour les graphes orientés.
- Les lignes représentent les sommets de départ, les colonnes les sommets d’arrivée.
Dictionnaire d’adjacence :
- On peut créer un dictionnaire des successeurs et un dictionnaire des prédécesseurs.
Graphes pondérés
Les graphes pondérés attribuent un poids à chaque arête.
Représentation en mémoire
Matrice d’adjacence :
- Les valeurs non nulles représentent le poids des arêtes.
- Pour un graphe non orienté et pondéré, la matrice est symétrique.
Dictionnaire d’adjacence :
- Peut être modifié pour inclure les poids des arêtes.
- Exemple de structure :
{"A": [("B", 5), ("C", 4), ("F", 6)], ...}.