Un graphe de sommets (indices par i) et arcs (indices par j) est décrit par les tableaux ci dessous :

i	1	2	3	4	5	6	7	8
	3	2	1	2	0	2	2	1

j	1	2	3	4	5	6	7	8	9	10	11	12	13
	3	5	8	3	6	8	2	7	3	8	1	3	5

On rappelle que désigne le nombre d’arcs ayant le sommet comme extrémité initiale, c’est à dire le nombre de successeurs de . Le tableau liste dans l’ordre lexicographique les extrémités terminales des arcs issus de (c’est à dire les successeurs de ) puis celles des arcs issus de et ainsi de suite. Ainsi a 3 successeurs qui sont et .

1. Quel est l’intérêt informatique de cette représentation d’un graphe ?

2. Construire le graphe à grande échelle, après avoir déterminé son entrée et sa sortie. On disposera les sommets de telle sorte que les arcs ne s’intersectent pas.

3. En fait, dans un contexte d’ordonnancement, tout arc représente une tâche et est valué par une durée donnée dans le tableau ci-dessous : tout sommet correspond à évènement (étape). Le graphe obtenu est le graphe PERT d’un projet comportant 13 tâches (sans tâches fictives). Donner l’indice du sommet "débuté et celui du sommet "fin" de ce projet.

	A	B	C	D	E	F	G	H	I	J	K	L	M
j	1	2	3	4	5	6	7	8	9	10	11	12	13
	4	2	1	3	3	2	1	5	1	3	2	2	1

Retracer le graphe en représentant chaque tâche par une lettre et valuer l’arc correspondant par sa durée.

4. Calculer les dates au plus tôt et au plus tard des étapes.

5. Donner le chemin critique

6. Calculer les marges totales et libres des tâches