L'Atelier Monstre

Introduction aux flux Un réseau de flot est un graphe orienté G = (V, E) avec une source s et un puits t. Chaque arête (u, v) possède une capacité c(u, v) ≥ 0. Un flot f est une fonction qui associe à chaque arête une valeur f(u, v) vérifiant : Contrainte de capacité : 0 ≤ f(u, v) ≤ c(u, v) Conservation du flot : pour tout sommet x autre que s ...

Modélisation d'un réseau de flux Un problème de flux en réseau modélise le transport d'une quantité à travers un graphe orienté dont chaque arc possède une capacité maximale. Les applicatoins couvrent la logistique, les télécommunications, la distribution électrique ou encore la planification de tâches. Formellement, on dispose d'un graphe o ...