Définition et propriété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.
- Propriétés
- La somme des degrés d’un graphe est toujours paire.
- Un arbre est un graphe sans cycle.
Représentation 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.
Propriétés
Les graphes pondérés attribuent un poids à chaque arête.Représentation 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)], ...}