Graphe non orienté
Algo 15
Résumé du cours
Définition et vocabulaire
- Un graphe est une collection d’éléments (sommets) mis en relation entre eux par des arêtes.
- L’ordre d’un graphe est le nombre de ses sommets.
- Un graphe non orienté a des arêtes qui peuvent être parcourues dans les deux sens.
- Deux sommets reliés par une arête sont dits adjacents.
- Le degré d’un sommet est le nombre d’arêtes qui y sont connectées.
Propriétés
- La somme des degrés d’un graphe est toujours paire.
- Un arbre est un graphe sans cycle.
Représentations en mémoire
Matrice d’adjacence
- Représentation mathématique où aij = 1 si les sommets i et j sont reliés, 0 sinon.
- Pour un graphe non orienté, la matrice est symétrique.
- Peut être gourmande en mémoire si le graphe est peu dense.
Dictionnaire d’adjacence
- Liste les sommets adjacents à chaque sommet.
- Généralement plus économe en mémoire pour les graphes peu denses.
Passage d’une structure à l’autre
- Il est possible de convertir une représentation en une autre selon les besoins.