Séance de cours

Flow Networks : la méthode Ford-Fulkerson

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, s ...

Description

Cette séance de cours couvre les réseaux de flux, les flux et la méthode Ford-Fulkerson. Il explique la définition formelle d'un réseau de flux, le concept de flux et la méthode pour trouver le flux maximal dans un réseau. L'instructeur présente la méthode Ford-Fulkerson, détaillant les étapes impliquées et fournissant des exemples de son application. La séance de cours traite également des réseaux résiduels, des coupures dans les réseaux de flux et du calcul du flux net à travers une coupure. Diverses définitions et contraintes liées aux réseaux de flux sont explorées, soulignant l'importance des contraintes de capacité et des principes de conservation.

Enseignant·e·s (3)

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Mikhail Kapralov

Enseignement et PhD Doctorant·es actuel·les Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth A dirigé les thèses EPFL de Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail A co-dirigé les thèses EPFL de Paritosh Garg Cours Algorithms II CS-450 Un premier cours de 2eme cycle sur les algorithmes, ce cours a peu de prerequis, mais va vite. Il couvre les techniques principales d'analyse et de

Source officielle

Concepts associés (23)

Théorème flot-max/coupe-min

Le théorème flot-max/coupe-min (ou max flow/min cut en anglais) est un théorème important en optimisation et en théorie des graphes. Il stipule qu'étant donné un graphe de flots, le flot maximum pouvant aller de la source au puits est égal à la capacité minimale devant être retirée du graphe afin d'empêcher qu'aucun flot ne puisse passer de la source au puits. Ce théorème est un cas particulier du théorème de dualité en optimisation linéaire et généralise le théorème de Kőnig, le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).

Conservation de la nature

La conservation de la nature consiste en la protection des populations d'espèces animales et végétales, ainsi que la conservation de l'intégrité écologique de leurs habitats naturels ou de substitution (comme les haies, carrières, terrils, mares ou autres habitats façonnés par les humains). Son objectif est de maintenir les écosystèmes dans un bon état de conservation et de prévenir ou de corriger les dégradations qu'ils pourraient subir. Chronologie de l'écologisme L'écologisme a des racines anciennes et plutôt anglo-saxonnes, qui ont évolué à la fin du .

Biologie de la conservation

La biologie de la conservation (ou écologie de la conservation) est une discipline traitant des questions de perte, maintien ou restauration de biodiversité. Robert Barbault la présente comme une discipline de gestion de crise ; elle vise à identifier les populations en déclin ou relictuelles et les espèces en danger, pour en déterminer les causes de leur déclin, proposer, tester et valider des moyens de remédier à ce déclin (éventuellement provisoirement ex situ).

Problème de flot maximum

thumb|right|Un exemple de graphe de flot avec un flot maximum. la source est , et le puits . Les nombres indiquent le flot et la capacité. Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum. Quelquefois, on ne s'intéresse qu'à la valeur de ce flot. Le s-t flot maximum (depuis la source s vers le puits t) est égal à la s-t coupe minimum du graphe, comme l'indique le théorème flot-max/coupe-min.

Réseau de flot

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).

Afficher plus

Séances de cours associées (18)

Algorithmes graphiques : Ford-Fulkerson et composants fortement connectés

Discute de la méthode Ford-Fulkerson et des composants fortement connectés dans les algorithmes graphiques.

Théorème de Min-Cut Max-Flow

Explore l'équivalence entre le débit maximal et la coupure minimale dans la théorie des réseaux, en démontrant ses applications à travers des exemples et des chemins disjoints.

Max-Flow Problème: Algorithme de Ford-Fulkerson

Explore l'algorithme Ford-Fulkerson pour résoudre le problème Max-Flow et ses applications dans l'optimisation du flux réseau.

Bounded Network Flow: Problème Solvable Minult-Maxcret

Couvre la résolution des problèmes de flux de réseau borné en ajustant les capacités de flux et les contraintes, y compris les programmes binaires.

Réseaux de flux : comprendre les flux et les coupes dans les algorithmes

Couvre les réseaux de flux, en se concentrant sur les flux, les coupes et leurs applications dans les algorithmes.

Afficher plus

Concepts associés (23)

Théorème flot-max/coupe-min

Conservation de la nature

Biologie de la conservation

Problème de flot maximum

Réseau de flot

Afficher plus