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
Lun 10 Nov - 17:27
