Ticker

6/recent/ticker-posts

Header Ads Widget

Cour TG : Réseaux de flots



La 4ème partie du cours de la théorie des graphes est en pièce jointe pour les étudiants de 2ème année info.



Les réseaux de flots aussi appelé réseaux de transport permettent de modéliser une très large classe de problèmes. Leur interprétation correspond à la circulation de flux physiques sur un réseau : il pourra s’agir d’une distribution électrique ou circuits électriques, le mouvement d’un fluide (eau, gaz, pétrole, ...) parcourant des canalisations, des véhicules se déplaçant sur des voies et transportant des marchandises ou acheminement de paquets sur Internet, ...etc. Il s'agit d'acheminer la plus grande quantité possible de matière entre un nœud d’entrée (une source s) et un nœud de sortie ou de destination (un puits t) en passant par des nœuds intermédiaires ou de transit. Les liens entre les nœuds (les arcs) ont une capacité limitée (un poids). Le cumul des flots sur un arc ne peut pas excéder sa capacité, et il n'y a ni perte ni création de matière lors de l'acheminement: Pour qu'un flot soit valide, il faut que la somme des flots atteignant un nœud soit égale à la somme des flots quittant ce nœud, sauf s'il s'agit d'une source s (qui n'a pas de flot entrant), ou d'un puits t (qui n'a pas de flot sortant).