Vous possédez une centrale de production électrique et vous souhaitez transporter l’électricité vers un consommateur. Pour cela, vous allez utiliser le réseau constitué de lignes électriques qui passent par des répartiteurs. Chaque ligne ne peut transférer qu’un débit limité de courant, correspondant à l’intensité maximale qu’elle peut supporter. Vous cherchez à acheminer le maximum d’électricité entre la centrale de production et le client, tout en respectant les capacités des lignes électriques. Comment procéder ?
Un graphe pour modéliser le réseau électrique
Ce problème va être modélisé à l’aide de la théorie des graphes. Les arcs représentent les lignes électriques avec un sens de circulation du courant, et les sommets (ou nœuds) modélisent les répartiteurs, la centrale et le client (voir la figure ci-dessous).
