Soit le graphe de sommets et arcs, valué par des capacités et défini par les tableaux suivants :

• Le tableau NARC désigne le demi-degré extérieur de chacun des sommets du graphe. indique le nombre d’arcs ayant le sommet comme extrémité initiale.

	1	2	3	4	5
	1	2	2	0	2

• Le tableau SUCC liste d’abord les successeurs (s’ils existent) du sommet 1, puis du sommet 2 et ainsi de suite. désigne l’indice du sommet qui est l’extrémité terminale de l’arc d’indice  : On à numéroté les arcs en commencant par ceux issus du sommet 1, puis du sommet 2, etc
  

	1	2	3	4	5	6	7
	4	1	4	2	5	1	2

• Le tableau CAPA désigne la capacité de l’arc d’indice

	1	2	3	4	5	6	7
	1	4	7	3	5	2	2

• Le tableau FLOT indique le flot transporté sur l’arc d’indice

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

1. Tracer le graphe G à grande échelle. On doit trouver pour chaque arc son numéro, sa capacité entre crochet et le flot transporté. Le tout devant apparaitre très clairement et très lisiblement.
2. Donner la valeur du flot défini dans le tableau FLOT.
3. Ce flot est-il complet ?
4. Déterminer toutes les coupes du réseau de transport et donner leur capacité. Donner la coupe de capacité minimale. Le flot est-il optimal ?
5. Sinon l’optimiser en utilisant l’algorithme de Ford-Fulkerson.