INF1231 - Mathématiques discrètes 2  

Dans ce cours, on présente les notions élémentaires sur la théorie des graphes : les définitions et propriétés de base ainsi que les algorithmes élémentaires. L'objectif visé est de monter comment les graphes peuvent être une méthode de résolution de problèmes. Ce cours ne demande pas de connaissances préalables autres que celles détenues par de nouveaux bacheliers de série S. Les deux notions de graphes qui sont abordées sont : les graphes orientés et les graphes non orientés. La première partie comporte beaucoup de définitions du fait que la théorie des graphes utilise un jargon particulier. Les exercies proposés dans ce cours sont essentiellement de deux types : des exercices théoriques sous forme de démonstration assez simple généralement par indiction ou par l'absurde; des exercices pratiques où on utilise des graphes pour la modélisation de problème afin de les résoudre.