Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Réseau de flot
Résumé
En théorie des graphes, un réseau de flot (aussi appelé réseau de transport) est un graphe orienté où chaque arête possède une capacité et peut recevoir un flot (ou flux). Le cumul des flots sur une arête ne peut pas excéder sa capacité. Un graphe orienté est souvent appelé réseau en recherche opérationnelle. Les sommets sont alors appelés des nœuds et les arêtes des arcs. 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 (qui n'a pas de flot entrant), ou d'un puits (qui n'a pas de flot sortant). Un réseau peut être utilisé pour modéliser le trafic dans un réseau routier, la circulation de fluides dans des conduites, la distribution d'électricité dans un réseau électrique, ou toutes autres données transitant à travers un réseau de nœuds.
Soit un graphe orienté fini dans lequel chaque arête est associée à une valeur réelle positive . Si , on suppose que . On distingue 2 sommets particuliers: une source et un puits . Un flot dans le réseau est une fonction à valeur réelle qui, pour tous sommets et , vérifie les 3 propriétés suivantes :
Contraintes de capacité
Le flot sur une arête ne peut excéder sa capacité.
Anti-symétrie
Le flot du sommet vers le sommet doit être l'opposé du flot de vers (voir l'exemple).
Conservation du flot
sauf si ou . Le cumul signé des flots entrant et sortant d'un nœud est nul, sauf pour la source qui en produit, ou pour le puits, qui en consomme.
Dit autrement, la conservation du flot entraîne :
pour tout sommet
À noter que est le flot signé de à . Si le graphe représente un réseau physique, et s'il s'agit d'un flot réel de, par exemple, 4 unités de vers , et un flot réel de 3 unités de vers , on a et .
On dit que le flot (au sens général) d'un réseau physique est le flot partant de la source s, soit
La capacité résiduelle d'une arête est . On peut donc définir le réseau résiduel noté , qui indique la quantité de capacité disponible.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.