Property |
Value |
dbo:abstract
|
- 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). (fr)
- 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). (fr)
|
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 10902 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-fr:année
|
- 1998 (xsd:integer)
- 2001 (xsd:integer)
- 2004 (xsd:integer)
- 2005 (xsd:integer)
|
prop-fr:auteur
| |
prop-fr:citation
|
- Chapter 7. Network Flow I (fr)
- Chapter 7. Network Flow I (fr)
|
prop-fr:consultéLe
| |
prop-fr:id
| |
prop-fr:isbn
|
- 0 (xsd:integer)
- 3 (xsd:integer)
- 978 (xsd:integer)
|
prop-fr:langue
|
- en (fr)
- fr (fr)
- en (fr)
- fr (fr)
|
prop-fr:lieu
|
- Mineola (fr)
- Mineola (fr)
|
prop-fr:lireEnLigne
| |
prop-fr:nom
|
- Théorème flot-max/coupe-min (fr)
- Théorème flot-max/coupe-min (fr)
|
prop-fr:numéroD'édition
| |
prop-fr:pagesTotales
|
- 374 (xsd:integer)
- 380 (xsd:integer)
- 496 (xsd:integer)
- 864 (xsd:integer)
|
prop-fr:présentationEnLigne
| |
prop-fr:sousTitre
|
- Algorithms and Complexity (fr)
- Networks and Matroids (fr)
- Algorithms and Complexity (fr)
- Networks and Matroids (fr)
|
prop-fr:série
|
- INF550 - Algorithmique avancée (fr)
- Lecture Slides for Algorithm Design (fr)
- INF550 - Algorithmique avancée (fr)
- Lecture Slides for Algorithm Design (fr)
|
prop-fr:titre
|
- Combinatorial Optimization (fr)
- Approximation Algorithms (fr)
- Algorithm Design (fr)
- Cours 2:Flots et couplages (fr)
- INF550 - Conception et analyse d’algorithmes (fr)
- Combinatorial Optimization (fr)
- Approximation Algorithms (fr)
- Algorithm Design (fr)
- Cours 2:Flots et couplages (fr)
- INF550 - Conception et analyse d’algorithmes (fr)
|
prop-fr:url
| |
prop-fr:wikiPageUsesTemplate
| |
prop-fr:éditeur
| |
prop-fr:énoncé
|
- Pour tout graphe orienté , tout couple de sommets, et pour tout vecteur de capacités positives, la valeur maximale du flot de à est égale à la capacité d'une coupe minimale séparant de . (fr)
- Pour tout graphe orienté , tout couple de sommets, et pour tout vecteur de capacités positives, la valeur maximale du flot de à est égale à la capacité d'une coupe minimale séparant de . (fr)
|
dct:subject
| |
rdfs:comment
|
- 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). (fr)
- 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). (fr)
|
rdfs:label
|
- Théorème flot-max/coupe-min (fr)
- Max-Flow-Min-Cut-Theorem (de)
- Max-flow min-cut theorem (en)
- Max-flow-min-cut-stelling (nl)
- Teorema de flux màxim tall mínim (ca)
- Teorema del flusso massimo e taglio minimo (it)
- 最大フロー最小カット定理 (ja)
|
rdfs:seeAlso
| |
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageWikiLink
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |