| 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 40507 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
