Maximum flow problem (original) (raw)
En optimització i teoria de grafs, el problema de flux màxim serveix per trobar la quantitat màxima de flux que pot passar per una xarxa de flux, des d'una sola font fins a un sol pou. El problema de flux màxim pot ser vist com un cas especial d'altres problemes de xarxes més complexes, com ara el . El valor màxim d'un flux s-t és igual a la capacitat mínima d'un tall s-t a la xarxa, tal com demostra el teorema de flux màxim tall mínim.
| Property | Value |
|---|---|
| dbo:abstract | En optimització i teoria de grafs, el problema de flux màxim serveix per trobar la quantitat màxima de flux que pot passar per una xarxa de flux, des d'una sola font fins a un sol pou. El problema de flux màxim pot ser vist com un cas especial d'altres problemes de xarxes més complexes, com ara el . El valor màxim d'un flux s-t és igual a la capacitat mínima d'un tall s-t a la xarxa, tal com demostra el teorema de flux màxim tall mínim. (ca) In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem. (en) 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[Quand ?], 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. (fr) 最大フロー問題（さいだいフローもんだい、英: Maximum flow problem）または最大流問題とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題であるの特殊ケースと見ることもできる。 最小カット問題（英: Minimum cut problem）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。 2部グラフの最大マッチング問題（英: Maximum bipartite matching）とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける。 (ja) Nella teoria dell'ottimizzazione, il problema del flusso massimo consiste nel trovare, in una rete di flusso con una sola sorgente ed un solo pozzo, un flusso ammissibile che sia massimo. Il problema del flusso massimo può essere visto come un caso particolare di problemi più complessi sulle reti di flusso, come il . Il valore massimo di un flusso s-t (ovvero un flusso generato da una sorgente s che si esaurisce in un pozzo t) è equivalente alla capacità minima di un taglio s-t nella medesima rete, come enunciato dal teorema del flusso massimo e taglio minimo. (it) Problem maksymalnego przepływu – zagadnienie często spotykane w informatyce. Polega ono na znalezieniu dla danej sieci przepływowej takiego przepływu którego wartość jest maksymalna, gdzie wartość przepływu jest zdefiniowana jako łączny przepływ opuszczający źródło. Bardziej formalnie, dla danego przepływu w sieci o źródle i ujściu jego wartość jest zdefiniowana następująco: Istnieje też uogólnienie tego problemu, w którym sieć zawiera wiele źródeł i ujść. Można jednak w prosty sposób sprowadzić je do przedstawionej wersji: Dla sieci zawierającej n źródeł oraz m ujść konstruujemy sieć gdzie: Ponadto: dla każdego dla każdego Innymi słowy, dodajemy do sieci wierzchołek połączony krawędziami o nieskończonej przepustowości ze wszystkimi źródłami oraz wierzchołek połączony krawędziami o nieskończonej przepustowości ze wszystkimi ujściami. Wierzchołek zwany jest superźródłem, zaś wierzchołek – superujściem. Maksymalny przepływ można znaleźć m.in. za pomocą algorytmu Edmondsa-Karpa opartego na metodzie Forda-Fulkersona. (pl) В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна. Задача о максимальном потоке является частным случаем более трудных задач, как например . (ru) O problema do fluxo máximo consiste em encontrar fluxo através de uma rede de fluxo que seja máximo O problema do fluxo máximo pode ser visto como um caso especial de um problema de fluxo mais complexo. Ele é o com so uma so mercadoria, e também como o com todos os fluxos zerados. O fluxo máximo esta relacionado ao corte em uma rede pelo . (pt) 在优化理论中,最大流问题涉及到在一个单源点、单汇点的网络流中找到一条最大的流。 最大流问题可以被看作是一个更复杂的网络流问题（循环问题，circulation problem）的特殊情况。s-t流（从源点s到汇点t）的最大值等于s-t割的最小容量，这被称为最大流最小割定理。 (zh) В теорії оптимізації та теорії графів, задача про максимальний потік полягає у знаходженні такого потоку за транспортною мережею, щоб сума потоків з витоку, або, що означає те ж саме, сума потоків до стоку була максимальна. Задача про максимальний потік є окремим випадком більш складних задач, таких, як, наприклад, задача про циркуляцію. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Pets_flow.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf |
| dbo:wikiPageID | 403165 (xsd:integer) |
| dbo:wikiPageLength | 40507 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102259293 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Push–relabel_maximum_flow_algorithm dbr:Robert_Tarjan dbr:Baseball dbc:Network_flow_problem dbr:Max-flow_min-cut_theorem dbr:Maximum_cardinality_matching dbr:Optimization_(mathematics) dbr:Glossary_of_graph_theory dbr:Greatest_common_divisor dbr:Andrew_V._Goldberg dbr:Path_(graph_theory) dbr:Linear_programming dbr:Minimum-cost_flow_problem dbr:Cut_(graph_theory) dbr:D._R._Fulkerson dbr:Flow_network dbr:Breadth-first_search dbr:Dinic's_algorithm dbr:Discrete_mathematics dbr:Edmonds–Karp_algorithm dbr:Ford–Fulkerson_algorithm dbr:James_B._Orlin dbr:Ted_Harris_(mathematician) dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Directed_acyclic_graph dbr:Circulation_problem dbr:Image_segmentation dbr:Kurt_Mehlhorn dbr:Rational_numbers dbr:Dynamic_trees dbr:Lester_R._Ford,_Jr. dbr:Daniel_D._Sleator dbr:Residual_graph dbr:Push-relabel_algorithm dbr:Push–relabel_algorithm dbr:Robert_E._Tarjan dbr:Strongly_NP-hard dbr:File:Baseball_Elimination_Problem.png dbr:File:Maxflow_imagesegmentation_image.png dbr:File:Maxflow_imagesegmentation_network.png dbr:File:Maxflow_imagesegmentation_result.png dbr:File:Maximum_bipartite_matching_to_max_flow.svg dbr:File:Multi-source_multi-sink_flow_problem.svg dbr:File:Node_splitting.svg dbr:File:Pets_flow.svg dbr:File:Simpe_flow_network.svg dbr:Joseph_Cheriyan |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Harvtxt dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Var dbt:Mset |
| dcterms:subject | dbc:Network_flow_problem dbc:Computational_problems_in_graph_theory |
| gold:hypernym | dbr:Maximum |
| rdf:type | dbo:Prison yago:WikicatMathematicalProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:State100024720 yago:WikicatAlgorithms |
| rdfs:comment | En optimització i teoria de grafs, el problema de flux màxim serveix per trobar la quantitat màxima de flux que pot passar per una xarxa de flux, des d'una sola font fins a un sol pou. El problema de flux màxim pot ser vist com un cas especial d'altres problemes de xarxes més complexes, com ara el . El valor màxim d'un flux s-t és igual a la capacitat mínima d'un tall s-t a la xarxa, tal com demostra el teorema de flux màxim tall mínim. (ca) In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem. (en) 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[Quand ?], 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. (fr) 最大フロー問題（さいだいフローもんだい、英: Maximum flow problem）または最大流問題とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題であるの特殊ケースと見ることもできる。 最小カット問題（英: Minimum cut problem）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。 2部グラフの最大マッチング問題（英: Maximum bipartite matching）とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける。 (ja) Nella teoria dell'ottimizzazione, il problema del flusso massimo consiste nel trovare, in una rete di flusso con una sola sorgente ed un solo pozzo, un flusso ammissibile che sia massimo. Il problema del flusso massimo può essere visto come un caso particolare di problemi più complessi sulle reti di flusso, come il . Il valore massimo di un flusso s-t (ovvero un flusso generato da una sorgente s che si esaurisce in un pozzo t) è equivalente alla capacità minima di un taglio s-t nella medesima rete, come enunciato dal teorema del flusso massimo e taglio minimo. (it) В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна. Задача о максимальном потоке является частным случаем более трудных задач, как например . (ru) O problema do fluxo máximo consiste em encontrar fluxo através de uma rede de fluxo que seja máximo O problema do fluxo máximo pode ser visto como um caso especial de um problema de fluxo mais complexo. Ele é o com so uma so mercadoria, e também como o com todos os fluxos zerados. O fluxo máximo esta relacionado ao corte em uma rede pelo . (pt) 在优化理论中,最大流问题涉及到在一个单源点、单汇点的网络流中找到一条最大的流。 最大流问题可以被看作是一个更复杂的网络流问题（循环问题，circulation problem）的特殊情况。s-t流（从源点s到汇点t）的最大值等于s-t割的最小容量，这被称为最大流最小割定理。 (zh) В теорії оптимізації та теорії графів, задача про максимальний потік полягає у знаходженні такого потоку за транспортною мережею, щоб сума потоків з витоку, або, що означає те ж саме, сума потоків до стоку була максимальна. Задача про максимальний потік є окремим випадком більш складних задач, таких, як, наприклад, задача про циркуляцію. (uk) Problem maksymalnego przepływu – zagadnienie często spotykane w informatyce. Polega ono na znalezieniu dla danej sieci przepływowej takiego przepływu którego wartość jest maksymalna, gdzie wartość przepływu jest zdefiniowana jako łączny przepływ opuszczający źródło. Bardziej formalnie, dla danego przepływu w sieci o źródle i ujściu jego wartość jest zdefiniowana następująco: Ponadto: dla każdego dla każdego Maksymalny przepływ można znaleźć m.in. za pomocą algorytmu Edmondsa-Karpa opartego na metodzie Forda-Fulkersona. (pl) |
| rdfs:label | Problema del flux màxim (ca) Problème de flot maximum (fr) Problema del flusso massimo (it) 最大フロー問題 (ja) Maximum flow problem (en) Problem maksymalnego przepływu (pl) Problema da vazão máxima (pt) Задача о максимальном потоке (ru) Задача про максимальний потік (uk) 最大流问题 (zh) |
| owl:sameAs | freebase:Maximum flow problem yago-res:Maximum flow problem wikidata:Maximum flow problem dbpedia-ca:Maximum flow problem dbpedia-fa:Maximum flow problem dbpedia-fr:Maximum flow problem dbpedia-hu:Maximum flow problem dbpedia-it:Maximum flow problem dbpedia-ja:Maximum flow problem dbpedia-pl:Maximum flow problem dbpedia-pt:Maximum flow problem dbpedia-ru:Maximum flow problem dbpedia-sr:Maximum flow problem dbpedia-th:Maximum flow problem dbpedia-uk:Maximum flow problem dbpedia-vi:Maximum flow problem dbpedia-zh:Maximum flow problem https://global.dbpedia.org/id/2SCtx |
| prov:wasDerivedFrom | wikipedia-en:Maximum_flow_problem?oldid=1102259293&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Baseball_Elimination_Problem.png wiki-commons:Special:FilePath/Maxflow_imagesegmentation_image.png wiki-commons:Special:FilePath/Maxflow_imagesegmentation_network.png wiki-commons:Special:FilePath/Maxflow_imagesegmentation_result.png wiki-commons:Special:FilePath/Maximum_bipartite_matching_to_max_flow.svg wiki-commons:Special:FilePath/Multi-source_multi-sink_flow_problem.svg wiki-commons:Special:FilePath/Node_splitting.svg wiki-commons:Special:FilePath/Pets_flow.svg wiki-commons:Special:FilePath/Simpe_flow_network.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Maximum_flow_problem |
| is dbo:wikiPageRedirects of | dbr:Max-flow dbr:Max-flow_problem dbr:Max_flow dbr:Max_flow_problem dbr:Maxflow dbr:Maximal_flow dbr:Maximal_flow_problem dbr:Maximum-flow_problem dbr:Maximum_flow dbr:Flow_algorithm dbr:Integral_flow_theorem |
| is dbo:wikiPageWikiLink of | dbr:Satish_Rao dbr:List_of_algorithms dbr:Algorithm dbr:Approximate_max-flow_min-cut_theorem dbr:Richard_M._Karp dbr:Kőnig's_theorem_(graph_theory) dbr:L._R._Ford_Jr. dbr:List_of_important_publications_in_mathematics dbr:Max-flow_min-cut_theorem dbr:Maximum_cardinality_matching dbr:Network_flow_problem dbr:Alexander_V._Karzanov dbr:George_Dantzig dbr:Gomory–Hu_tree dbr:Andrew_V._Goldberg dbr:Link/cut_tree dbr:Closure_problem dbr:Hopcroft–Karp_algorithm dbr:Market_equilibrium_computation dbr:Widest_path_problem dbr:K-edge-connected_graph dbr:Lattice_of_stable_matchings dbr:Minimum-cost_flow_problem dbr:D._R._Fulkerson dbr:Flow_network dbr:Barrier_resilience dbr:Breadth-first_search dbr:Dinic's_algorithm dbr:Edmonds–Karp_algorithm dbr:Ford–Fulkerson_algorithm dbr:Fractional_matching dbr:Graph_cuts_in_computer_vision dbr:Graph_traversal dbr:LEMON_(C++_library) dbr:Directed_acyclic_graph dbr:Circulation_problem dbr:Max-flow dbr:Max-flow_problem dbr:Max_flow dbr:Max_flow_problem dbr:Maxflow dbr:Maximal_flow dbr:Maximal_flow_problem dbr:Maximum-flow_problem dbr:Maximum_flow dbr:Minimum_spanning_tree dbr:Magic_number_(sports) dbr:Explicit_multi-threading dbr:Parallel_RAM dbr:Stoer–Wagner_algorithm dbr:Flow_algorithm dbr:Integral_flow_theorem |
| is rdfs:seeAlso of | dbr:Max-flow_min-cut_theorem |
| is foaf:primaryTopic of | wikipedia-en:Maximum_flow_problem |
