Initier la personne étudiante à la théorie des graphes. Explorer et implémenter différents algorithmes sur les graphes. Appliquer ces notions à travers divers exemples.
Modèles de graphes orientés et non-orientés : modélisation de problèmes à l'aide de graphes, principales familles de graphes (complets, bipartis, cycles, roues, hypercubes), distance, centre, diamètre et rayon, chemins et cycles, arbres, arborescence et forêts. Sous-graphes : isomorphisme, principales opérations sur les graphes, graphes eulériens et hamiltoniens. Représentation : matrices d'adjacence, matrice d'incidence, listes d'adjacence, graphes planaires. Arbres : algorithmes de parcours, arbre couvrant, plus courts chemins. Problème de coloriage de graphes.
Préalable(s): ((8THE105) ou (8MAT122))
Formule pédagogique : Magistral et/ou formation à distance