Théorie des Graphes (programme)

Programme :

o Notions fondamentales de la théorie des graphes

· Définitions d’un graphes et différentes représentations

· Applications multi-graphes

· Applications multivoque, degré, demi degré, cycles, cocycles, connexité…

o Les nombres fondamentaux de la théories des graphes

· Nombres de stabilités

· Noyau, fonction ordinale, fonction de Grundy

· Nombre chromatique, clique, théorème de Koening

o Graphes particuliers

· Graphes planaires, Graphe dual

· Graphes aux arêtes, graphes aux arcs

o Arbres et Arborescence

· Construction d’un arbre

· Construction d’une forêt

· Algorithme de Kruskall (cycles et cocycles)

· Algorithme de Sollin

o Problèmes de flots

· Définitions

· Cycles élémentaires et flots élémentaires

· Problème du flot maximal dans un réseau de transport

· Graphe d’écart

· Algorithme de recherche du flot maximal (Ford-Fulkerson)

o Problèmes du plus court chemin

· Introduction au problème du plus court chemin

· Algorithme de Dantzig

· Algorithme de Ford

· Algorithme de Dijkstra

o Méthodes d’ordonnancement

· Diagramme de Gantt

· Méthode PERT

· Méthode MPM