In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Satz von Menger (de)
- Théorème de Menger (fr)
- Menger's theorem (en)
- 멩거의 정리 (ko)
- メンガーの定理 (ja)
- Teorema de Menger (pt)
- Теорема Менгера (ru)
- Теорема Менгера (uk)
- 门格尔定理 (zh)
|
| rdfs:comment
| - In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs. (en)
- メンガーの定理（メンガーのていり、英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小辺カット（辺切断，除去することで x と y が連結されなくなる最小の辺の数）の大きさは、x から y の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小点カット（点切断。除去することで x と y が連結されなくなる最小の頂点の数）の大きさは、x から y の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。 (ja)
- En théorie des graphes, le théorème de Menger est à l'origine du théorème flot-max/coupe-min qui le généralise. Il fut prouvé par Karl Menger en 1927. (fr)
- 그래프 이론의 수학적 분야인 멩거의 정리에서는 유한 그래프에서 최소 의 크기가 정점 쌍 사이에서 발견될 수 있는 최대 분리 경로 수와 동일하다고 한다. 1927년에 카를 멩거(Karl Menger)가 증명한 것으로 그래프의 연결성은 연결 그래프를 특징짓는다. 이것은 에 의해 일반화되며, 이는 가중 그래프로 선형 프로그램에 대한 의 특별한 경우이다. 이러한 멩거의 정리를 무한한 그래프로 확대하여 추측한다면 이것은 에르되시-멩거 추측이라고 한다. (ko)
- Теорема Менгера — основной результат о связности в конечном неориентированном графе, тесно связанный с теоремой Форда — Фалкерсона.Сформулирована и доказана в 1927 году Карлом Менгером (мл.). (ru)
- Теорема Менгера — основний результат про зв'язність у скінченному неорієнтованому графі, тісно пов'язаний із теоремою Форда — Фалкерсона. Сформулював та довів 1927 року . (uk)
- 在图论中，门格尔定理（英：Menger's Theorem）指在有限图中，最小的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于1927年发表。这被认为是图论中最重要且经典的定理之一。该定理刻畫了连通性的性质，增加了邊的權重可推廣成最大流量小割定理，而最大流量小割定理是線性規劃的强对偶性定理的直接推論。 (zh)
- Der Satz von Menger ist eines der klassischen Ergebnisse der Graphentheorie. Er wurde von 1927 von Karl Menger bewiesen und stellt einen Zusammenhang zwischen der Anzahl disjunkter Wege und der Größe von Trennern in einem Graphen her. Insbesondere die globale Variante des Satzes trifft auch Aussagen über den K-Zusammenhang und den Kantenzusammenhang eines Graphen. Der Satz ist eine Verallgemeinerung des Satzes von König (1916), wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht. (de)
- Em teoria dos grafos e áreas relacionadas da matemática, o teorema de Menger é um resultado básico sobre conectividade em grafos finitos não direcionados. Foi provada a K-aresta-conectividade e K-vértice-conectividade por Karl Menger em 1927. A versão para aresta-conectividade do teorema de Menger foi generalizada mais tarde pelo Teorema do Fluxo Máximo–Corte Mínimo. A versão do teorema de Menger para aresta-conectividade funciona da seguinte forma: A versão do teorema de Menger para vértice-conectividade funciona da seguinte forma: (pt)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| bot
| |
| date
| |
| fix-attempted
| |
| has abstract
| - Der Satz von Menger ist eines der klassischen Ergebnisse der Graphentheorie. Er wurde von 1927 von Karl Menger bewiesen und stellt einen Zusammenhang zwischen der Anzahl disjunkter Wege und der Größe von Trennern in einem Graphen her. Insbesondere die globale Variante des Satzes trifft auch Aussagen über den K-Zusammenhang und den Kantenzusammenhang eines Graphen. Der Satz ist eine Verallgemeinerung des Satzes von König (1916), wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht. Er lässt sich wie der Satz von König auch auf unendliche Graphen übertragen (Ron Aharoni, 2009). (de)
- In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices.Proved by Karl Menger in 1927, it characterizes the connectivity of a graph.It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs. (en)
- メンガーの定理（メンガーのていり、英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小辺カット（辺切断，除去することで x と y が連結されなくなる最小の辺の数）の大きさは、x から y の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、x と y が隣接していない頂点であるとする。このとき、x と y の最小点カット（点切断。除去することで x と y が連結されなくなる最小の頂点の数）の大きさは、x から y の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。 (ja)
- En théorie des graphes, le théorème de Menger est à l'origine du théorème flot-max/coupe-min qui le généralise. Il fut prouvé par Karl Menger en 1927. (fr)
- 그래프 이론의 수학적 분야인 멩거의 정리에서는 유한 그래프에서 최소 의 크기가 정점 쌍 사이에서 발견될 수 있는 최대 분리 경로 수와 동일하다고 한다. 1927년에 카를 멩거(Karl Menger)가 증명한 것으로 그래프의 연결성은 연결 그래프를 특징짓는다. 이것은 에 의해 일반화되며, 이는 가중 그래프로 선형 프로그램에 대한 의 특별한 경우이다. 이러한 멩거의 정리를 무한한 그래프로 확대하여 추측한다면 이것은 에르되시-멩거 추측이라고 한다. (ko)
- Em teoria dos grafos e áreas relacionadas da matemática, o teorema de Menger é um resultado básico sobre conectividade em grafos finitos não direcionados. Foi provada a K-aresta-conectividade e K-vértice-conectividade por Karl Menger em 1927. A versão para aresta-conectividade do teorema de Menger foi generalizada mais tarde pelo Teorema do Fluxo Máximo–Corte Mínimo. A versão do teorema de Menger para aresta-conectividade funciona da seguinte forma: G é um grafo finito não direcionado e x e y são dois vértices distintos. Então o teorema afirma que o tamanho mínimo de arestas que precisam ser removidas para desconectar x e y é igual ao número máximo de caminhos aresta-independentes emparelhados de x para y.Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-arestas de corte é idêntico aos subgrafo maximal com um número mínimo de k caminhos aresta-independente entre qualquer par de nós x, y no subgrafo. A versão do teorema de Menger para vértice-conectividade funciona da seguinte forma: G é um grafo finito não direcionado e x e y são dois vértices não adjacentes. Então o teorema afirma que o número mínimo de vértices que precisam ser removidos para desconectar x e y é igual ao número máximo de caminhos vértice-independentes emparelhados de x para y.Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-vértices de corte é identico aos subgrafo maximal com um número mínimo de k caminhos vértice-independente entre qualquer par de nós x, y no subgrafo. (pt)
- Теорема Менгера — основной результат о связности в конечном неориентированном графе, тесно связанный с теоремой Форда — Фалкерсона.Сформулирована и доказана в 1927 году Карлом Менгером (мл.). (ru)
- Теорема Менгера — основний результат про зв'язність у скінченному неорієнтованому графі, тісно пов'язаний із теоремою Форда — Фалкерсона. Сформулював та довів 1927 року . (uk)
- 在图论中，门格尔定理（英：Menger's Theorem）指在有限图中，最小的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于1927年发表。这被认为是图论中最重要且经典的定理之一。该定理刻畫了连通性的性质，增加了邊的權重可推廣成最大流量小割定理，而最大流量小割定理是線性規劃的强对偶性定理的直接推論。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
