Max-flow min-cut theorem (original) (raw)
En optimització i teoria de grafs, el teorema de flux màxim tall mínim postula que en una xarxa de flux, la quantitat màxima de flux que pot passar d'una font fins a un pou és igual a la capacitat mínima que necessitem treure-li a la xarxa perquè no pugui passar més flux de la font al pou. El teorema de flux màxim tall mínim és un cas especial del teorema de dualitat i pot derivar-se en el teorema de Menger i el teorema de König-Egerváry.
| Property | Value |
|---|---|
| dbo:abstract | En optimització i teoria de grafs, el teorema de flux màxim tall mínim postula que en una xarxa de flux, la quantitat màxima de flux que pot passar d'una font fins a un pou és igual a la capacitat mínima que necessitem treure-li a la xarxa perquè no pugui passar més flux de la font al pou. El teorema de flux màxim tall mínim és un cas especial del teorema de dualitat i pot derivar-se en el teorema de Menger i el teorema de König-Egerváry. (ca) Fordova-Fulkersonova věta uvádí do vztahu maximální tok a v síti oddělující zdroj od stoku. Vychází z ní i myšlenka základního způsobu hledání maximálního toku - Fordova-Fulkersonova algoritmu, která řeší úlohu toku v síti. (cs) Auf dem Gebiet der Graphentheorie bezeichnet das Max-Flow-Min-Cut-Theorem einen Satz, der eine Aussage über den Zusammenhang von maximalen Flüssen und minimalen Schnitten eines Flussnetzwerkes gibt. Der Satz besagt: Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts. Der Satz ist eine Verallgemeinerung des Satzes von Menger. Er wurde im Jahr 1956 unabhängig von L.R. Ford Jr. und D.R. Fulkerson, sowie von P. Elias, und C.E. Shannon bewiesen. (de) En optimumigo, la teoremo pri maksimuma-fluo kaj minimuma-tranĉo asertas, ke la maksimuma fluo en trairanta de la fonto ĝis la dreno egalas al la sumo de pezoj de la minimuma tranĉo, t.e. aro da eĝoj kun la plej malgranda sumo de pezoj tiaj, ke se forigantaj, malligas la fonton kaj la drenon. La teoremo pri maksimuma-fluo kaj minimuma-tranĉo estas malĝenerala kazo de por kaj per ĝi oni povas devenigi kaj la . (eo) In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink. This is a special case of the duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem. (en) 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) De max-flow-min-cut-stelling is een stelling in de over de maximum flow in netwerken.Hij is afgeleid van de . De stelling luidt:De maximale hoeveelheid van flow is gelijk aan de minimale capaciteit van een s-t-. Informeel zegt de stelling dat de maximale flow in een netwerk bepaald wordt door de 'bottleneck': het is onmogelijk dat er tussen twee knopen meer data stroomt dan de zwakste verbinding ergens tussen deze twee knopen. (nl) Il teorema del flusso massimo e taglio minimo (conosciuto anche come max-flow min-cut) dice che, in una rete di flusso, il massimo flusso passante dalla sorgente (il nodo iniziale) al pozzo (il nodo finale) è uguale alla somma dei pesi degli archi nel taglio minimo. Si tratta di una generalizzazione del problema primale standard, tipico della programmazione lineare. Il teorema fu dimostrato da P. Elias, A. Feinstein, e C.E. Shannon nel 1956, e indipendentemente anche da L.R. Ford Jr. e nello stesso anno. (it) 最大フロー最小カット定理（さいだいフローさいしょうカットていり、英: Max-flow min-cut theorem）は、フローネットワークにおいて最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。 (ja) No campo da Otimização, o teorema do fluxo máximo-corte mínimo afirma que em um fluxo de rede, o valor máximo do fluxo passando de um ponto-origem até um ponto destino é igual à sua capacidade mínima, que quando removida da rede de uma forma específica ocasiona a situação onde nenhum fluxo passa mais entre a origem e o destino.. O teorema do fluxo máximo-corte mínimo é um caso especial do e pode ser usado pra derivar o Teorema de Menger e o . (pt) Satsen om max-flöde, minsta-snitt säger att för en given viktad graf är det största möjliga flödet mellan två noder lika med det minsta möjliga snitt som separerar dessa två noder. Satsen är av stor vikt inom optimeringslära och har praktiska tillämpningar inom till exempel bildanalys och datorseende. (sv) Теорема — — теорема про найбільший потік у графі, тісно пов'язана з теоремою Менгера. Формулювання: величина найбільшого потоку в графі шляхів дорівнює величині пропускної спроможності його найменшого розрізу. Достатність: будь-який потік між вершинами t і s менший або дорівнює величині будь-якого розрізу. Нехай дано деякий потік і деякий розріз. Величина цього потоку складається з величин «вантажів», що перевозяться по всіх можливих шляхах з вершини t до s. Кожен такий шлях повинен мати спільне ребро з цим розрізом. Оскільки по кожному ребру перерізу сумарно не можна перевезти «вантажу» більше, ніж його пропускна здатність, то сума всіх вантажів менша або дорівнює сумі всіх пропускних здібностей ребер даного розрізу. Твердження доведено. Звідси випливає, що будь-який потік менший або дорівнює величині найменшого розрізу, а отже й найбільший потік менший або дорівнює величині найменшого перерізу. На цій теоремі ґрунтується алгоритм Форда — Фалкерсона пошуку найбільшого потоку в графі, він же є доведенням необхідності даної теореми, тобто воно є конструктивним. (uk) 在最优化理论中，最大流最小割定理提供了对于一个网络流，从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和。 最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和。 (zh) Теорема Форда — Фалкерсо́на — теорема о максимальном потоке в графе, тесно связанная с теоремой Менгера. Звучит так: величина максимального потока в графе путей равна величине пропускной способности его минимального разреза. Достаточность: любой поток между вершинами t и s меньше или равен величине любого сечения.Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин «грузов», перевозимых по всем возможным путям из вершины t в s. Каждый такой путь обязан иметь общее ребро с данным сечением. Так как по каждому ребру сечения суммарно нельзя перевести «груза» больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна сумме всех пропускных способностей рёбер данного сечения. Утверждение доказано. Отсюда следует, что любой поток меньше или равен величине минимального сечения, а значит и максимальный поток меньше или равен величине минимального сечения. На этой теореме основан алгоритм Форда — Фалкерсона поиска максимального потока в графе, он же является доказательством необходимости данной теоремы, то есть оно является конструктивным. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Max_flow.svg?width=300 |
| dbo:wikiPageID | 78130 (xsd:integer) |
| dbo:wikiPageLength | 23839 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124909077 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Menger's_theorem dbr:Approximate_max-flow_min-cut_theorem dbc:Network_flow_problem dbr:Kőnig's_theorem_(graph_theory) dbr:L._R._Ford_Jr. dbc:Combinatorial_optimization dbr:Maximum_flow_problem dbr:Optimization_(mathematics) dbr:Glossary_of_graph_theory dbr:Computer_science dbr:Dual_linear_program dbr:GNRS_conjecture dbr:Linear_programming dbr:Minimum_cut dbr:D._R._Fulkerson dbr:Flow_network dbr:Ford-Fulkerson_algorithm dbr:Directed_graph dbr:Edmonds–Karp_algorithm dbr:Ford–Fulkerson_algorithm dbr:Kenneth_Steiglitz dbc:Theorems_in_graph_theory dbr:Max-flow dbr:Maximum_flow dbr:Vijay_Vazirani dbr:Christos_H._Papadimitriou dbr:Dual_problem dbr:Linear_program dbr:Min-cut dbr:File:Image_segmentation.jpg dbr:File:Max-flow_min-cut_project-selection.svg dbr:File:Max_flow.svg |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Cite_book dbt:Math dbt:Mvar dbt:Reflist dbt:See_also dbt:Short_description |
| dct:subject | dbc:Network_flow_problem dbc:Combinatorial_optimization dbc:Theorems_in_graph_theory |
| gold:hypernym | dbr:Case |
| rdf:type | owl:Thing yago:WikicatMathematicalTheorems yago:WikicatTheoremsInDiscreteMathematics yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 dbo:SupremeCourtOfTheUnitedStatesCase yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | En optimització i teoria de grafs, el teorema de flux màxim tall mínim postula que en una xarxa de flux, la quantitat màxima de flux que pot passar d'una font fins a un pou és igual a la capacitat mínima que necessitem treure-li a la xarxa perquè no pugui passar més flux de la font al pou. El teorema de flux màxim tall mínim és un cas especial del teorema de dualitat i pot derivar-se en el teorema de Menger i el teorema de König-Egerváry. (ca) Fordova-Fulkersonova věta uvádí do vztahu maximální tok a v síti oddělující zdroj od stoku. Vychází z ní i myšlenka základního způsobu hledání maximálního toku - Fordova-Fulkersonova algoritmu, která řeší úlohu toku v síti. (cs) Auf dem Gebiet der Graphentheorie bezeichnet das Max-Flow-Min-Cut-Theorem einen Satz, der eine Aussage über den Zusammenhang von maximalen Flüssen und minimalen Schnitten eines Flussnetzwerkes gibt. Der Satz besagt: Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts. Der Satz ist eine Verallgemeinerung des Satzes von Menger. Er wurde im Jahr 1956 unabhängig von L.R. Ford Jr. und D.R. Fulkerson, sowie von P. Elias, und C.E. Shannon bewiesen. (de) En optimumigo, la teoremo pri maksimuma-fluo kaj minimuma-tranĉo asertas, ke la maksimuma fluo en trairanta de la fonto ĝis la dreno egalas al la sumo de pezoj de la minimuma tranĉo, t.e. aro da eĝoj kun la plej malgranda sumo de pezoj tiaj, ke se forigantaj, malligas la fonton kaj la drenon. La teoremo pri maksimuma-fluo kaj minimuma-tranĉo estas malĝenerala kazo de por kaj per ĝi oni povas devenigi kaj la . (eo) In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink. This is a special case of the duality theorem for linear programs and can be used to derive Menger's theorem and the Kőnig–Egerváry theorem. (en) 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) De max-flow-min-cut-stelling is een stelling in de over de maximum flow in netwerken.Hij is afgeleid van de . De stelling luidt:De maximale hoeveelheid van flow is gelijk aan de minimale capaciteit van een s-t-. Informeel zegt de stelling dat de maximale flow in een netwerk bepaald wordt door de 'bottleneck': het is onmogelijk dat er tussen twee knopen meer data stroomt dan de zwakste verbinding ergens tussen deze twee knopen. (nl) Il teorema del flusso massimo e taglio minimo (conosciuto anche come max-flow min-cut) dice che, in una rete di flusso, il massimo flusso passante dalla sorgente (il nodo iniziale) al pozzo (il nodo finale) è uguale alla somma dei pesi degli archi nel taglio minimo. Si tratta di una generalizzazione del problema primale standard, tipico della programmazione lineare. Il teorema fu dimostrato da P. Elias, A. Feinstein, e C.E. Shannon nel 1956, e indipendentemente anche da L.R. Ford Jr. e nello stesso anno. (it) 最大フロー最小カット定理（さいだいフローさいしょうカットていり、英: Max-flow min-cut theorem）は、フローネットワークにおいて最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。 (ja) No campo da Otimização, o teorema do fluxo máximo-corte mínimo afirma que em um fluxo de rede, o valor máximo do fluxo passando de um ponto-origem até um ponto destino é igual à sua capacidade mínima, que quando removida da rede de uma forma específica ocasiona a situação onde nenhum fluxo passa mais entre a origem e o destino.. O teorema do fluxo máximo-corte mínimo é um caso especial do e pode ser usado pra derivar o Teorema de Menger e o . (pt) Satsen om max-flöde, minsta-snitt säger att för en given viktad graf är det största möjliga flödet mellan två noder lika med det minsta möjliga snitt som separerar dessa två noder. Satsen är av stor vikt inom optimeringslära och har praktiska tillämpningar inom till exempel bildanalys och datorseende. (sv) 在最优化理论中，最大流最小割定理提供了对于一个网络流，从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和。 最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和。 (zh) Теорема Форда — Фалкерсо́на — теорема о максимальном потоке в графе, тесно связанная с теоремой Менгера. Звучит так: величина максимального потока в графе путей равна величине пропускной способности его минимального разреза. Отсюда следует, что любой поток меньше или равен величине минимального сечения, а значит и максимальный поток меньше или равен величине минимального сечения. На этой теореме основан алгоритм Форда — Фалкерсона поиска максимального потока в графе, он же является доказательством необходимости данной теоремы, то есть оно является конструктивным. (ru) Теорема — — теорема про найбільший потік у графі, тісно пов'язана з теоремою Менгера. Формулювання: величина найбільшого потоку в графі шляхів дорівнює величині пропускної спроможності його найменшого розрізу. Звідси випливає, що будь-який потік менший або дорівнює величині найменшого розрізу, а отже й найбільший потік менший або дорівнює величині найменшого перерізу. На цій теоремі ґрунтується алгоритм Форда — Фалкерсона пошуку найбільшого потоку в графі, він же є доведенням необхідності даної теореми, тобто воно є конструктивним. (uk) |
| rdfs:label | Teorema de flux màxim tall mínim (ca) Fordova–Fulkersonova věta (cs) Max-Flow-Min-Cut-Theorem (de) Teoremo pri maksimuma-fluo kaj minimuma-tranĉo (eo) Théorème flot-max/coupe-min (fr) Teorema del flusso massimo e taglio minimo (it) 最大フロー最小カット定理 (ja) Max-flow min-cut theorem (en) Max-flow-min-cut-stelling (nl) Teorema do fluxo máximo e corte mínimo (pt) Теорема Форда — Фалкерсона (ru) Max-flöde, minsta-snitt (sv) 最大流最小割定理 (zh) Теорема Форда — Фалкерсона (uk) |
| rdfs:seeAlso | dbr:Maximum_flow_problem dbr:Menger's_Theorem dbr:Cederbaum's_maximum_flow_theorem |
| owl:sameAs | freebase:Max-flow min-cut theorem yago-res:Max-flow min-cut theorem wikidata:Max-flow min-cut theorem dbpedia-ca:Max-flow min-cut theorem dbpedia-cs:Max-flow min-cut theorem dbpedia-de:Max-flow min-cut theorem dbpedia-eo:Max-flow min-cut theorem dbpedia-fa:Max-flow min-cut theorem dbpedia-fr:Max-flow min-cut theorem dbpedia-he:Max-flow min-cut theorem dbpedia-hu:Max-flow min-cut theorem dbpedia-it:Max-flow min-cut theorem dbpedia-ja:Max-flow min-cut theorem dbpedia-nl:Max-flow min-cut theorem dbpedia-pt:Max-flow min-cut theorem dbpedia-ru:Max-flow min-cut theorem dbpedia-sv:Max-flow min-cut theorem dbpedia-uk:Max-flow min-cut theorem dbpedia-vi:Max-flow min-cut theorem dbpedia-zh:Max-flow min-cut theorem https://global.dbpedia.org/id/4o2d7 |
| prov:wasDerivedFrom | wikipedia-en:Max-flow_min-cut_theorem?oldid=1124909077&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Image_segmentation.jpg wiki-commons:Special:FilePath/Max-flow_min-cut_project-selection.svg wiki-commons:Special:FilePath/Max_flow.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Max-flow_min-cut_theorem |
| is dbo:knownFor of | dbr:George_Dantzig |
| is dbo:wikiPageRedirects of | dbr:Max-flow-min-cut dbr:Max-flow_min-cut dbr:Max_flow_in_networks dbr:Max_flow_min_cut dbr:Max_flow_min_cut_theorem dbr:Maxflow-mincut dbr:Maximum_flow,_minimum_cut_theorem dbr:Maximum_flow/minimum_cut_theorem dbr:Maximum_flow_minimum_cut_theorem dbr:Max-Flow_Min-Cut_theorem dbr:Max-flow,_mincut_theorem dbr:Min_cut_max_flow dbr:Minimal_cut dbr:MFMC |
| is dbo:wikiPageWikiLink of | dbr:Push–relabel_maximum_flow_algorithm dbr:Menger's_theorem dbr:Approximate_max-flow_min-cut_theorem dbr:Kőnig's_theorem_(graph_theory) dbr:L._R._Ford_Jr. dbr:Segmentation-based_object_categorization dbr:Connectivity_(graph_theory) dbr:Maximum_flow_problem dbr:Network_flow_problem dbr:Pipe_network_analysis dbr:Quadratic_pseudo-Boolean_optimization dbr:George_Dantzig dbr:Glossary_of_graph_theory dbr:Gomory–Hu_tree dbr:Cooperative_diversity dbr:Skew-symmetric_graph dbr:Closure_problem dbr:Fulkerson_Prize dbr:Hall's_marriage_theorem dbr:Active_contour_model dbr:Cederbaum's_maximum_flow_theorem dbr:Dual_linear_program dbr:GNRS_conjecture dbr:K-edge-connected_graph dbr:Karger's_algorithm dbr:Linear_network_coding dbr:Minimum_cut dbr:Optical_flow dbr:Cut_(graph_theory) dbr:Flow_network dbr:Ford–Fulkerson_algorithm dbr:Graph_cut_optimization dbr:Graph_cuts_in_computer_vision dbr:Iterative_compression dbr:Max-flow-min-cut dbr:Max-flow_min-cut dbr:Max_flow_in_networks dbr:Max_flow_min_cut dbr:Max_flow_min_cut_theorem dbr:Maxflow-mincut dbr:Maximum_flow,_minimum_cut_theorem dbr:Maximum_flow/minimum_cut_theorem dbr:Maximum_flow_minimum_cut_theorem dbr:Unimodular_matrix dbr:Extended_natural_numbers dbr:Max-Flow_Min-Cut_theorem dbr:Max-flow,_mincut_theorem dbr:Min_cut_max_flow dbr:Minimal_cut dbr:MFMC |
| is foaf:primaryTopic of | wikipedia-en:Max-flow_min-cut_theorem |
