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