Description
Cet ECUE apporte aux étudiants tous les éléments nécessaires à la définition et à la manipulation d’un graphe : représentation, propriétés, algorithmes de base. Plusieurs familles de problèmes pouvant être modélisés par les graphes sont abordés pour illustrer quelques domaines d’applications (Web, réseau, etc). A la fin de cet ECUE les étudiants sont capables d’écrire des algorithmes de manipulation de graphes, et savent modéliser un problème par un graphe.
Contenu :
- Modélisation par un graphe
- Représentation et propriétés d’un graphe
- Parcours d’un graphe (profondeur, largeur)
- Connexité
- Arbre couvrant