IFT-7012 Théorie algorithmique des graphes

Ce cours aborde des sujets tels la connexité dans un graphe (problèmes du flot maximum, de la dualité min-max, de couplage parfait, etc.), la planarité d'un graphe (formule d'Euler, théorème de Kuratowski, graphe dual), le coloriage d'un graphe (coloriages entiers et fractionnaires des sommets ou des arêtes, graphes de Kneiser), les problèmes de transversales d'un graphe (parcours eulériens, cycles hamiltoniens, graphes de DeBruijn, etc.) et la notion de marche aléatoire sur un graphe (chaînes de Markov, existence de la distribution limite, « mixing time », etc.). Plusieurs problèmes sur les graphes ont d'élégantes solutions, d'autres évidemment sont NP-complets; une partie de ce cours portera donc sur la théorie de la complexité (problèmes NP et NP-complets, théorème de Cook, algorithmes de réductions).