Graphes et ordonnancement

1Maîtriser le vocabulaire de la théorie des graphes : sommet, arête, degré, chemin, cycle.

2Distinguer graphes orientés et non orientés ; lire et construire une matrice d'adjacence.

3Reconnaître les graphes particuliers : arbres, graphes eulériens, hamiltoniens, bipartis.

4Appliquer l'algorithme de Dijkstra pour trouver le plus court chemin dans un graphe pondéré.

5Construire un arbre couvrant minimal (algorithmes de Kruskal et Prim).

6Modéliser un projet par un réseau PERT : tâches, dépendances, dates au plus tôt et au plus tard.

7Identifier le chemin critique et calculer les marges totale et libre.

8Construire et interpréter un diagramme de Gantt.