L’UE est découpée en 2 parties.

La 1^ère partie est dédiée à un court historique, associé aux premières définitions (sommets, arêtes ou arcs, avec notamment les premiers théorèmes liés aux degrés des sommets). Nombreux exemples en TD, où il s’agit de modéliser sous forme graphique. On apprend à représenter les graphes grâce aux matrices d’adjacence (avec application en TP, à l’existence de chemin, ou de connexité), ou aux matrices d’incidence (avec application en TP, au calcul de cycles indépendants ou du nombre de composantes connexes), ou aux listes de successeurs, ou prédécesseurs (avec application en TP, au calcul d’arbres en profondeur).

La 2^ème partie est liée aux cheminements (chaînes, chemins, cycles, circuits). Plusieurs algorithmes permettent de déterminer les composantes connexes, ou fortement connexes, en utilisant les arbres en profondeur, ou le calcul explicite des fermetures transitives. Les chaînes ou chemins eulériens sont évoqués, et cette partie s’achève sur des propriétés des graphes planaires.

À la fin de cette UE/EC, vous serez capable de :

• Modéliser sous forme graphique un problème (sommet, arc ou arête), et lister les principales propriétés du graphe
• Identifier le problème à résoudre, à partir du modèle graphique, et l’associer à des grandes classes de problèmes de la théorie de graphes.
• Représenter le graphe par matrice d’adjacence, d’incidence, ou listes ce graphe
• Mettre en place des algorithmes permettant de parcourir de manière arborescente en profondeur ces graphes, d’ajouter des numérotations préfixes ou suffixes, de trouver des forêts en profondeur
• Mettre en place des algorithmes permettant de trouver des composantes fortement connexes : exploitant les arbres de successeurs ou prédécesseurs, ou exploitant la numérotation suffixe, ou exploitant la fermeture transitive.

Algèbre linéaire

Évaluation continue intégrale (ECI) 100%

Poursuites possibles : L3 NEC : UE Théorie des graphes 2