Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Bounded Network Flow: Problème Solvable Minult-Maxcret

Dans cours

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

Description

Cette séance de cours couvre le concept de flux de réseau borné, en se concentrant sur la résolution du problème minult-maxcret. Il explique la solvabilité des problèmes de réseau borné en ajustant les capacités de flux. La séance de cours explore également différents concepts duaux et l'ajustement requis pour le problème. En outre, il discute des contraintes et des ajustements nécessaires pour les programmes binaires dans le contexte des flux de réseau.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e·s (2)

Rom Pinchasi

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (32)

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

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.

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

Arbre binaire

En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.

Théorie des réseaux

vignette|Graphe partiel de l'internet, basé sur les données de opte.org du 15 janvier 2005 (voir description de l'image pour plus de détails) La théorie des réseaux est l'étude de graphes en tant que représentation d'une relation symétrique ou asymétrique entre des objets discrets. Elle s'inscrit dans la théorie des graphes : un réseau peut alors être défini comme étant un graphe où les nœuds (sommets) ou les arêtes (ou « arcs », lorsque le graphe est orienté) ont des attributs, comme une étiquette (tag).

Afficher plus

Séances de cours associées (52)

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.

Algorithme de Stein : Test d'identité polynomiale

Explore l'algorithme Stein pour le test d'identité polynomiale et la minimisation d'un problème de coupe.

Max Flav-Min Découpe dans les graphiques dirigés

Couvre le concept de réduction maximale du débit minimal dans les graphiques dirigés avec des contraintes de capacité.

Modèles graphiques : Représentation des distributions probabilistes

Couvre les modèles graphiques pour les distributions probabilistes à l'aide de graphiques, de nœuds et de bords.

Groupes d'automorphisme : Arbres et graphiques

Explore les groupes d'automorphisme dans les arbres et les graphiques, en se concentrant sur les extrémités et les types d'automorphismes.

Afficher plus

Concepts associés (32)

Réseau de flot

Problème de flot maximum

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

Arbre binaire

Théorie des réseaux

Afficher plus